Sorting
Given a permutation S[0..n - 1] and a sequence of m grader swaps (P_i, Q_i), in each round i the grader first applies swap (P_i, Q_i) to S, then you apply your own swap (X_i, Y_i). Find the minimum number of rounds m^...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given a permutation $S[0..n{-}1]$ and a sequence of $m$ grader swaps $(P_i, Q_i)$, in each round $i$ the grader first applies swap $(P_i, Q_i)$ to $S$, then you apply your own swap $(X_i, Y_i)$. Find the minimum number of rounds $m^*$ to sort $S$, and output your swaps.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Binary Search on the Number of Rounds
Lemma.
The minimum number of swaps to sort a permutation equals $n$ minus the number of cycles in the permutation.
Let $S'$ be the permutation obtained by applying grader swaps $(P_0,Q_0), \ldots, (P_{m-1}, Q_{m-1})$ to $S$. Then $m$ rounds suffice if and only if the number of swaps needed to sort $S'$ is at most $m$, i.e., $n - \text{cycles}(S') \le m$.
This predicate is monotone in $m$ (applying more grader swaps can only be compensated by more of our swaps), so we binary search on $m$.
Constructing the Swap Sequence
Given the optimal $m^*$:
Compute $S'$ by applying grader swaps $0, \ldots, m^*{-}1$ to $S$.
Find the cycle decomposition of $S'$ and generate a list of $\le m^*$ swaps that sort $S'$ (pad with dummy swaps $(0,0)$).
These swaps are expressed in terms of elements (not positions). Simulate forward: at each round, after the grader's swap, find the current positions of the two target elements and swap those positions.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int n, int S[], int m,
int P[], int Q[], int X[], int Y[]) {
auto check = [&](int rounds) -> bool {
vector<int> T(S, S + n);
for (int i = 0; i < rounds; i++) swap(T[P[i]], T[Q[i]]);
vector<bool> vis(n, false);
int cycles = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
cycles++;
for (int j = i; !vis[j]; j = T[j]) vis[j] = true;
}
}
return n - cycles <= rounds;
};
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (check(mid)) hi = mid; else lo = mid + 1;
}
int ans = lo;
// Build swap sequence
vector<int> T(S, S + n);
for (int i = 0; i < ans; i++) swap(T[P[i]], T[Q[i]]);
vector<pair<int,int>> planned;
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i] && T[i] != i) {
vector<int> cyc;
for (int j = i; !vis[j]; j = T[j]) { vis[j] = true; cyc.push_back(j); }
for (int k = (int)cyc.size()-1; k >= 1; k--)
planned.push_back({cyc[0], cyc[k]});
}
}
while ((int)planned.size() < ans) planned.push_back({0, 0});
// Simulate forward, translating element-swaps to position-swaps
vector<int> pos(n), elem(n);
for (int i = 0; i < n; i++) { elem[i] = S[i]; pos[S[i]] = i; }
for (int i = 0; i < ans; i++) {
// Grader swap
int a = elem[P[i]], b = elem[Q[i]];
swap(elem[P[i]], elem[Q[i]]);
pos[a] = Q[i]; pos[b] = P[i];
// Our swap (by element)
int u = planned[i].first, v = planned[i].second;
X[i] = pos[u]; Y[i] = pos[v];
swap(elem[X[i]], elem[Y[i]]);
pos[u] = Y[i]; pos[v] = X[i];
}
return ans;
}Complexity Analysis
Time: $O((n + m) \log m)$ for binary search, $O(n + m)$ for construction.
Space: $O(n + m)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int n, int S[], int m,
int P[], int Q[], // grader's swaps (size m)
int X[], int Y[]) // our swaps (output)
{
// Binary search on number of rounds
int lo = 0, hi = m;
auto check = [&](int rounds) -> int {
// Simulate S after 'rounds' grader swaps
vector<int> T(S, S + n);
for (int i = 0; i < rounds; i++) {
swap(T[P[i]], T[Q[i]]);
}
// Count cycles
vector<bool> visited(n, false);
int cycles = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
cycles++;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = T[j];
}
}
}
return n - cycles <= rounds;
};
while (lo < hi) {
int mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid + 1;
}
int ans = lo;
// Construct the swap sequence
// Compute S after 'ans' grader swaps
vector<int> T(S, S + n);
for (int i = 0; i < ans; i++) {
swap(T[P[i]], T[Q[i]]);
}
// Find swaps to sort T: process cycles
// planned[k] = (element_a, element_b) to swap in step k (in terms of elements, not positions)
vector<pair<int,int>> planned;
vector<bool> visited(n, false);
for (int i = 0; i < n; i++) {
if (!visited[i] && T[i] != i) {
// Trace cycle starting at i
vector<int> cycle;
int j = i;
while (!visited[j]) {
visited[j] = true;
cycle.push_back(j);
j = T[j];
}
// Sort this cycle: swap cycle[0] with cycle[k] for k = len-1 down to 1
for (int k = (int)cycle.size() - 1; k >= 1; k--) {
planned.push_back({cycle[0], cycle[k]});
}
}
}
// Pad with dummy swaps
while ((int)planned.size() < ans) {
planned.push_back({0, 0});
}
// Now simulate forward and adjust
// pos[v] = current position of element v
// elem[p] = element at position p
vector<int> pos(n), elem(n);
for (int i = 0; i < n; i++) {
elem[i] = S[i];
pos[S[i]] = i;
}
for (int i = 0; i < ans; i++) {
// Grader swap: swap positions P[i] and Q[i]
int a = elem[P[i]], b = elem[Q[i]];
swap(elem[P[i]], elem[Q[i]]);
pos[a] = Q[i];
pos[b] = P[i];
// Our swap: we want to swap elements planned[i].first and planned[i].second
int u = planned[i].first, v = planned[i].second;
X[i] = pos[u];
Y[i] = pos[v];
// Apply our swap
swap(elem[X[i]], elem[Y[i]]);
pos[u] = Y[i];
pos[v] = X[i];
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
int S[n];
for (int i = 0; i < n; i++) scanf("%d", &S[i]);
int m;
scanf("%d", &m);
int P[m], Q[m];
for (int i = 0; i < m; i++) scanf("%d %d", &P[i], &Q[i]);
int X[m], Y[m];
int ans = findSwapPairs(n, S, m, P, Q, X, Y);
printf("%d\n", ans);
for (int i = 0; i < ans; i++) printf("%d %d\n", X[i], Y[i]);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.