Overview

This problem asks us to rearrange \(N\) given numbers in a line to maximize the sum of absolute differences between adjacent elements (the total contrast).

Observation

1. Basic Idea for Maximizing the Total Contrast

Let the rearranged array be \(A_1, A_2, \ldots, A_N\). The value we want to maximize is \(\sum_{i=1}^{N-1} |A_i - A_{i+1}|\).

Let’s consider how to remove the absolute value symbols. To maximize the sum, it is optimal to alternately arrange “large numbers” and “small numbers” so that the difference between each adjacent pair is always in the form of “(large number) - (small number)”.

By arranging them alternately like this, the sign (\(+\) or \(-\)) with which each element \(C_i\) contributes to the total sum and its frequency (coefficient) are determined. - “Valley” elements (small numbers): Since they are smaller than both of their adjacent elements, they contribute with a negative sign (\(-1\) or \(-2\)) in the difference calculations. - “Peak” elements (large numbers): Since they are larger than both of their adjacent elements, they contribute with a positive sign (\(+1\) or \(+2\)) in the difference calculations. - Elements at the ends: Since they have only one adjacent element, they contribute only once (coefficient of \(\pm 1\)). - Elements in the interior: Since they have two adjacent elements, they contribute twice (coefficient of \(\pm 2\)).

Using this property, we sort the given array \(C\) in ascending order so that \(C_0 \leq C_1 \leq \ldots \leq C_{N-1}\), and then divide the elements into a “small group (valleys)” and a “large group (peaks)”.

---

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

We divide the elements in half into \(k\) small elements (\(C_0, \ldots, C_{k-1}\)) and \(k\) large elements (\(C_k, \ldots, C_{2k-1}\)).

In this case, the optimal arrangement places a peak at one end and a valley at the other (e.g., Valley, Peak, Valley, Peak, \(\ldots\), Valley, Peak). - We place the smallest element among the peaks, \(C_k\), at the end, giving it a coefficient of \(+1\). The other peaks are placed in the interior, giving them a coefficient of \(+2\). - We place the largest element among the valleys, \(C_{k-1}\), at the end, giving it a coefficient of \(-1\). The other valleys are placed in the interior, giving them a coefficient of \(-2\).

Therefore, the maximum value can be found using the following formula: $\( \text{Ans} = 2 \sum_{i=k}^{N-1} C_i - C_k - 2 \sum_{i=0}^{k-1} C_i + C_{k-1} \)$

---

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

Since the balance between the number of peaks and valleys differs by one, we need to compare the following two patterns.

Pattern 1: When there are \(k+1\) peaks and \(k\) valleys

Both ends will be “peaks” (e.g., Peak, Valley, Peak, \(\ldots\), Valley, Peak). - We place the two smallest elements among the peaks, \(C_k\) and \(C_{k+1}\), at the ends, giving them a coefficient of \(+1\). The remaining peaks have a coefficient of \(+2\). - Since all valleys are in the interior, they all have a coefficient of \(-2\).

\[ \text{Ans}_1 = 2 \sum_{i=k+2}^{N-1} C_i + C_k + C_{k+1} - 2 \sum_{i=0}^{k-1} C_i \]

Pattern 2: When there are \(k\) peaks and \(k+1\) valleys

Both ends will be “valleys” (e.g., Valley, Peak, Valley, \(\ldots\), Peak, Valley). - We place the two largest elements among the valleys, \(C_{k-1}\) and \(C_k\), at the ends, giving them a coefficient of \(-1\). The remaining valleys have a coefficient of \(-2\). - Since all peaks are in the interior, they all have a coefficient of \(+2\).

\[ \text{Ans}_2 = 2 \sum_{i=k+1}^{N-1} C_i - 2 \sum_{i=0}^{k-2} C_i - C_{k-1} - C_k \]

The answer is the maximum of these two patterns.

Algorithm

1. Sort the input array \(C\) in ascending order.
2. If \(N\) is even, calculate the total contrast using the formula for even \(N\).
3. If \(N\) is odd, calculate both Pattern 1 and Pattern 2 for odd \(N\) and take the larger value.
4. Output the calculated maximum value.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the array takes \(O(N \log N)\) time.
  • The subsequent calculation of partial sums can be done in \(O(N)\) time, so the overall bottleneck is the sorting step.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input array \(C\).

Implementation Points

• Preventing Overflow: Since \(N\) is up to \(10^6\) and each \(C_i\) is up to \(10^9\), the total contrast can reach around \(10^{15}\). Since this will overflow a 32-bit integer, make sure to use a 64-bit integer type (such as long long in C++) for the calculations.

• Fast I/O: Since \(N\) is large, using cin.tie(NULL) and ios_base::sync_with_stdio(false) in C++ to speed up input/output will ensure the program easily runs within the time limit.

  Source Code

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> C(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }

    sort(C.begin(), C.end());

    long long ans = 0;
    if (N % 2 == 0) {
        int k = N / 2;
        long long sum_L = 0;
        for (int i = 0; i < k; ++i) sum_L += C[i];
        long long sum_R = 0;
        for (int i = k; i < N; ++i) sum_R += C[i];
        ans = 2 * sum_R - C[k] - 2 * sum_L + C[k - 1];
    } else {
        int k = N / 2;
        // パターン 1: 小さいグループが k 個、大きいグループが k+1 個
        long long sum_L1 = 0;
        for (int i = 0; i < k; ++i) sum_L1 += C[i];
        long long sum_R1_rest = 0;
        for (int i = k + 2; i < N; ++i) sum_R1_rest += C[i];
        long long ans1 = 2 * sum_R1_rest + C[k] + C[k + 1] - 2 * sum_L1;

        // パターン 2: 小さいグループが k+1 個、大きいグループが k 個
        long long sum_L2_rest = 0;
        for (int i = 0; i < k - 1; ++i) sum_L2_rest += C[i];
        long long sum_R2 = 0;
        for (int i = k + 1; i < N; ++i) sum_R2 += C[i];
        long long ans2 = 2 * sum_R2 - 2 * sum_L2_rest - C[k - 1] - C[k];

        ans = max(ans1, ans2);
    }

    cout << ans << "\n";

    return 0;
}

---

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