ix. Sorting and Ordering Observations

Sorting the input often makes the structure visible: the answer depends only on the multiset, or the optimal object is sorted, or elements that cannot pass each other keep their relative order.

Fact	Statement
adjacent swaps to sort	exactly the number of inversions
arbitrary swaps to sort a permutation	$n-(\text{number of cycles})$
sort by “move an element to the front”	$n-$ (longest suffix of the sorted order that already appears as a subsequence in order, ending at the largest)
sort by reversing prefixes (pancakes)	at most $2n-3$ flips
relative order	elements that only swap with neighbours, or bounce off each other, keep their order
exchange argument	sort by the key that makes swapping adjacent elements never improve the answer
”choose $k$ elements” problems	after sorting, the optimal choice is often contiguous or a prefix plus a suffix

Proof: adjacent swaps = inversions, swaps = n − cycles

An adjacent swap changes the inversion count by exactly $\pm 1$, and while the array is unsorted some adjacent pair is inverted, so swapping it lowers the count by 1. Hence exactly $\mathrm{inv}$ swaps. For arbitrary swaps: a swap of two elements in the same cycle splits it into two cycles, and a swap across two cycles merges them, so each swap changes the cycle count by exactly $1$. The identity has $n$ cycles, so at least $n-c$ swaps are needed, and swapping an element into its place always splits a cycle, so $n-c$ suffice.

Ants on a stick

$n$ ants on a stick of length $L$ at distinct integer positions, each walking left or right at speed 1; when two meet they both turn around. Over all direction choices, what are the earliest and latest times the last ant falls off?

Turning around is indistinguishable from passing through (only labels swap), so each ant’s “ghost” walks straight. Hence:

pair<int, int> antsTimes(int L, const vector<int>& x) {   // {earliest, latest} time the last ant falls
    int lo = 0, hi = 0;
    for (int v : x) lo = max(lo, min(v, L - v)), hi = max(hi, max(v, L - v));
    return {lo, hi};
}

Proof: collisions can be ignored

Replace “two ants meet and both reverse” by “two ants pass through each other and swap labels”. The set of occupied positions at every moment is the same in both systems, so the moments when some ant falls off are the same. In the pass-through system each ghost falls at time $x$ (walking left) or $L-x$ (walking right). The last fall is the maximum over ghosts; to minimise it, each ghost chooses $\min (x,L-x)$; to maximise it, one ghost chooses $\max (x,L-x)$. Also true: the ants keep their left-to-right order forever, so the $i$-th ghost time to fall off the left end belongs to the $i$-th ant from the left. Tested against an exact collision simulation for all direction choices.

Patterns

Statement	Observation
”the order of operations does not matter”	sort the operations by the cheapest order, or count instead of simulate
”choose pairs to minimise the maximum pair sum”	sort and pair smallest with largest
”minimise $\sum	a_i - x
”minimise $\sum (a_i-x{)}^2$”	$x$ is the mean
”make the array non-decreasing by increments”	prefix maxima; the cost is $\sum ({\max }_{j\le i}{a}_j-a_i)$
“cyclic shifts”	double the array, or fix the rotation that puts the minimum first

Related: Sorting, Exchange Arguments.