Overview

This problem asks us to form \(M\) pairs from \(N\) given socks, minimizing the total “difference in color intensity (awkwardness)” across all pairs.

Since the number of socks \(N\) and the number of pairs to form \(M\) can be as large as \(2 \times 10^5\), a naive dynamic programming (DP) approach is too slow. Therefore, we use an advanced optimization technique called WQS binary search (also known as Alien DP) to efficiently find the solution.

---

Analysis

1. Sorting the Socks (Optimality of Adjacent Pairs)

Intuitively, it is optimal to pair socks with similar color intensities. Let \(A\) be the array of sock color intensities sorted in ascending order. Then, optimal pairs always consist of adjacent elements in the sorted array.

For example, if the sorted socks are \([1, 3, 4, 9]\): - Forming adjacent pairs \((1, 3)\) and \((4, 9)\) gives a total awkwardness of \(|1-3| + |4-9| = 2 + 5 = 7\). - Forming crossing pairs \((1, 9)\) and \((3, 4)\) gives a total awkwardness of \(|1-9| + |3-4| = 8 + 1 = 9\), which is worse.

Therefore, after sorting the array, we only need to decide whether to “pair two adjacent elements or skip them without pairing.”

2. Naive DP and Its Limitations

This problem can be solved with the following dynamic programming (DP):

• \(dp[i][j]\): the minimum total awkwardness when forming \(j\) pairs from the first \(i\) socks

The transition takes the minimum of the following two choices: 1. Do not pair the \(i\)-th sock: \(dp[i-1][j]\) 2. Pair the \(i\)-th sock with the \((i-1)\)-th sock: \(dp[i-2][j-1] + (A[i-1] - A[i-2])\)

However, the number of states in this DP is \(O(NM)\). Since \(N, M \le 2 \times 10^5\), the number of states can be up to \(4 \times 10^{10}\), which exceeds time limits (TLE) and memory limits (MLE).

3. Dimension Reduction via WQS Binary Search (Alien DP)

The constraint “choose exactly \(M\) pairs” is what causes the DP dimension to grow to \(O(NM)\). To remove this constraint, we consider a new problem: “each time a pair is formed, a penalty (additional cost) \(C\) is incurred.”

By fixing the penalty \(C\), we no longer need to track the number of pairs, reducing the DP dimension by one. - \(dp[i]\): the minimum cost using the first \(i\) socks, considering the penalty \(C\)

The transition becomes: 1. Do not pair the \(i\)-th sock: \(dp[i-1]\) 2. Pair the \(i\)-th sock: \(dp[i-2] + (A[i-1] - A[i-2] + C)\)

This DP can be computed efficiently in \(O(N)\).

The relationship (monotonicity) between the penalty \(C\) and the number of pairs formed is as follows: - If \(C\) is very large, the cost of forming pairs is too high, so \(0\) pairs are formed. - If \(C\) is very small (a large negative value), forming pairs decreases the overall cost, so as many pairs as possible are formed.

Using this property, we binary search for the threshold penalty \(C\) at which the number of pairs formed is exactly \(M\) (or more).

---

Algorithm

1. Sort: Sort the sock array \(S\) in ascending order.
2. Binary Search: Set the search range for penalty \(C\) to \([low, high] = [-2 \times 10^9, 2 \times 10^9]\).
3. Decision Function (DP):
   • For a given \(C\), run the \(O(N)\) DP.
   • Each DP element stores {minimum cost, maximum number of pairs achieving that cost}.
   • When costs are equal, prioritize the option with more pairs (tiebreaking).
4. Binary Search Update:
   • If the number of pairs obtained from the DP is \(M\) or more, we can potentially increase the penalty \(C\) to reduce the number of pairs, so set low = mid + 1 and record the current mid as the tentative optimal penalty ans_C.
   • If the number of pairs is less than \(M\), the penalty is too large, so set high = mid - 1.
5. Answer Recovery:
   • Run the DP again using the optimal penalty ans_C.
   • The obtained minimum cost equals “total awkwardness + \(M \times ans\_C\)”, so subtracting \(M \times ans\_C\) from it gives the true minimum total awkwardness when forming exactly \(M\) pairs.

---

Complexity

• Time Complexity: \(O(N \log N + N \log(\max |S_i|))\)

  • Sorting takes \(O(N \log N)\).
  • The number of binary search iterations is approximately \(32\), since the search range for the penalty is about \(4 \times 10^9\). Each step performs an \(O(N)\) DP, so the entire binary search takes \(O(N \log(\max |S_i|))\), which is well within the time limit.

• Space Complexity: \(O(N)\)

  • We maintain an array of size \(N\) and a DP table, so the space complexity is \(O(N)\), which easily fits within the memory limit.

---

Implementation Notes

• Tiebreaking: In the DP transition, when two choices have equal cost, select the one with more pairs. This is essential for reliably finding the boundary that achieves the target number of pairs \(M\).

• Sign of Penalty \(C\): The penalty \(C\) can be negative (effectively a bonus). Therefore, the initial value low for the binary search must be set to a large negative value.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Solves the DP for a fixed penalty C.
// Returns {minimum_cost, maximum_pairs_achieving_this_cost}.
pair<long long, long long> solve_dp(long long C, const vector<long long>& A) {
    int n = A.size();
    vector<pair<long long, long long>> dp(n + 1);
    dp[0] = {0, 0};
    dp[1] = {0, 0};
    for (int i = 2; i <= n; ++i) {
        // Option 1: Do not pair the i-th sock
        auto res = dp[i-1];
        
        // Option 2: Pair the i-th sock with the (i-1)-th sock
        auto res2 = dp[i-2];
        res2.first += A[i-1] - A[i-2] + C;
        res2.second += 1;
        
        // Choose the option that minimizes cost, maximizing pairs as a tie-breaker
        if (res2.first < res.first) {
            dp[i] = res2;
        } else if (res2.first > res.first) {
            dp[i] = res;
        } else {
            dp[i] = (res2.second > res.second) ? res2 : res;
        }
    }
    return dp[n];
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    if (!(cin >> N >> M)) return 0;
    
    vector<long long> S(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }
    
    // Sort the socks by color intensity
    sort(S.begin(), S.end());
    
    // Binary search over the penalty C
    long long low = -2e9 - 7;
    long long high = 2e9 + 7;
    long long ans_C = low;
    
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        auto res = solve_dp(mid, S);
        if (res.second >= M) {
            ans_C = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    // Retrieve the answer using the optimal penalty ans_C
    auto res = solve_dp(ans_C, S);
    long long ans = res.first - M * ans_C;
    cout << ans << "\n";
    
    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.