Overview

Given \(N\) students, we need to find the number of students for whom there exists at least one other student whose score differs by exactly \(K\) in absolute value.

Analysis

Naive Approach and Its Issues

The simplest method is to check all pairs \((i, j)\) of students to see if \(|A_i - A_j| = K\). However, the number of pairs is \(\frac{N(N-1)}{2}\), and when \(N\) is up to \(2 \times 10^5\), this requires about \(2 \times 10^{10}\) operations, resulting in TLE (Time Limit Exceeded).

Key Insight

The condition \(|A_i - A_j| = K\) can be rephrased as:

\[A_j = A_i + K \quad \text{or} \quad A_j = A_i - K\]

In other words, for a student \(i\) with score \(A_i\), we just need to check whether another student with score \(A_i + K\) or \(A_i - K\) exists.

By managing the frequency of each score using a hash map (dictionary), we can determine this in \(O(1)\) per student.

Special Case When \(K = 0\)

When \(K = 0\), we need to check whether there exists \(j \neq i\) such that \(A_j = A_i\). In other words, the key point is whether there are two or more students with the same score. If a score appears only once, the condition is not satisfied.

Algorithm

1. Count the frequency of each score using a Counter (hash map).
2. When \(K = 0\): For scores with a frequency of \(2\) or more, sum up all their frequencies.
3. When \(K \neq 0\): For each score \(v\), check whether \(v + K\) or \(v - K\) exists in the Counter. If so, all students with score \(v\) satisfy the condition, so add their frequency to the total.

Concrete Example

For \(N = 5\), \(K = 2\), \(A = [3, 1, 5, 3, 7]\):

• Frequencies: \(\{3: 2, 1: 1, 5: 1, 7: 1\}\)
• Score \(3\): \(3+2=5\) exists → condition satisfied (2 students)
• Score \(1\): \(1+2=3\) exists → condition satisfied (1 student)
• Score \(5\): \(5-2=3\) exists → condition satisfied (1 student)
• Score \(7\): \(7-2=5\) exists → condition satisfied (1 student)
• Answer: \(2 + 1 + 1 + 1 = 5\) students

Complexity

• Time complexity: \(O(N)\) (\(O(N)\) to build the Counter, \(O(1)\) per distinct score for the check × number of distinct scores)
• Space complexity: \(O(N)\) (required to store the Counter)

Implementation Notes

• Handle the \(K = 0\) case separately: When \(K = 0\), \(v + K = v - K = v\), so we are looking for “students with the same score as ourselves.” However, since there must be another person with the same score, we check whether the frequency is \(2\) or more.

• When \(K \neq 0\), check both \(v + K\) and \(v - K\): Because of the absolute value condition, we need to check both the positive and negative directions.

• The answer is the number of students, not the number of pairs: Even if a student has multiple valid pairs, that student is counted only once. By processing scores grouped by type using a Counter, this requirement is naturally satisfied.

  Source Code

import sys
from collections import Counter

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = list(map(int, input_data[2:2+N]))
    
    cnt = Counter(A)
    
    ans = 0
    if K == 0:
        for v, c in cnt.items():
            if c >= 2:
                ans += c
    else:
        for v, c in cnt.items():
            if (v + K) in cnt or (v - K) in cnt:
                ans += c
    
    print(ans)

main()

---

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