Pepero Disposal

Let $s_i$ be 1 if person $i$ initially faces right and 0 otherwise. Define the final-direction indicator $c_i$ similarly. Let $l_i,r_i$ be their total left and right departures. Alternation implies $r_i-l_i=s_i-c_i$.

Put $P_i=\sum_{j\leq i}A_j$ and let be the number of sticks discarded to the left. Conservation across each edge gives , with and . Consequently,

$$W=\sum_{i=1}^{N}P_i-\sum_{i=1}^{N}s_i,\qquad (N+1)L=W+\sum_{i=1}^{N}c_i.$$

Since $0\leq\sum c_i\leq N$, both $L=\lceil W/(N+1)\rceil$ and the final number of right-facing people are determined.

Scan from left to right, maintaining $l_i$ and the remaining number $K$ of right-facing final directions. Set $c_i=1$ precisely when , , and , and decrement . Otherwise set . Update and . The answer is .

To justify the greedy choice, put $Y_i=\sum_{j\leq i}c_j$, , and . Nonnegative departures are equivalent to

$$Y_i\leq U_i=iL-Q_{i-1}+H_i+\min(0,L-P_i).$$

Because $P_i$ is nondecreasing, $U_i$ first increases and then decreases, ending at the required total number of final right directions. Thus taking a feasible 1 as early as possible, while respecting this total, never violates a later upper bound. Comparing prefixes against any feasible final state shows that greedy never chooses its 1s later, so it reaches the required total. All departures are nonnegative and the boundary conditions hold.

It remains to show these counts describe a legal execution. A fired person's last departure is opposite their final direction. On a path, a directed last-departure cycle could only be two neighbors whose final directions are left, right. If greedy creates this transition, $r_i=0$ or $l_{i+1}=0$, implying one endpoint never fires. Hence there is no last-departure cycle among fired people.

Any legal execution cannot exceed the computed quota at a vertex: at the first excess firing, neighbors have sent at most their quotas, so conservation leaves no stick there. If an execution finished with unused quotas, the remaining departures would be balanced at each vertex and send no stick to a sink. Following their last departures would create a directed cycle, a contradiction. Therefore every legal execution has exactly these counts, and their sum is the minimum.

The time and space complexities are $O(N)$. Use signed 64-bit integers. For $C=\sum A_i$, we have $l_i\leq iC+i-1$, giving the safe answer bound .

Solution written by GPT6.1