Overview

This problem requires calculating the “absolute differences of all pairs” of goal times among athletes belonging to the same school, and finding the total sum.

Analysis

1. Breaking Down the Problem

First, we do not need to consider athletes from different schools. By grouping athletes by school, performing calculations within each group, and then summing up all the results, we can obtain the answer.

2. Efficiently Calculating Absolute Differences of Pairs

If a school has \(k\) athletes’ times, naively computing \(|L_i - L_j|\) for all pairs \((i, j)\) takes \(O(k^2)\) time per school. Since the total number of people \(N\) is at most 1000, this approach (\(O(N^2)\) overall) is fast enough, but let’s consider a more efficient method.

If we sort the times in ascending order as \(t_0, t_1, \dots, t_{k-1}\), we can remove the absolute value signs. Since \(t_i \leq t_j\) always holds when \(i < j\), the desired sum becomes: $\(\sum_{0 \leq i < j < k} (t_j - t_i)\)$

In this expression, by focusing on the “number of times each \(t_i\) is added” and “number of times it is subtracted,” we can simplify as follows: - \(t_i\) contributes positively as \(t_i - t_{small}\) in pairs with smaller values (\(i\) of them). - \(t_i\) contributes negatively as \(t_{large} - t_i\) in pairs with larger values (\((k - 1) - i\) of them).

Therefore, the contribution of each \(t_i\) can be expressed as: $\((\text{number of elements before it} \times t_i) - (\text{number of elements after it} \times t_i)\)\( \)\(= i \times t_i - (k - 1 - i) \times t_i\)$

Using this, after sorting, we only need to examine each element once to compute the total for that school in \(O(k)\).

Algorithm

1. Grouping: Using a dictionary (associative array) or similar structure, store the data with school numbers as keys and lists of times as values.
2. Calculation for each school:
   • Sort each school’s list of times in ascending order.
   • Using the formula derived in the analysis above, compute the total sum of time differences within that school.
3. Aggregation: Sum up the results from all schools and output the answer.

Complexity

• Time Complexity: \(O(N \log N)\)

  • Reading data and grouping takes \(O(N)\).
  • Sorting per school takes \(O(N \log N)\) in total.
  • Calculation per school takes \(O(N)\) in total.
  • Overall, this is \(O(N \log N)\), which runs very quickly for the constraint \(N \leq 1000\).

• Space Complexity: \(O(N)\)

  • Memory is needed to store the times for each school.

Implementation Notes

• Using a dictionary: Since school numbers are not necessarily consecutive, using Python’s dict allows flexible grouping.

• Sorting: The key point is to sort the times for each school using the list’s sort() method or the sorted() function.

• Mathematical optimization: While a brute-force double loop searching all pairs can also produce a correct answer, using the \(O(k)\) formula introduced here allows you to handle problems with larger constraints as well.

  Source Code

import sys

def solve():
    # 入力を読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    # 学校ごとにタイムを格納する辞書
    schools = {}
    
    idx = 1
    for _ in range(n):
        c = int(input_data[idx])
        l = int(input_data[idx + 1])
        if c not in schools:
            schools[c] = []
        schools[c].append(l)
        idx += 2
    
    total_sum = 0
    # 各学校について計算を行う
    for school_id in schools:
        times = sorted(schools[school_id])
        k = len(times)
        # ソート済みのリストに対して、すべてのペアの絶対差の総和を計算する
        # 総和 = Σ ( (i * times[i]) - (k - 1 - i) * times[i] ) (iは0からk-1まで)
        school_sum = 0
        for i in range(k):
            school_sum += i * times[i] - (k - 1 - i) * times[i]
        total_sum += school_sum
        
    print(total_sum)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.