Overview

This problem asks you to find the absolute difference in times for every pair of athletes belonging to the same school, and output the total sum.

Analysis

In this problem, we need to find the sum of absolute differences in times for all pairs of athletes belonging to the same school.

Naive Approach and Its Issues

The first idea that comes to mind is to compute the absolute difference for every pair. That is, if a school has \(k\) athletes, we compute \(|L_i - L_j|\) for each of the \({}_kC_2 = \frac{k(k-1)}{2}\) pairs. However, in the worst case where all \(N\) athletes belong to the same school, this requires up to \(O(N^2)\) comparisons, resulting in an overall time complexity of \(O(N^2)\). Since the constraint is \(N \leq 1000\), this might be fast enough in some languages, but it may not pass in time when implemented in Python, for example.

Key Insight for an Efficient Approach

We consider whether we can compute this efficiently by sorting the times. Let the times sorted in ascending order be \([t_0, t_1, ..., t_{k-1}]\).

The key observation is how much each element \(t_i\) contributes to the total sum when paired with other elements.

• For elements before \(t_i\) (\(t_0\) through \(t_{i-1}\)): since \(t_i > t_j\ (j < i)\), the difference is \(t_i - t_j\)
• For elements after \(t_i\) (\(t_{i+1}\) through \(t_{k-1}\)): since \(t_i < t_j\ (j > i)\), the difference is \(t_j - t_i\)

Therefore, the total contribution of \(t_i\) is: $\( \sum_{j=0}^{i-1}(t_i - t_j) + \sum_{j=i+1}^{k-1}(t_j - t_i) = t_i \cdot i - \sum_{j=0}^{i-1}t_j + \sum_{j=i+1}^{k-1}t_j - t_i \cdot (k-1-i) \)$

Simplifying this: $\( t_i \cdot (2i - k + 1) + \left(\sum_{j=i+1}^{k-1}t_j - \sum_{j=0}^{i-1}t_j\right) \)$

However, using prefix sums, we can more simply determine the coefficient \(2i - k + 1\) for each \(t_i\) directly.

In other words, after sorting each school’s time list, we can compute the total in linear time by using the coefficient \((2i - k + 1)\) for each element.

This means the computation for each school takes \(O(k)\), and the overall processing is \(O(N)\).

Algorithm

1. Classify each athlete’s time into lists by school using defaultdict.
2. Sort the times for each school.
3. For each school’s time list, compute as follows:
   • Let the sorted time list be \([t_0, t_1, ..., t_{k-1}]\).
   • For each \(i\), add \(t_i \cdot (2i - k + 1)\) to the total sum.
4. Output the final total.

Complexity

• Time complexity: \(O(N \log N)\) (due to the need to sort each school’s times)
• Space complexity: \(O(N)\) (for storing athlete information)

Implementation Notes

• Using defaultdict(list) allows efficient grouping of times by school.
• The times for each school must be sorted before performing the computation.
• Instead of directly computing the sum of absolute differences, we achieve efficiency by using sorting and coefficient calculation.

## Source Code

```python
from collections import defaultdict

N = int(input())
schools = defaultdict(list)

for _ in range(N):
    C, L = map(int, input().split())
    schools[C].append(L)

total_sum = 0

for times in schools.values():
    times.sort()
    k = len(times)
    for i in range(k):
        total_sum += times[i] * (2 * i - k + 1)

print(total_sum)

---

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