Overview

This problem asks us to efficiently find the sum of height differences (absolute values) for all pairs when selecting 2 people from \(N\) students.

Analysis

Naive Approach

The simplest method is to calculate \(|A_i - A_j|\) for all pairs \((i, j)\) (\(i < j\)) and sum them up.

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += abs(A[i] - A[j])

However, the number of pairs is \(\frac{N(N-1)}{2}\), and when \(N = 2 \times 10^5\), this requires approximately \(2 \times 10^{10}\) calculations. This would result in TLE (Time Limit Exceeded).

Key Insight: Utilize Sorting

By sorting the array, we can remove the absolute value.

If we denote the sorted array as \(A_0 \leq A_1 \leq \ldots \leq A_{N-1}\), then when \(i < j\), we always have \(A_i \leq A_j\), so: $\(|A_i - A_j| = A_j - A_i\)$

Further Optimization: Consider Each Element’s Contribution

After sorting, let’s think about how much each element \(A_i\) contributes to the total sum.

\(A_i\): - When paired with the \(i\) elements before it (smaller), it is subtracted from (contributes as \(+A_i\) a total of \(i\) times) - When paired with the \(N-1-i\) elements after it (larger), it is the one subtracting (contributes as \(-A_i\) a total of \(N-1-i\) times)

However, let’s think about this more simply.

Understanding Through a Concrete Example

Sorting \(A = [3, 1, 4]\) gives us \([1, 3, 4]\).

When \(i = 2\) (value is \(4\)), the sum of differences with preceding elements \([1, 3]\) is: $\((4 - 1) + (4 - 3) = 2 \times 4 - (1 + 3) = 8 - 4 = 4\)$

In other words, for the \(i\)-th element: $\(i \times A_i - (A_0 + A_1 + \ldots + A_{i-1})\)$

We can efficiently calculate this using prefix sums.

Algorithm

1. Sort array \(A\)
2. Initialize prefix sum prefix_sum to \(0\)
3. For each element \(A_i\) (\(i = 0, 1, \ldots, N-1\)):
   • Add the sum of differences with elements before \(A_i\) \(= i \times A_i - \text{prefix\_sum}\) to total
   • Add \(A_i\) to prefix_sum
4. Output total

Calculation with a Concrete Example

\(A = [3, 1, 4]\) → After sorting: \([1, 3, 4]\)

\(i\)	\(A_i\)	\(i \times A_i - \text{prefix\_sum}\)	total	prefix_sum
0	1	\(0 \times 1 - 0 = 0\)	0	1
1	3	\(1 \times 3 - 1 = 2\)	2	4
2	4	\(2 \times 4 - 4 = 4\)	6	8

Answer: \(6\) (Verification: \(|3-1| + |4-1| + |4-3| = 2 + 3 + 1 = 6\) ✓)

Complexity

• Time Complexity: \(O(N \log N)\) (sorting is the bottleneck, subsequent processing is \(O(N)\))
• Space Complexity: \(O(N)\) (for storing the array)

Implementation Notes

• Since the maximum value of \(A_i\) is \(10^9\) and the maximum value of \(N\) is \(2 \times 10^5\), the total sum can be up to approximately \(10^{14}\). In Python, there’s no need to worry about integer overflow, but in C++ and similar languages, you need to use the long long type.
• Instead of maintaining the prefix sum in a separate array, we save memory by managing it with a single variable.

Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Sort the array
    A.sort()
    
    # Calculate prefix sum
    # After sorting, efficiently calculate the sum of differences between each element A[i] and smaller elements
    # For pairs of A[i] and A[j] (j < i), find the sum of A[i] - A[j]
    # = i * A[i] - (A[0] + A[1] + ... + A[i-1])
    # = i * A[i] - prefix_sum[i]
    
    total = 0
    prefix_sum = 0
    
    for i in range(N):
        # Sum of differences with elements before A[i]
        # A[i] is larger than i elements (since array is sorted)
        total += i * A[i] - prefix_sum
        prefix_sum += A[i]
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.