Overview

This problem asks you to calculate the absolute difference in goal times for all pairs of athletes belonging to the same school, and find the total sum.

Analysis

Naive Approach

The simplest method is to calculate \(|L_i - L_j|\) for all pairs \((i, j)\) of athletes from the same school.

# Naive approach (conceptual)
for i in range(n):
    for j in range(i+1, n):
        total += abs(times[i] - times[j])

With this method, if there are \(n\) people in one school, the number of pairs is \(\frac{n(n-1)}{2}\), resulting in \(O(n^2)\) time complexity. While this is not a problem with the constraint \(N \leq 1000\), it’s good to learn a more efficient method.

Key Insight: Using Sorting

When we sort the times, we can remove the absolute value.

For example, if the times are \([2, 5, 9]\) (already sorted): - \(5\) is greater than \(2\), so \(|5-2| = 5-2\) - \(9\) is greater than \(2, 5\), so \(|9-2| = 9-2\), \(|9-5| = 9-5\)

In other words, in a sorted array, \(times[i]\) contributes as the “positive side” in differences with all \(i\) elements smaller than itself.

Mathematical Formulation

In a sorted array \(times[0], times[1], \ldots, times[n-1]\), the total contribution of differences from \(times[i]\) is:

\[\sum_{j=0}^{i-1} (times[i] - times[j]) = times[i] \times i - \sum_{j=0}^{i-1} times[j]\]

The term \(\sum_{j=0}^{i-1} times[j]\) on the right side can be precomputed as a prefix sum.

Concrete Example

For times \([2, 5, 9]\): - \(i=0\): contribution = \(2 \times 0 - 0 = 0\) - \(i=1\): contribution = \(5 \times 1 - 2 = 3\) (corresponds to \(|5-2|=3\)) - \(i=2\): contribution = \(9 \times 2 - (2+5) = 18 - 7 = 11\) (corresponds to \(|9-2|+|9-5|=7+4=11\))

Total = \(0 + 3 + 11 = 14\) ✓

Algorithm

1. Group by school: Store each athlete’s time in a list organized by their school
2. Process each school:
   • Sort the times
   • Using prefix sums, calculate the contribution of each element’s differences with smaller elements
   • Add \(times[i] \times i - prefix\_sum\) to the total
   • Update \(prefix\_sum\)
3. Output the total sum across all schools

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting by school takes \(O(N \log N)\) (across all athletes combined)
  • Calculation using prefix sums takes \(O(N)\)
• Space complexity: \(O(N)\)
  • Used for storing time lists by school

Implementation Notes

• Using defaultdict(list) makes it easy to group athletes’ times by school number as the key
• The prefix sum prefix_sum should be managed as an integer type and updated within the loop
• Processing after sorting eliminates the need to consider absolute values, simplifying the calculation

Source Code

from collections import defaultdict

def solve():
    N = int(input())
    
    # Store athletes' times by school
    school_times = defaultdict(list)
    
    for _ in range(N):
        C, L = map(int, input().split())
        school_times[C].append(L)
    
    total = 0
    
    # Calculate for each school
    for school, times in school_times.items():
        # Sort times
        times.sort()
        n = len(times)
        
        # Efficient calculation with sorted array
        # The i-th element contributes to differences with i smaller elements and (n-1-i) larger elements
        # Total = Σ times[i] * i - Σ times[j] (j < i) for all i
        #       = Σ times[i] * i - prefix_sum[i]
        
        prefix_sum = 0
        for i in range(n):
            # Sum of differences with elements smaller than times[i]
            total += times[i] * i - prefix_sum
            prefix_sum += times[i]
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.