Editorial: Magical Tiered Cake

You are given three pegs (kitchen, warehouse, party), each holding a stack of cake layers. Layer $i$ is the $i$-th tier by size ($1$ = smallest on top, $n$ = largest on bottom). A move picks one movable layer from any peg and places it on top of another peg, but only if the new top is smaller than the layer below it (or the peg is empty).

The magic rule: layer $i$ is movable on a peg iff exactly $a_i$ layers on that same peg sit above it.

The problem asks for a construction within $2^n$ moves, or NO if impossible.

Because you may only place a smaller layer on a larger one, every peg’s stack is always sorted by increasing layer number from top to bottom.

So a peg containing layers $\{3,5,7\}$ must look like $[3,5,7]$ (top to bottom), never $[5,3,7]$.

Once you notice this, movability becomes combinatorial:

On a peg whose layer set is $S$, layer $i \in S$ is movable iff

$$\bigl|\{ j \in S : j < i \}\bigr| = a_i.$$

That is: among layers sharing the peg, exactly $a_i$ of the smaller ones must be present (they are precisely the layers above $i$).

Layer $i$ can have at most $i - 1$ smaller layers anywhere in the cake, hence at most $i - 1$ above it on its peg. Therefore:

Example: $n = 3$, $a = [2,2,2]$. Layer $1$ needs two layers above it, but only two other layers exist and they cannot both sit above the smallest tier in a valid stack — impossible (sample test 3).

Surprisingly, this condition is also sufficient. Every array with $a_i \le i - 1$ admits a valid sequence within $2^n$ moves. The rest of the editorial builds one.

If layers $1,2,\ldots,k$ share a peg in sorted order, layer $k$ has exactly $k - 1$ smaller layers above it, so it is movable.

Start with $[1,2,\ldots,n]$ in the kitchen. Move $n$ to the party, then $n-1$, …, then $1$. Each move is legal; total $n$ moves.

This matches sample test 2 ($a = [0,1,2]$): output moves $3,2,1$ to the party.

Now layer $i$ moves only when no smaller layer shares its peg — i.e. when it is the top of its stack.

To extract bottom layer $n$ from a complete tower, you must first move off layers $1,2,\ldots,n-1$ — classic Tower of Hanoi. This takes $2^n - 1$ moves, still within the budget.

Sample test 1 ($a = [0,0,0]$) uses $7 = 2^3 - 1$ moves.

These extremes suggest a recursive strategy: before moving a large layer, temporarily relocate a controlled number of smaller layers to the warehouse.

Focus on a contiguous block of layers $l, l+1, \ldots, k$ that currently live together on one peg in sorted order.

Layer $k$ (the bottom of the block) has exactly $(k - l)$ smaller layers from the block above it. It is movable iff

Define the deficit

If $d > 0$, we must remove the $d$ smallest layers of the block ($l, l+1, \ldots, l+d-1$) to another peg before moving $k$.

Move layers $l..k$ from src to dst using aux as spare:

1. Stash: move_range(l, l+d-1, src, aux, dst) — park the top $d$ layers on the warehouse peg.
2. Move bottom: move layer $k$ from src to dst.
3. Middle tiers: for $m = k-1, k-2, \ldots, l+d$, adjust how many smaller layers sit on the same peg as $m$ until exactly $a_m$ of them are present, then move $m$ to dst.
   • If too few smaller layers share the peg, pull one in from another peg (often from the stash).
   • If too many share the peg, push the largest smaller one away — but never onto dst if it is smaller than some middle layer still waiting, or you block a later placement.
4. Unstash: move any remaining layers among $l..l+d-1$ from aux/src onto dst.

Steps 1 and 4 are the same recursion on a smaller interval; step 2 is one move. This is the Hanoi-like skeleton.

Each recursive call strictly shrinks the interval length or peels one layer permanently to the party. The all-zero case achieves $2^n - 1$; the all-$(i-1)$ case achieves $n$. Every mixed array sits between these extremes, so the total is at most $2^n - 1 \le 2^n$.

The recursive construction is the intended solution path and handles the large structured cases (all zeros, all $a_i = i-1$) in $O(2^n)$ time with no search.

For a few mixed small patterns the direct recursion needs careful peg selection when clearing blockers; the reference implementation (model_sol.cpp) validates the recursive trace and, if needed, finishes with a breadth-first search on the tiny state graph for that test case. With $a_i \le i - 1$, the graph is small enough for $n \le 20$ under the given $\sum 2^n$ limit.

For each test case:

1. If some $a_i > i - 1$, print NO.
2. Otherwise run move_range(1, n, kitchen, party, warehouse).
3. If simulation fails, BFS with move cap $2^n$.
4. Print YES, move count, and moves $(\mathrm{id}, \mathrm{from}, \mathrm{to})$.

$a = [0,1,2]$, $n = 3$. Here $a_k = k - 1$ for every layer, so $d = 0$ always.

• Move $3$ kitchen $\to$ party.
• Move $2$ kitchen $\to$ party (now exactly one smaller layer, layer $3$, is below on another peg — on the party stack, layer $2$ sits on $3$).
• Move $1$ kitchen $\to$ party.

Three moves; matches the sample.

$a = [0,0,0]$, $n = 3$. For layer $3$, $d = 2$:

1. Stash layers $1,2$ to the warehouse (recursive Hanoi on two layers).
2. Move $3$ to the party.
3. Move $2$, then $1$ to the party in valid order.

Total $7$ moves.

• Recursive construction: $O(2^n)$ moves, $O(n \cdot 2^n)$ time in the worst case (all zeros).
• BFS fallback (rare): exponential in $n$ but only over feasible states; used when the direct trace needs correction on small $n$.

Both satisfy the problem limits.