Overview

This problem asks us to efficiently count the number of pairs formed by choosing 2 different students from \(N\) students such that the sum of their scores is at least the threshold value \(K\).

Analysis

Naive Approach and Its Issues

The simplest method is to check whether \(A_i + A_j \geq K\) for every pair \((i, j)\) (\(i < j\)). However, the total number of pairs is \(\frac{N(N-1)}{2}\), which is approximately \(2 \times 10^{10}\) when \(N = 2 \times 10^5\). This will not fit within the time limit (TLE).

Key Insight

By rearranging the condition \(A_i + A_j \geq K\), we get \(A_j \geq K - A_i\). In other words, when we fix a student \(i\), the other student’s score just needs to be at least \(K - A_i\).

If we sort the array beforehand, we can efficiently find where the elements greater than or equal to \(K - A_i\) start using binary search. This allows us to determine the number of valid partners for each student \(i\) in \(O(\log N)\).

Concrete Example

Consider the case \(N = 4\), \(K = 7\), \(A = [2, 5, 3, 8]\).

After sorting: \(A = [2, 3, 5, 8]\)

• \(i = 0\) (\(A_i = 2\)): Number of \(j > 0\) satisfying \(A_j \geq 7 - 2 = 5\) → \(A[2]=5, A[3]=8\), so 2
• \(i = 1\) (\(A_i = 3\)): Number of \(j > 1\) satisfying \(A_j \geq 7 - 3 = 4\) → \(A[2]=5, A[3]=8\), so 2
• \(i = 2\) (\(A_i = 5\)): Number of \(j > 2\) satisfying \(A_j \geq 7 - 5 = 2\) → \(A[3]=8\), so 1
• \(i = 3\) (\(A_i = 8\)): No elements in the range \(j > 3\) → 0

Total: \(2 + 2 + 1 + 0 = 5\) pairs

Algorithm

1. Sort the array \(A\) in ascending order.
2. For each \(i = 0, 1, \ldots, N-1\), do the following:
   • Compute the threshold \(\text{threshold} = K - A_i\).
   • Use binary search (bisect_left) to find the smallest index in the interval \([i+1, N)\) of array \(A\) where \(A_j \geq \text{threshold}\). Let this index be \(\text{idx}\).
   • The number of pairs satisfying the condition is \(N - \text{idx}\), so add this to the answer.
3. Output the final total.

bisect_left(A, threshold, i+1, N) restricts the search range to indices \(i+1\) and beyond, which naturally satisfies the condition \(i < j\) and prevents counting the same pair twice.

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, plus \(O(\log N)\) × \(N\) times for binary search on each element)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• Specifying the search range: By using the 3rd and 4th arguments of bisect_left to restrict the search range from i+1 to N, we prevent pairing a student with themselves and avoid duplicate counting.

• Score values up to \(10^9\) with sums up to \(2 \times 10^9\): Python handles arbitrary-precision integers, so there is no concern about overflow. However, in languages like C++, you need to use long long.

• Answer type: The number of pairs can be as large as \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\), so note that 32-bit integers are insufficient (this is not an issue in Python).

  Source Code

import bisect

def main():
    import sys
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    A.sort()
    
    count = 0
    for i in range(N):
        # A[i] + A[j] >= K => A[j] >= K - A[i]
        threshold = K - A[i]
        # Find the leftmost index j in A where A[j] >= threshold, but j > i
        idx = bisect.bisect_left(A, threshold, i + 1, N)
        count += N - idx
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.