Overview

Given the heights of \(N\) students, find the sum of absolute differences in height for all distinct pairs.

Analysis

A naive approach would be to compute \(|A_i - A_j|\) for all pairs \((i, j)\) (\(i < j\)) and sum them up. However, this approach has a time complexity of \(O(N^2)\), and since \(N\) can be up to \(2 \times 10^5\), it will not fit within the time limit (TLE).

Therefore, we need to think of an efficient computation method. To quickly compute the sum of height differences, it is effective to consider how much each element contributes to the final answer.

Here, we consider sorting the heights in ascending order. By sorting, we can collectively handle “the differences with elements larger than a given element.”

For example, suppose the heights sorted in ascending order are \(A_0, A_1, ..., A_{N-1}\). Then, for a given element \(A_i\):

• There are \(i\) elements to the left (with smaller indices), and all of them have heights less than or equal to \(A_i\).
• There are \(N - 1 - i\) elements to the right (with larger indices), and all of them have heights greater than or equal to \(A_i\).

Therefore, the contribution of \(A_i\) to the differences with other elements is: - Sum of differences with left elements: \(A_i\) is subtracted \(i\) times → total contribution of \(+A_i \cdot i\) - Sum of differences with right elements: \(A_i\) is subtracted \(N - 1 - i\) times → total contribution of \(-A_i \cdot (N - 1 - i)\)

Simplifying this, the contribution of element \(A_i\) is:

\[ A_i \cdot i - A_i \cdot (N - 1 - i) = A_i \cdot (2i - N + 1) \]

Using this formula, we can compute each element’s contribution to the answer in \(O(1)\), reducing the overall time complexity to \(O(N)\).

Algorithm

1. Read the input and sort the list of heights in ascending order.
2. For each element \(A_i\), compute its contribution to the answer \(A_i \cdot (2i - N + 1)\) and add it to the total.
3. Output the total.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Make sure to sort the heights.

• Pay attention to the sign and coefficient in the formula \(A_i \cdot (2i - N + 1)\).

• In Python, simply using sort() sorts in ascending order.

  Source Code

n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = 0
for i in range(n):
    ans += a[i] * (2 * i - n + 1)

print(ans)

This editorial was generated by qwen3-coder-480b.