Overview

This problem asks us to find a permutation \(A\) of a given array \(C\) of \(N\) elements that maximizes the sum of absolute differences between adjacent elements: \(\sum_{i=1}^{N-1} |A_i - A_{i+1}|\).

---

Analysis

1. Intuitive Approach: Arranging in a Zigzag

To maximize the total contrast (the sum of absolute differences between adjacent elements), we need to make the differences between adjacent elements as large as possible. To achieve this, it is optimal to alternate between “small values” and “large values” (arranging them in a zigzag pattern).

For example, suppose the rearranged array \(A\) alternates between peaks (local maxima) and valleys (local minima) as follows: $\(A_1 < A_2 > A_3 < A_4 > A_5 \dots\)$

In this case, the sum of absolute differences of adjacent elements can be simplified by removing the absolute value signs as follows: $\(|A_1 - A_2| + |A_2 - A_3| + |A_3 - A_4| + |A_4 - A_5|\)\( \)\(= (A_2 - A_1) + (A_2 - A_3) + (A_4 - A_3) + (A_4 - A_5)\)\( \)\(= -A_1 + 2A_2 - 2A_3 + 2A_4 - A_5\)$

By simplifying the expression this way, we can see the “coefficient” that each element \(A_i\) contributes to the total sum: - Valleys (elements smaller than both neighbors): The coefficient is \(-2\) (or \(-1\) if it is at either end). - Peaks (elements larger than both neighbors): The coefficient is \(+2\) (or \(+1\) if it is at either end).

To maximize the total contrast, we should multiply the smaller values in the original array by large negative coefficients (\(-2\) or \(-1\)), and the larger values by large positive coefficients (\(+2\) or \(+1\)).

We first sort the original array \(C\) in ascending order and then consider the optimal assignment of coefficients based on the parity of \(N\).

---

2. When \(N\) is Even (\(N = 2M\))

When the number of elements is even, the number of peaks and valleys is equal. Of the two ends, one will be a peak and the other will be a valley. In this case, the configuration of coefficients is as follows: - Valleys (the \(M\) smallest elements): \(M-1\) coefficients of \(-2\), and \(1\) coefficient of \(-1\) - Peaks (the \(M\) largest elements): \(M-1\) coefficients of \(+2\), and \(1\) coefficient of \(+1\)

We assign the coefficients to the sorted array \(C\) as follows: - Multiply the \(M-1\) elements from \(C[0]\) to \(C[M-2]\) by \(-2\). - Multiply \(C[M-1]\) by \(-1\). - Multiply \(C[M]\) by \(+1\). - Multiply the \(M-1\) elements from \(C[M+1]\) to \(C[N-1]\) by \(+2\).

Concrete Example (When \(N = 4\), \(C = [1, 3, 6, 8]\), \(M = 2\))

• \(-2\) for the \(M-1=1\) element on the smaller side (\(C[0]=1\))
• \(-1\) for \(C[1]=3\)
• \(+1\) for \(C[2]=6\)
• \(+2\) for the \(M-1=1\) element on the larger side (\(C[3]=8\))

\[ans = -2 \times 1 - 3 + 6 + 2 \times 8 = -2 - 3 + 6 + 16 = 17\]

(Example of an actual optimal arrangement: \([3, 8, 1, 6]\) \(\rightarrow\) \(|3-8| + |8-1| + |1-6| = 5 + 7 + 5 = 17\))

---

3. When \(N\) is Odd (\(N = 2M + 1\))

When the number of elements is odd, there are two possible patterns: both ends are “valleys (small values)” or both ends are “peaks (large values)”. We choose the pattern that yields the larger sum.

Pattern 1: Both ends are valleys

There are \(M+1\) valleys and \(M\) peaks. - Valleys (the \(M+1\) smallest elements): the two ends are \(-1\), and the inner \(M-1\) elements are \(-2\) - Peaks (the \(M\) largest elements): since they are all internal, all \(M\) elements are \(+2\)

For the sorted array \(C\): - \(-2\) for the \(M-1\) elements from \(C[0]\) to \(C[M-2]\) - \(-1\) for the two boundary elements \(C[M-1]\) and \(C[M]\) - \(+2\) for the \(M\) elements from \(C[M+1]\) to \(C[N-1]\)

Pattern 2: Both ends are peaks

There are \(M\) valleys and \(M+1\) peaks. - Valleys (the \(M\) smallest elements): since they are all internal, all \(M\) elements are \(-2\) - Peaks (the \(M+1\) largest elements): the two ends are \(+1\), and the inner \(M-1\) elements are \(+2\)

For the sorted array \(C\): - \(-2\) for the \(M\) elements from \(C[0]\) to \(C[M-1]\) - \(+1\) for the two boundary elements \(C[M]\) and \(C[M+1]\) - \(+2\) for the \(M-1\) elements from \(C[M+2]\) to \(C[N-1]\)

---

Algorithm

1. Sort the input array \(C\) in ascending order.
2. If \(N\) is even, calculate the sum of each part using slicing based on the central boundary, and compute the value according to the formula.
3. If \(N\) is odd, calculate the two patterns described above: “both ends are valleys (ans1)” and “both ends are peaks (ans2)”, and find their maximum max(ans1, ans2).
4. Output the calculated maximum value.

---

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the array takes \(O(N \log N)\) time.
  • The subsequent sum calculation using slicing (sum) can be done in \(O(N)\) time. Thus, the total complexity is bottlenecked by the sorting step, resulting in \(O(N \log N)\). This is well within the time limit even for \(N \le 10^6\).
• Space Complexity: \(O(N)\)
  • We use \(O(N)\) memory to store the input array \(C\).

---

Implementation Points

• Fast I/O: Since the input size can be as large as \(N \le 10^6\), we can avoid I/O bottlenecks in Python by using sys.stdin.read().split() to read all inputs at once.

• Using Slices: By using slices like C[:M-1] or C[M+1:] to calculate range sums, the code becomes simpler and leverages Python’s internal C-optimized implementations, which is faster than writing explicit loops.

  Source Code

import sys


def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = [int(x) for x in input_data[1:]]

    # 昇順にソート
    C.sort()

    if N % 2 == 0:
        M = N // 2
        ans = -2 * sum(C[: M - 1]) - C[M - 1] + C[M] + 2 * sum(C[M + 1 :])
    else:
        M = N // 2
        ans1 = -2 * sum(C[: M - 1]) - C[M - 1] - C[M] + 2 * sum(C[M + 1 :])
        ans2 = -2 * sum(C[: M]) + C[M] + C[M + 1] + 2 * sum(C[M + 2 :])
        ans = max(ans1, ans2)

    print(ans)


if __name__ == "__main__":
    solve()

---

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