Birthday
Initially child i sits in seat i around a circle. We want the final circular order to be the given permutation, up to choosing one of the two possible orientations of that cycle. All children move simultaneously, and...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Initially child $i$ sits in seat $i$ around a circle. We want the final circular order to be the given permutation, up to choosing one of the two possible orientations of that cycle. All children move simultaneously, and the cost is the maximum circular distance moved by any child.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Fix One Orientation
Consider one clockwise order \[ q_0, q_1, \dots, q_{n-1}. \] If child $q_0$ is placed into final seat $f$, then child $q_i$ must end in seat $f+i \pmod n$.
For child $q_i$, define the signed movement \[ d_i^{(f)} = (f+i-(q_i-1)) \bmod n \] converted to the shortest signed circular move:
keep it positive if it is at most $n/2$,
otherwise subtract $n$.
When the two directions are equally short ($n$ even and the move is $n/2$), we keep the positive value, exactly as in the official analysis.
So every movement belongs to the cyclic set \[ D = \{\,1-\lceil n/2 \rceil,\ 2-\lceil n/2 \rceil,\ \dots,\ \lfloor n/2 \rfloor\,\}, \] which contains exactly $n$ consecutive integers.
Shifting the First Child
Let $S_f = \{d_i^{(f)}\}$. If we increase $f$ by $1$, every signed movement also increases by $1$, except that $\lfloor n/2 \rfloor$ wraps around to $1-\lceil n/2 \rceil$. Hence all $S_f$ are just cyclic shifts of one base set, say $S_0$.
Therefore the problem becomes:
Choose a cyclic shift of the occupied values in $D$ so that the largest absolute occupied value is minimized.
Largest Empty Cyclic Gap
Mark which values of $D$ appear in $S_0$. Let $C$ be the maximum length of a consecutive cyclic block of values in $D$ that does not appear.
Then all occupied values can be rotated into one ordinary interval of length \[ L = n - C. \] Among all intervals of $L$ consecutive signed values, the best one is centered as close to $0$ as possible, so the minimum possible mess is \[ \left\lfloor \frac{L}{2} \right\rfloor = \left\lfloor \frac{n-C}{2} \right\rfloor. \]
Thus one orientation is solved in linear time:
compute all signed moves for $f=0$,
mark the values that appear,
find the longest cyclic run of values that do not appear,
return $\lfloor (n-C)/2 \rfloor$.
Two Possible Final Orientations
The permutation can be realized in two circular directions:
$p_1, p_2, \dots, p_n$,
$p_1, p_n, p_{n-1}, \dots, p_2$.
We solve both and take the smaller answer.
Complexity
Time: $O(n)$.
Space: $O(n)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int signed_shift(int x, int n) {
return (2 * x <= n ? x : x - n);
}
int solve_orientation(const vector<int> &order) {
int n = (int)order.size();
int low = 1 - (n + 1) / 2;
vector<char> seen(n, 0);
for (int i = 0; i < n; ++i) {
int delta = (i - (order[i] - 1)) % n;
if (delta < 0) delta += n;
int move = signed_shift(delta, n);
seen[move - low] = 1;
}
int first = 0;
while (first < n && !seen[first]) ++first;
if (first == n) return 0;
int best_gap = 0;
int current_gap = 0;
for (int step = 1; step <= n; ++step) {
int idx = (first + step) % n;
if (!seen[idx]) {
++current_gap;
} else {
best_gap = max(best_gap, current_gap);
current_gap = 0;
}
}
return (n - best_gap) / 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; ++i) cin >> p[i];
vector<int> reversed(n);
reversed[0] = p[0];
for (int i = 1; i < n; ++i) reversed[i] = p[n - i];
cout << min(solve_orientation(p), solve_orientation(reversed)) << '\n';
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.