Overview

This problem asks you to find the number of pairs of two different students whose combined scores are at least the threshold value \(K\).

Analysis

A naive approach would be to examine all pairs \((i, j)\) (\(i < j\)) and check whether \(A_i + A_j \geq K\). However, the time complexity of this approach is \(O(N^2)\), and given the constraint that \(N\) can be up to \(2 \times 10^5\), this would require approximately \(2 \times 10^{10}\) operations, which would not fit within the time limit.

Therefore, we need to consider a more efficient method. By sorting the array, we can use techniques that efficiently count pairs satisfying a specific condition. After sorting, we can use the two-pointer technique or binary search to efficiently determine the number of pairs that satisfy the condition.

Algorithm

1. Sort array \(A\).
2. Use the two-pointer technique to count the number of pairs satisfying the condition.
   • Set the left pointer left to the beginning and the right pointer right to the end.
   • If A[left] + A[right] >= K:
     • In this case, pairing right with any element from left to right-1 satisfies the condition (since the sum will be at least A[left] + A[right]). Therefore, (right - left) pairs satisfy the condition.
     • Then, decrement right to examine combinations with the next largest value.
   • If the condition is not satisfied:
     • Increment left to increase the sum.
3. Repeat this operation while left < right.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\), and the two-pointer processing takes \(O(N)\).
• Space complexity: \(O(N)\)
  • Memory is needed to store array \(A\).

Implementation Notes

• Sorting enables the application of the two-pointer technique.

• Pay attention to how pairs are counted when the condition is satisfied. right - left counts all pairs of elements from left onward that can be paired with the current right.

• It is important to update the pointers correctly. When the condition is satisfied, decrease right; when it is not, increase left.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    A.sort()
    
    count = 0
    left = 0
    right = n - 1
    
    while left < right:
        if A[left] + A[right] >= K:
            count += (right - left)
            right -= 1
        else:
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.