Pepero Gifts

Subtask 1 Use a bitmask for the remaining people. For each state, enumerate a sender $a$ and every nearest remaining receiver $b$, then transition to the state with both removed. Store decisions to recover a sequence. Time is $O(2^N N^2)$ and space is $O(2^N+N^2)$.

Optimal value Let $D_1,\ldots,D_N$ be clockwise gaps between consecutive people, including $D_N=L-X_N+X_1$. Let and be the sums of odd and even gaps. The answer is .

Any sequence induces a perfect matching. Choose the traveled shortest arc for each pair and count how many arcs cover each gap. At every person, exactly one arc has an endpoint there, so the coverage counts of its two incident gaps have opposite parity. Thus either every odd gap or every even gap has odd coverage. Total distance is at least $\min(A,B)$.

Choose the lighter of the two alternating adjacent matchings. Its total gap length is at most $L/2$, so every chosen gap is itself a shortest arc. It remains to execute this matching while obeying the nearest-person rule.

Execution order Among remaining people, chosen and unchosen gaps alternate. Write their sums as $A\le B$. If no chosen pair were legal from either endpoint, every chosen gap would be longer than both neighboring unchosen gaps. Summing gives $2A>2B$, a contradiction. Therefore some chosen pair is legal in at least one direction.

Removing a legal pair of length $d$ changes the sums to $A-d$ and $B+d$, because its gap and its two neighboring unchosen gaps merge. The inequality is preserved, so the process continues to the end. With two people remaining, they are necessarily each other's nearest person.

Maintain current circular neighbors using a doubly linked list. At every step scan remaining people and execute a fixed matched pair when its distance is no larger than the sender's distances to both current neighbors. A nearest point on a circle is one of these neighbors. This yields $O(N^2)$ time and $O(N)$ space.

Solution written by GPT6.1