Overview

This problem asks you to sort socks by color intensity, then choose to pair or not pair adjacent socks, selecting exactly \(M\) pairs to minimize the total discomfort (sum of absolute differences).

Analysis

1. Sorting is the key first step

Since only the relative order of color intensities \(S_i\) matters, we sort \(S\) in ascending order: $\(S_0 \le S_1 \le \dots \le S_{N-1}\)$ From here on, we handle socks in this order.

2. In the optimal solution, “pairs are adjacent elements after sorting”

Intuitively, to minimize the absolute difference \(|S_i-S_j|\), we should pair values that are close together.

In fact, if we pair \(i<j\) after sorting and \(S_{i+1}\) between them is unused, replacing \((i,j)\) with \((i,i+1)\) gives a difference of: $\(S_{i+1}-S_i \le S_j-S_i\)$ which never worsens (and actually improves).
Also, if elements in between belong to other pairs, we can “untangle crossing pairs and re-pair closer elements” without increasing the total, ultimately reaching a form where “if used, adjacent elements are paired.”

As a result, the problem reduces to:

• Consider the adjacent differences after sorting: $\(w_i = S_{i+1}-S_i \quad (i=0,\dots,N-2)\)$
• Creating a pair \((S_i,S_{i+1})\) corresponds to selecting an “edge” with weight \(w_i\).
• Since the same sock cannot be used twice, adjacent edges \(w_i\) and \(w_{i+1}\) cannot be selected simultaneously (= no consecutive selections).
• Therefore, the problem becomes “from an array \(w\) of length \(N-1\), select exactly \(M\) non-adjacent elements to minimize their sum.”

3. Naive DP is \(O(NM)\) and too slow

A DP approach of “look from the front, decide to pair or not” gives: $\(dp[i][j] = \text{minimum cost of making } j \text{ pairs considering the first } i \text{ elements}\)\( The transitions work, but the complexity is \)O(NM)\(. With constraints \)N\le 2\times 10^5,\ M\le 10^5$, this is far too slow.

4. Handling “exactly \(M\) items” with penalties (Aliens trick / WQS binary search)

Instead of directly handling “select exactly \(M\) items,” we consider a problem where a fixed penalty \(\lambda\) is added for each selection:

• Each selection incurs cost \(w_i+\lambda\)
• Solve the minimization with “any number of selections allowed”

If \(\lambda\) is large, selecting becomes costly and the count decreases; if \(\lambda\) is small (negative), the count increases.
Using the property that “the optimal number of selections changes monotonically with \(\lambda\),” we binary search to adjust to around \(M\) items.

Algorithm

1. Preprocessing

1. Sort \(S\)
2. Compute \(w_i = S_{i+1}-S_i\) (length \(N-1\))

2. DP for a fixed \(\lambda\) (\(O(N)\))

Since this is a “select non-adjacent elements from \(w\)” problem (similar to maximum independent set), it can be solved with a 2-state DP:

• dp0: best state (cost including penalty, number selected) when the previous element was NOT selected
• dp1: best state (cost including penalty, number selected) when the previous element WAS selected

Process each \(w\) in order with transitions:

• New dp0: “don’t select current” regardless of whether previous was selected: min(dp0, dp1)
• New dp1: to select current, previous must not be selected: dp0 + (w+λ)

In the code, the comparison uses: - Prefer smaller cost - If costs are equal, prefer “more items selected”

This is a crucial technique to maintain the monotonicity of “count decreases as \(\lambda\) increases” in the binary search.

The DP returns: - The minimum (\(\sum w + \lambda \times \#\text{selected}\)) for that \(\lambda\) - The number of selected items cnt

3. Binary search on \(\lambda\)

Since cnt(λ) decreases as \(\lambda\) increases (monotonically decreasing):

• Binary search for the maximum \(\lambda\) satisfying cnt(λ) >= M

The range in the code: - low = -1_000_000_010: sufficiently negative, making it easy to select many items (cnt >= M side) - high = 1_000_000_010: sufficiently positive, selecting almost nothing (cnt < M side)

4. Recovering the final answer

Running DP with the \(\lambda\) found by binary search gives the minimum value including penalties cost (in the form \(cost = C + \lambda \cdot cnt\)).

What we want is the actual cost \(C\) for “exactly \(M\) items,” so we subtract the penalty for \(M\) items: $\(\text{answer} = cost - \lambda \cdot M\)$ (In the code: ans = cost - lam * M).

Complexity

• Time complexity: Sorting is \(O(N\log N)\), one DP run is \(O(N)\), binary search is about \(O(\log 10^9)\approx 31\) iterations, so: $\(O(N\log N + N\log 10^9)\)$
• Space complexity: The difference array \(w\) uses \(O(N)\), and the DP itself uses only a constant number of variables, so: $\(O(N)\)$

Implementation Notes

• The comparison in DP (when costs are equal, adopt the one with more selections) is extremely important. Without this, the monotonicity of cnt breaks down in the binary search on \(\lambda\), causing instability.

• Values can be up to \(10^9\) and \(N\) up to \(2\times 10^5\), so totals can reach the \(10^{14}\) scale. In Python, arbitrary precision is automatic, but setting INF sufficiently large (in the code, \(10^{30}\)) is safe.

• Since input is large, reading all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def solve_lambda(weights, lam):
    INF = 10**30
    dp0_c, dp0_k = 0, 0          # previous item not taken
    dp1_c, dp1_k = INF, -10**18  # previous item taken

    for w in weights:
        a0_c, a0_k = dp0_c, dp0_k
        a1_c, a1_k = dp1_c, dp1_k

        # new dp0 = best of (a0, a1)
        if a0_c < a1_c or (a0_c == a1_c and a0_k > a1_k):
            ndp0_c, ndp0_k = a0_c, a0_k
        else:
            ndp0_c, ndp0_k = a1_c, a1_k

        # new dp1 = take current (must come from a0)
        ndp1_c = a0_c + w + lam
        ndp1_k = a0_k + 1

        dp0_c, dp0_k = ndp0_c, ndp0_k
        dp1_c, dp1_k = ndp1_c, ndp1_k

    # best at end
    if dp0_c < dp1_c or (dp0_c == dp1_c and dp0_k > dp1_k):
        return dp0_c, dp0_k
    else:
        return dp1_c, dp1_k

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    S = data[2:]
    S.sort()

    weights = [S[i + 1] - S[i] for i in range(N - 1)]

    low = -1_000_000_010  # always enough pairs
    high = 1_000_000_010  # always too few pairs (0)

    # binary search for maximum lambda with count >= M
    while high - low > 1:
        mid = (low + high) // 2
        _, cnt = solve_lambda(weights, mid)
        if cnt >= M:
            low = mid
        else:
            high = mid

    lam = low
    cost, cnt = solve_lambda(weights, lam)
    ans = cost - lam * M
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.