Overview

Among all pairs of players participating in the same sport, we count the number of pairs where the players belong to different teams. This is computed by subtracting the number of same-team pairs from the total number of pairs for each sport.

Analysis

A match can take place when two players have the “same sport number” and “different team numbers.”

Naively checking all \(\frac{N(N-1)}{2}\) pairs would result in up to about \(2\times 10^{10}\) pairs since \(N \le 2\times 10^5\), which is far too slow (TLE).

Instead, we use a smarter counting approach. If there are \(k\) players participating in a sport \(p\), the total number of pairs within that sport is \(k \choose 2\). However, this includes “same-team” pairs (which cannot be valid matches).

For example, if in sport \(p\), the number of players belonging to team \(q\) is \(c_{p,q}\), then the number of (invalid) pairs within that team is \({c_{p,q} \choose 2}\). Therefore, the number of valid match pairs in sport \(p\) is: $\( {k \choose 2} - \sum_q {c_{p,q} \choose 2} \)$

Summing this over all sports gives the answer. In other words: - First, count the “number of players per sport” - Next, count the “number of players per (sport, team) pair” - Add \(\sum_p {k_p \choose 2}\) and subtract \(\sum_{p,q} {c_{p,q} \choose 2}\)

Algorithm

1. Use associative arrays (dictionaries) to count the following:
   • sport_cnt[p] = number of participants in sport \(p\), i.e., \(k_p\)
   • sport_team_cnt[(p,q)] = number of players in sport \(p\) and team \(q\), i.e., \(c_{p,q}\)
2. Initialize ans = 0, then for all sports add ans += k_p (k_p-1)/2 (total number of pairs within each sport).
3. For all \((p,q)\), subtract ans -= c_{p,q} (c_{p,q}-1)/2 (removing same-team pairs, which are invalid matches).
4. Output ans.

Complexity

• Time complexity: \(O(N)\) (scan the input once to count, then sum over the dictionary values)
• Space complexity: \(O(N)\) (in the worst case, the number of distinct sports or (sport, team) combinations is on the order of \(N\))

Implementation Notes

• The combination count is \({x \choose 2} = \frac{x(x-1)}{2}\), which can be written as x*(x-1)//2 using integer arithmetic.

• Since \(N\) is large, in Python it is faster to read input all at once using sys.stdin.buffer.read().

• Using defaultdict(int) for dictionaries makes counting concise.

  Source Code

import sys
from collections import defaultdict

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))

    sport_cnt = defaultdict(int)
    sport_team_cnt = defaultdict(int)

    for _ in range(n):
        p = int(next(it))
        q = int(next(it))
        sport_cnt[p] += 1
        sport_team_cnt[(p, q)] += 1

    ans = 0
    for k in sport_cnt.values():
        ans += k * (k - 1) // 2

    for c in sport_team_cnt.values():
        ans -= c * (c - 1) // 2

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.