Overview

This is a problem of selecting 2 integers from \(N\) integers and counting the number of pairs whose absolute difference is exactly \(K\).

Analysis

Key Insight

For the absolute difference to be \(K\), two numbers \(a\) and \(b\) must satisfy \(|a - b| = K\). This means one of the following two cases: - \(b = a + K\) (\(b\) is \(K\) larger than \(a\)) - \(b = a - K\) (\(b\) is \(K\) smaller than \(a\))

Problem with the Naive Approach

Enumerating all pairs and checking their differences has a time complexity of \(O(N^2)\). When \(N\) is at most \(2 \times 10^5\), this requires approximately \(4 \times 10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Solution

For each element \(a\), we need to quickly check whether the value \(a + K\) exists in the sequence. Using a hash table (Counter or dict in Python), we can perform existence checks in \(O(1)\).

Important Point: When considering the pair of \(a\) and \(a + K\), the pair of \(a + K\) and \(a\) is the same thing. Therefore, by only looking for “elements that are \(K\) larger than itself” for each element, we prevent counting the same pair twice.

Concrete Example

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

Counting the occurrences of each element: - \(1\): 1 time - \(3\): 2 times - \(5\): 1 time - \(7\): 1 time

Finding pairs with difference \(2\): - For \(1\), \(1 + 2 = 3\) exists → \(1 \times 2 = 2\) pairs - For \(3\), \(3 + 2 = 5\) exists → \(2 \times 1 = 2\) pairs - For \(5\), \(5 + 2 = 7\) exists → \(1 \times 1 = 1\) pair - For \(7\), \(7 + 2 = 9\) does not exist → \(0\) pairs

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

Algorithm

1. Count the occurrences of each element in the sequence using Counter
2. For each unique value \(a\) in the Counter:
   • Check if \(a + K\) exists in the Counter
   • If it exists, add (count of \(a\)) × (count of \(a + K\)) to the pair count
3. Output the total pair count

Complexity

• Time Complexity: \(O(N)\)
  • Building the Counter takes \(O(N)\)
  • The loop over each unique value runs at most \(N\) times, with each iteration being \(O(1)\)
• Space Complexity: \(O(N)\)
  • The Counter may have up to \(N\) keys

Implementation Notes

• Using Counter allows for concise management of the occurrence count of each value
• By only searching for \(a + K\) instead of \(a - K\), we prevent duplicate counting of pairs
• When the same value appears multiple times (e.g., \(3\) appears twice), we take the product of occurrence counts to correctly count each combination

Source Code

from collections import Counter

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    result = 0
    
    for a in count:
        # Check if a + K exists
        if a + K in count:
            result += count[a] * count[a + K]
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.