Overview

This is a problem of finding the number of students for whom there exists another student whose score differs by exactly \(K\) in absolute value.

Analysis

For each student \(i\), we need to determine whether there exists another student \(j\) such that \(|A_i - A_j| = K\). Naively checking all pairs would require \(O(N^2)\) time complexity, which is too slow since \(N\) can be up to \(2 \times 10^5\).

A key observation is that for student \(i\) to satisfy the condition, there only needs to be at least one other student with a score of \(A_i + K\) or \(A_i - K\). However, when \(K = 0\), the case is special: there needs to be at least one other student with the same score as student \(i\).

Algorithm

1. First, count the frequency of each score using a hash map (dictionary).
2. For each student \(i\):
   • If \(K = 0\): Check whether there is another student with the same score (i.e., the frequency is at least 2)
   • If \(K > 0\): Check whether there exists a student with a score of \(A_i + K\) or \(A_i - K\)
3. Count the number of students satisfying the condition.

Complexity

• Time complexity: \(O(N)\)
  • Iterating through the score list and hash map operations are each \(O(N)\)
• Space complexity: \(O(N)\)
  • For storing \(N\) elements in the hash map

Implementation Notes

• Use a hash map (defaultdict) to efficiently manage the frequency of each score

• The cases \(K = 0\) and \(K > 0\) need to be handled separately

• Even when \(K\) is very large (on the order of \(10^9\)), hash map lookups are \(O(1)\), so there is no issue

• While \(A_i \pm K\) could potentially be negative, since scores are non-negative integers, if \(A_i - K\) is negative, it is automatically determined to not exist (looking up a non-existent key in a hash map does not cause an error)

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    if n == 0:
        print(0)
        return
        
    from collections import defaultdict
    count_map = defaultdict(int)
    for a in A:
        count_map[a] += 1
        
    ans = 0
    for a in A:
        if K == 0:
            if count_map[a] >= 2:
                ans += 1
        else:
            if count_map[a + K] > 0 or count_map[a - K] > 0:
                ans += 1
                
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.