Overview

This problem asks for the maximum number of pairs that can be formed from \(N\) socks, where each pair must have a color intensity difference of at most \(K\).

Analysis

Key Insight

First, the condition for pairing socks is “the difference in color intensity is at most \(K\)”. Since this is the absolute value of the difference, pairing values that are close to each other becomes important.

Problems with the Naive Approach

If we try to examine all possible pairs of socks, the number of ways to choose 2 socks from \(N\) is \(\binom{N}{2} = \frac{N(N-1)}{2}\). Furthermore, we would need to optimize which pairs to select, making the computational complexity enormous.

Key to the Solution: Sorting + Greedy

When we sort the socks by color intensity, the socks that can potentially be paired are limited to “socks that are close to each other”.

Example: When \(K = 2\) and the sock color intensities are \([1, 3, 5, 6, 8]\): - Difference between \(1\) and \(3\) is \(2\) → Can be paired - Difference between \(5\) and \(6\) is \(1\) → Can be paired - \(8\) is left over - Result: 2 pairs

Why is Greedily Pairing Adjacent Socks Optimal?

After sorting, the optimal strategy is to look from left to right and pair adjacent socks whenever possible.

Reason: Suppose for some sock \(A[i]\), instead of choosing \(A[i+1]\) as its partner, we choose the more distant \(A[i+2]\). Then \(A[i+1]\) would be left over, and \(A[i+1]\) might only be able to pair with \(A[i]\) or \(A[i+2]\). By pairing items as close as possible, we leave more options available for later choices.

Algorithm

1. Sort the array \(A\) of sock color intensities in ascending order
2. Start from index \(i = 0\) and process from left to right
3. If \(A[i+1] - A[i] \leq K\), pair the \(i\)-th and \((i+1)\)-th socks, and increment \(i\) by \(2\)
4. Otherwise, skip the \(i\)-th sock and increment \(i\) by \(1\)
5. Output the number of pairs created

Concrete Example: \(N=5\), \(K=2\), \(A=[3, 1, 6, 5, 8]\)

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

\(i\)	Comparison	Difference	Decision	Operation	Pair Count
0	\(A[1] - A[0] = 3 - 1\)	2	\(\leq K\)	Pair formed, \(i \to 2\)	1
2	\(A[3] - A[2] = 6 - 5\)	1	\(\leq K\)	Pair formed, \(i \to 4\)	2
4	Loop ends at \(i = N-1\)

Answer: 2

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck; the greedy loop is \(O(N)\))
• Space complexity: \(O(N)\) (for storing array \(A\))

Implementation Notes

• After sorting, we only need to look at differences between adjacent elements, so there’s no need to take the absolute value when computing A[i+1] - A[i] (sorting guarantees \(A[i+1] \geq A[i]\))
• Pay attention to the different increments: i += 2 when a pair is formed, i += 1 when not
• The termination condition while i < N - 1 ensures that if only one sock remains at the end, the loop exits automatically

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sort and solve using greedy method
    A.sort()
    
    # Greedy: From left to right, pair adjacent socks if possible
    # Why this is optimal: After sorting, pairing items as close as possible
    # leaves more options for later choices
    
    pairs = 0
    i = 0
    while i < N - 1:
        if A[i + 1] - A[i] <= K:
            pairs += 1
            i += 2  # Both socks are now used
        else:
            i += 1  # Look for a potential pair for the current sock later
    
    print(pairs)

solve()

---

This editorial was generated by claude4.5opus.