Official

C - Socks 2 Editorial by en_translator

First, it is optimal to pair socks that he has not lost.

Proof

For a color $p$ that he has not used, consider a case where two socks with color $p$ are not paired. When they are colored with socks of color $A_i$ and $A_j$, by the triangle inequality $|A_i-A_p| + |A_j-A_p| \geq |A_i-A_j| = |A_i-A_j| + |A_p-A_p|$, so the total weirdness does not increase by pairing $(A_p,A_p)$ and $(A_i,A_j)$ instead of $(A_p,A_i),(A_p,A_j)$. When one sock of color $p$ is not paired with any sock, while the other is paired with a sock of another color $A_i$, then the total weirdness does not increase by pairing $(A_p, A_p)$ and leaving $A_i$ unpaired instead of pairing $(A_p, A_i)$ and leaving $A_p$ unpaired. Thus, we can assume that the two socks of color $A_p$ are always paired in the optimal solution.


Thus, this problem can be considered as a problem that asks to make \(\lfloor \frac{K}{2} \rfloor\) pairs from one sock each of color \(A_1,A_2,\dots,A_K\).

If \(K\) is even, it seems optimal that pairing \((A_1,A_2),(A_3,A_4),\dots,(A_{K-1},A_K)\), so that adjacent colors (in the sorted sequence) are paired, which is indeed the case.

Proof

We show it by induction with respect to $K$. It is sufficient to show that color $A_1$ is always paired with color $A_2$ in an optimal solution.

We prove the claim above by contradiction. In an optimal solution, suppose that color $A_1$ is paired with color $A_i\ (i > 2)$, and color $A_2$ with color $A_j$. Then, by $A_1 < A_2 < A_i, A_j$, we have $|A_i-A_1| + |A_j-A_2| > |A_2-A_1| + |A_j-A_i|$, so pairing $(A_1,A_2)$ and $(A_i,A_j)$ instead of $(A_1,A_i)$ and $(A_2,A_j)$ make the total weirdness smaller, which violates the optimality.


The problem is when \(K\) is odd. In this case, we can brute-force over the only color that is not paired, where the optimal way to make pairs from the other socks can be found just as we did for an even \(K\). When the only color that is not paired is fixed, the minimum total weirdness when the remaining socks are paired is naively found in \(O(N)\) time, but it results in a total of \(O(N^2)\) complexity. Instead, one can precalculate the total weirdness when the first few socks are paired, such as \(\mathrm{presum}[2]=(A_2-A_1),\mathrm{presum}[4]= (A_4-A_3)+(A_2-A_1), \mathrm{presum}[6]=(A_6-A_5)+(A_4-A_3)+(A_2-A_1),\dots\), in manner of prefix sum; one can also find “suffix sum.” Thus, this way, the problem can be solved in a total of \(O(N)\) time.

Bonus: when \(K\) is odd, instead of brute-forcing ever sock that is not paired, one can only try \(A_1,A_3,A_5,\dots,A_K\) (proof omitted). In the following sample code, we adopt this method to simplify the implementation.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    for (int &i: a) cin >> i;
    vector<int> pre(k + 1), suf(k + 1);
    for (int i = 1; i <= k; i++) {
        pre[i] = pre[i - 1];
        if (i % 2 == 0) pre[i] += a[i - 1] - a[i - 2];
    }
    for (int i = k - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        if ((k - i) % 2 == 0) suf[i] += a[i + 1] - a[i];
    }
    int ans = 1e9;
    for (int i = 0; i <= k; i += 2) {
        ans = min(ans, pre[i] + suf[i]);
    }
    cout << ans << endl;
}

posted:
last update: