Overview

Given \(N\) socks, find the maximum number of pairs that can be formed such that the difference in color intensity within each pair is at most \(K\).

Analysis

The key point of this problem is to think about “which socks should be paired together optimally”.

First, it seems intuitive to pair socks with similar color intensities. For example, consider the case where the color intensities are \([10, 12, 13, 20]\) and \(K=5\). - If we try to pair \(10\) and \(20\), the difference is \(10\), so they cannot be paired. - However, looking at values that are close together, such as \(10\) and \(12\), or \(12\) and \(13\), the differences are at most \(K\).

In this way, when the color intensities are sorted in ascending order, adjacent socks have the smallest differences, making them the most likely candidates for pairing.

Greedy Approach

With the socks sorted as \(A_1, A_2, \dots, A_N\), we examine them in order from left to right. 1. If the difference between \(A_1\) and \(A_2\) is at most \(K\), pair these two socks. - This is because there is no benefit to pairing \(A_1\) with any other sock (\(A_3\) or later). If there exists a sock that can be paired with \(A_1\), pairing it with \(A_2\) (the closest in value) is the best choice, as it leaves the other socks free to form their own pairs. 2. If the difference between \(A_1\) and \(A_2\) is greater than \(K\), then \(A_1\) cannot be paired with any sock. - This is because all socks from \(A_2\) onward have values at least as large as \(A_2\), so the difference would only increase further. Therefore, we give up on \(A_1\) and consider pairing from \(A_2\) onward.

This greedy approach of “processing from one end, pairing immediately whenever possible” allows us to find the maximum number of pairs.

Algorithm

1. Sort the color intensities \(A\) of the socks in ascending order.
2. Starting from the leftmost sock, check the difference with the adjacent sock in sequence.
3. Begin with index \(i = 0\) and repeat the following process:
   • If \(A_{i+1} - A_i \le K\):
     • One pair can be formed, so increment the count by \(+1\).
     • Since the used socks can no longer be used, move to the \((i+2)\)-th sock next.
   • If \(A_{i+1} - A_i > K\):
     • \(A_i\) cannot be paired with anyone, so move to the \((i+1)\)-th sock next.
4. Output the final count.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the socks takes \(O(N \log N)\). The subsequent traversal of the list is \(O(N)\), so overall the sorting complexity dominates.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input sock data.

Implementation Notes

• Since \(N\) can be as large as \(2 \times 10^5\), in Python it is safer to use fast input reading such as sys.stdin.read().split().

• The process of advancing the index by \(2\) when a pair is formed and by \(1\) when it is not can be written concisely using a while loop.

  Source Code

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # 靴下の色の濃さを昇順にソート
    a.sort()
    
    ans = 0
    i = 0
    # 隣り合う靴下を確認していく貪欲法
    while i < n - 1:
        # 差が K 以下であればペアにする
        if a[i+1] - a[i] <= k:
            ans += 1
            # ペアにしたので次の靴下は2つ先から確認
            i += 2
        else:
            # ペアにできなかったので次の靴下へ
            i += 1
            
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.