Pepero Party

Sort remaining givers and recipients by their numbers, and match equal ranks. Initially this is the identity matching. Maintain that this matching is valid and each matched recipient is at most the giver's original number.

For giver $i$, let $x$ be their matched recipient and $y$ the previous remaining recipient, or 0 if none exists. Call $i$ blocked if $L_i>y$. The first giver is always blocked. Choose the rightmost blocked giver $i$.

The response $j$ cannot precede $x$, since $j\geq L_i>y$. Removing $i$ and shifts each intervening giver's match one recipient to the left. Every giver to the right of is unblocked, so its lower bound remains satisfied after the shift. Upper bounds remain satisfied because recipients only decrease. The matching stays valid, proving success on every turn against every interactor choice.

Maintain, for each remaining giver,

$$D_i=\operatorname{rank}_{\rm giver}(i)-\#\{\text{remaining recipients }j<L_i\}-1,$$

using 1-based ranks. Validity implies $D_i\geq0$, and blocked givers are exactly those with $D_i=0$. After removing giver $$ and recipient , decrement precisely for with . Indeed, any giver with lies to the right of , so its two rank changes cancel.

Divide original giver indices into blocks of size $B$. Within each block, sort by $L_i$ and use a lazy segment tree for prefix decrements and the minimum. Materialize and rebuild the selected giver's block after directly updating it. For each complete block to its right, decrement the prefix with $L_k\leq j$. Maintain a set of blocks whose minimum is zero to find the rightmost zero.

Time is $O(N(B+(N/B)\log B))$ and space is $O(N)$. The implementation uses $B=1024$. For , explicitly maintaining the sorted matching gives an solution. For , exhaustive minimax search over two masks of used givers and recipients is sufficient.

Solution written by GPT6.1