Overview

Given \(N\) socks, form \(M\) pairs to minimize the sum of absolute differences in color intensity for each pair. After sorting, this reduces to “selecting \(M\) non-adjacent elements from the adjacent difference array to minimize their sum,” which is efficiently solved using a regret-based greedy algorithm.

Analysis

Observation 1: After sorting, optimal pairs consist of adjacent elements

When socks are sorted by color intensity \(S\), optimal pairing always pairs socks that are adjacent after sorting. Intuitively, when \(a \leq b \leq c\), we have \(|c - a| \geq |b - a|\) and \(|c - a| \geq |c - b|\), so pairing closer elements is always better than pairing distant ones.

Observation 2: Reduction to a difference array problem

Define the differences after sorting as \(d[i] = S[i+1] - S[i]\) (\(i = 0, 1, \ldots, N-2\)). Pairing sock \(i\) with sock \(i+1\) costs \(d[i]\).

The key constraint here is that each sock can only be used once. For example, if \((S[0], S[1])\) is paired, then \(S[1]\) is already used, so \((S[1], S[2])\) cannot be paired. In other words, when selecting \(M\) indices from the difference array \(d\), no two adjacent indices may be selected simultaneously.

Observation 3: Naive DP is insufficient

A DP solution would be \(O(NM)\), which is too slow when \(N, M\) can be up to \(2 \times 10^5\).

Algorithm

We use a Regret-based Greedy approach.

This is a standard technique for the problem of “selecting \(M\) non-adjacent elements to minimize their sum.”

Basic Idea

1. Insert all \(d[i]\) into a min-heap
2. Extract the minimum \(d[i]\) and add it to the answer
3. Since \(d[i]\) was selected, adjacent elements \(d[i-1]\) and \(d[i+1]\) can no longer be selected → remove them
4. Insert a regret element with value \(d[i-1] + d[i+1] - d[i]\) at the position of \(d[i]\)

Why insert a regret element?

Later, it might turn out that “not selecting \(d[i]\), but instead selecting both \(d[i-1]\) and \(d[i+1]\) would have been better.” Selecting the regret element \(d[i-1] + d[i+1] - d[i]\) is effectively equivalent to undoing the selection of \(d[i]\) and selecting \(d[i-1]\) and \(d[i+1]\) instead (since the cost change is \(d[i-1] + d[i+1] - d[i]\)).

Concrete Example

For \(S = [1, 3, 4, 9, 10]\), \(M = 2\): - \(d = [2, 1, 5, 1]\) - Minimum is \(d[1] = 1\). Answer \(= 1\). Regret element: \(d[0] + d[2] - d[1] = 2 + 5 - 1 = 6\) is inserted. Note that \(d[3] = 1\) is not removed (the neighbors are \(d[0]\) and \(d[2]\)). - Remaining valid elements: value 6 at position 1, \(d[3] = 1\). Minimum is \(d[3] = 1\). Answer \(= 1 + 1 = 2\).

Result: Pairing \((3,4)\) and \((9,10)\) gives a total discomfort of \(2\).

Data Structures

• Doubly linked list: Skip deleted elements and reference left/right neighbors in \(O(1)\)
• Min-heap: Efficiently retrieve the current minimum (skip invalid elements using lazy deletion)

Complexity

• Time complexity: \(O(N \log N)\) (sorting + \(O(N)\) heap operations each taking \(O(\log N)\))
• Space complexity: \(O(N)\)

Implementation Details

• Sentinel handling in the linked list: When there is no neighbor at the left or right boundary, treat the value as \(\infty\). This ensures the regret element is correctly computed at boundaries (if one neighbor doesn’t exist, regret in that direction is effectively impossible).

• Lazy deletion: When extracting an element from the heap, check whether it has been marked as deleted with the removed flag or whether its value has been updated. If invalid, skip it.

• Value updates: The regret element overwrites the same index position with a new value and is re-added to the heap, reusing the position in the linked list.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    S = [int(input_data[i + 2]) for i in range(N)]
    
    S.sort()
    
    # After sorting, optimal pairs are always adjacent elements.
    # We need to choose M non-overlapping adjacent pairs from N sorted elements
    # to minimize total difference.
    
    # Let d[i] = S[i+1] - S[i] for i = 0..N-2
    # We need to select M non-overlapping intervals of length 2 covering adjacent pairs.
    # This is equivalent to selecting M indices from d[0..N-2] such that no two selected
    # indices are consecutive, and minimizing the sum.
    
    # Wait, that's not quite right. If we pair (S[0],S[1]), that uses d[0].
    # If we pair (S[1],S[2]), that uses d[1]. These overlap (share S[1]).
    # If we pair (S[0],S[1]) and (S[2],S[3]), indices 0 and 2 in d - they are NOT consecutive,
    # so the constraint is: no two chosen indices in d are consecutive.
    
    # So: choose M indices from {0, 1, ..., N-2} with no two consecutive, minimize sum of d[chosen].
    
    # K = N-1 differences, choose M with no two adjacent.
    # This is feasible when M <= ceil(K/2) = ceil((N-1)/2).
    # Since M <= N/2, this is always feasible.
    
    # For small cases or when 2M = N or close, DP works.
    # But N can be 2*10^5, and we need efficient solution.
    
    # Classic approach: greedy with a linked list and priority queue (similar to the 
    # "choose M non-adjacent elements to minimize sum" problem).
    
    # Algorithm: Use a min-heap. When we pick element d[i], we must exclude d[i-1] and d[i+1].
    # But we add a "replacement" element d[i-1] + d[i+1] - d[i] which represents the option
    # of un-picking d[i] and instead picking d[i-1] and d[i+1].
    
    import heapq
    
    K = N - 1
    d = [S[i + 1] - S[i] for i in range(K)]
    
    # Linked list
    left = list(range(-1, K - 1))   # left[i] = i-1
    right = list(range(1, K + 1))   # right[i] = i+1
    # Sentinel values
    INF = float('inf')
    
    val = d[:]
    removed = [False] * K
    
    heap = [(d[i], i) for i in range(K)]
    heapq.heapify(heap)
    
    ans = 0
    
    for _ in range(M):
        # Pop minimum not removed
        while heap:
            v, idx = heapq.heappop(heap)
            if not removed[idx] and val[idx] == v:
                break
        
        ans += v
        
        # Get neighbors
        l = left[idx]
        r = right[idx]
        
        # New replacement value
        lv = val[l] if (0 <= l < K) else INF
        rv = val[r] if (0 <= r < K) else INF
        new_val = lv + rv - v
        
        val[idx] = new_val
        heapq.heappush(heap, (new_val, idx))
        
        # Remove left neighbor
        if 0 <= l < K:
            removed[l] = True
            ll = left[l]
            left[idx] = ll
            if 0 <= ll < K:
                right[ll] = idx
        
        # Remove right neighbor
        if 0 <= r < K:
            removed[r] = True
            rr = right[r]
            right[idx] = rr
            if 0 <= rr < K:
                left[rr] = idx
    
    print(ans)

solve()

---

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