Arranging Shoes
There are 2n shoes: n left shoes (represented by -i) and n right shoes (+i) for sizes i = 1,, n. Rearrange using the minimum number of adjacent swaps so that each pair is adjacent with the left shoe on the left.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
There are $2n$ shoes: $n$ left shoes (represented by $-i$) and $n$ right shoes ($+i$) for sizes $i = 1, \ldots, n$. Rearrange using the minimum number of adjacent swaps so that each pair is adjacent with the left shoe on the left.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Greedy Strategy
Process positions left to right. For each even position $i$ (start of a pair slot):
Let shoe $s$ be at position $i$. If $s > 0$ (right shoe), its matching left shoe $-s$ is somewhere to the right; conceptually swap them (costs 1 extra swap) so the left shoe is at position $i$.
Find the matching shoe and bring it to position $i+1$ by counting the number of active (not yet matched) positions between them.
Mark both positions as used.
Counting with a Fenwick Tree
A Fenwick tree tracks active positions. The cost to bring the match from position $j$ to the slot adjacent to position $i$ is the number of active positions strictly between $i$ and $j$.
Lemma.
This greedy produces the minimum number of swaps.
Proof (Proof sketch).
At each step, the pair occupying the leftmost unfilled slot is fixed. The greedy matches each pair optimally: bringing the partner with the minimum number of intermediate active elements. Since completed pairs never need to be disturbed again, this is optimal.
Complexity Analysis
Time: $O(n \log n)$ -- each shoe processed once with $O(\log n)$ Fenwick tree operations.
Space: $O(n)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> tree;
BIT(int n) : n(n), tree(n + 1, 0) {}
void update(int i, int val) {
for (i++; i <= n; i += i & (-i))
tree[i] += val;
}
int query(int i) {
int s = 0;
for (i++; i > 0; i -= i & (-i))
s += tree[i];
return s;
}
// number of active elements in [0, i]
};
long long count_swaps(vector<int> S) {
int n2 = S.size();
int n = n2 / 2;
// For each shoe size, store positions of left and right shoes
map<int, queue<int>> left_pos, right_pos;
for (int i = 0; i < n2; i++) {
if (S[i] < 0)
left_pos[-S[i]].push(i);
else
right_pos[S[i]].push(i);
}
BIT bit(n2);
// Initialize: all positions active (value 1)
for (int i = 0; i < n2; i++)
bit.update(i, 1);
vector<bool> used(n2, false);
long long ans = 0;
for (int i = 0; i < n2; i++) {
if (used[i]) continue;
int shoe = S[i];
int match_pos;
if (shoe < 0) {
// Left shoe, find matching right shoe
int size = -shoe;
match_pos = right_pos[size].front();
right_pos[size].pop();
left_pos[size].pop(); // this is position i
} else {
// Right shoe at left position of pair: need extra swap
int size = shoe;
match_pos = left_pos[size].front();
left_pos[size].pop();
right_pos[size].pop(); // this is position i
ans++; // one swap to put left before right
}
// Cost: number of active positions between i and match_pos, minus 1
// (because we bring match_pos next to i)
int lo = min(i, match_pos);
int hi = max(i, match_pos);
int active_between = bit.query(hi) - bit.query(lo);
ans += active_between;
used[i] = true;
used[match_pos] = true;
bit.update(i, -1);
bit.update(match_pos, -1);
}
return ans;
}
// For local testing
int main() {
int n;
scanf("%d", &n);
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
scanf("%d", &S[i]);
printf("%lld\n", count_swaps(S));
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.