Overview

This problem asks you to select \(K+1\) out of \(N\) given observation spots (with their elevations), rearrange them in a line, and maximize the sum of absolute differences between adjacent elements (total thrill value).

Analysis

1. Problem Reformulation

“Building suspension bridges at \(K\) adjacent locations from \(N\) spots” is equivalent to selecting \(K+1\) spots from \(N\) and forming a path by arranging them in a line. Let the elevations of the selected \(K+1\) spots, sorted in ascending order, be \(Y_1 \le Y_2 \le \dots \le Y_{K+1}\). Let \(X_1, X_2, \dots, X_{K+1}\) be a rearrangement of these values. The value we want to maximize is: $\( \sum_{i=1}^{K} |X_{i+1} - X_i| \)$

2. Arrangement that Maximizes the Sum of Absolute Differences (Zigzag Arrangement)

To maximize the total sum of absolute differences, the optimal strategy is to arrange adjacent elements in an alternating pattern of ”(small) → (large) → (small) → (large)” (a zigzag pattern).

For example, if the 4 selected elements are \(Y = [1, 3, 6, 8]\), the optimal arrangement is \([3, 8, 1, 6]\). The thrill value is: $\( |8 - 3| + |1 - 8| + |6 - 1| = 5 + 7 + 5 = 17 \)\( Removing the absolute values and expanding the expression: \)\( (8 - 3) + (8 - 1) + (6 - 1) = 2 \times 8 + 1 \times 6 - 2 \times 1 - 1 \times 3 \)\( We can see that larger elements get positive coefficients (\)+2, +1\() and smaller elements get negative coefficients (\)-2, -1$).

In this way, the coefficient pattern is determined by the parity of the number of elements \(K+1\).

3. Case Analysis by Parity of \(K\)

To maximize the value, the optimal strategy is to “assign the largest values in \(A\) to the largest positive coefficients, and the smallest values in \(A\) to the largest negative coefficients”. Therefore, we sort the original array \(A\) in ascending order and assign elements from both ends.

Pattern A: When \(K\) is odd (number of elements \(K+1\) is even)

Express the number of elements as \(2m + 2\) (\(m = (K-1)/2\)). In this case, the optimal coefficient assignment is uniquely determined: - The largest \(m\) elements get \(+2\), the next one gets \(+1\) - The smallest \(m\) elements get \(-2\), the next one gets \(-1\)

Therefore, for the sorted array \(A\), the maximum value can be computed as: $\( 2 \sum_{i=N-m}^{N-1} A_i + A_{N-m-1} - 2 \sum_{i=0}^{m-1} A_i - A_m \)$

Pattern B: When \(K\) is even (number of elements \(K+1\) is odd)

Express the number of elements as \(2m + 1\) (\(m = K/2\)). In this case, depending on whether the endpoints of the zigzag are “peaks” or “valleys,” two coefficient patterns are possible:

1. More peaks pattern
   • The largest \(m-1\) elements get \(+2\), the next 2 get \(+1\)
   • The smallest \(m\) elements get \(-2\)
2. More valleys pattern
   • The largest \(m\) elements get \(+2\)
   • The smallest \(m-1\) elements get \(-2\), the next 2 get \(-1\)

We adopt whichever of these two patterns gives the larger result.

---

Algorithm

1. Sort the elevation array \(A\) of observation spots in ascending order.
2. If \(K\) is odd:
   • Compute using the formula for Pattern A with slicing and sum().
3. If \(K\) is even:
   • Compute the values for both formulas of Pattern B and adopt the larger one.

---

Complexity

• Time Complexity: \(O(N \log N)\)

  • Sorting array \(A\) takes \(O(N \log N)\).
  • The subsequent sum calculations (using slicing and sum()) take at most \(O(N)\), so sorting is the overall bottleneck. Since \(N \le 10^6\), this comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • Memory space is needed to store the input array \(A\).

---

Implementation Notes

• When \(K\) is even, you need to compare two patterns. Since array index (boundary value) specification can easily become complex, it is safe to verify with concrete examples (e.g., when \(K=2\)) to ensure indices are not off by one.

• In Python, you can efficiently compute the sum of a specified range using sum(A[l:r]).

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    A.sort()

    if K % 2 == 1:
        m = (K - 1) // 2
        ans = 2 * sum(A[N - m :]) + A[N - m - 1] - 2 * sum(A[:m]) - A[m]
    else:
        m1 = K // 2 - 1
        m2 = K // 2
        ans1 = (
            2 * sum(A[N - m1 :])
            + A[N - m2]
            + A[N - m2 - 1]
            - 2 * sum(A[:m2])
        )

        m3 = K // 2
        m4 = K // 2 - 1
        ans2 = (
            2 * sum(A[N - m3 :])
            - 2 * sum(A[:m4])
            - A[m4]
            - A[m4 + 1]
        )

        ans = max(ans1, ans2)

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.