Three-Dimensional Ladder Game

For each destination $i$, let $p_i$ be the zero-based index of its starting pole. Initially set $d_i=i-p_i$. Unwrap the circle into an infinite line; adding a multiple of $N$ to $d_i$ represents another lift of the same destination.

If $d_u-d_v>N$, subtract $N$ from ${}_{}$ and add to . This preserves the sum of displacements and does not increase the number of necessary crossings. Repeat until the difference between the maximum and minimum displacements is at most .

Define $x_i=p_i+d_i$. For $$, the minimum number of crossings between these two paths is

$$\left|\left\lfloor\frac{x_i-x_j-1}{N}\right\rfloor+[p_i<p_j]\right|.$$

The bracket equals $1$ when its condition holds and $0$ otherwise. Sum this expression over all $i<j$. Use mathematical floor division, not integer division truncated toward zero, for negative numerators.

When choosing the maximum and minimum each time, no index needs to be adjusted twice, so there are $O(N)$ adjustments. Each adjustment takes $O(N)$ time and the pair sum takes $O(N^2)$ time. Total time is $O(N^2$ with auxiliary space.

Solution written by GPT6