1931. Stacks of Plates With a Pop at One of Them

Plates are stacked in piles that are at most h high. When the last pile is full a new pile is started beside it. Four operations arrive, one per line:

push v put v on the last pile, or start a new pile, and print which pile pop take the top plate off the LAST pile and print it popat i take the top plate off pile i, 1-indexed, and print it count print how many piles exist

h = 2 push 7 -> 1 pile 1 is 7 push 8 -> 1 pile 1 is 7 8, now full push 9 -> 2 pile 2 is 9 popat 1 -> 8 pile 1 is 7 push 5 -> 2 pile 2 is 9 5, NOT pile 1; a gap is never filled popat 2 -> 5 pop -> 9 pile 2 is now empty, so it stops existing count -> 1

## The rules, stated so the answer is decidable

• push prints the 1-indexed pile the plate landed on. It puts the plate on
• the LAST pile if that pile holds fewer than h plates, otherwise it starts a
• new pile at the end. It never looks for a pile with a gap in it.
• pop prints the plate taken from the last pile, or empty when no pile
• exists.
• popat i prints the plate taken from pile i, or oor when i is below 1,
• above the number of piles, or names a pile that is currently empty.
• After every pop and every popat, while the LAST pile exists and is empty,
• it stops existing. That repeats, so removing the last plate of the last pile
• can retire several piles at once if empty ones were sitting behind it.
• A pile emptied by popat that is NOT the last one keeps existing as a gap.
• It is still addressable by popat, which then reports oor, and count
• still counts it.
• h is at least 1.

Problem 174 holds two stacks in one array, where the number of stacks is fixed and known. Here the number is part of the state and, uniquely in this bank, it can go DOWN as a side effect of a removal.

## What most people try first

Keep a list of piles, and on pop scan from the end for the last non-empty pile. That is correct only if trailing empty piles are allowed to exist, which the rule above forbids, and it is also O(n) per pop. A stream that fills 10^5 piles of height 1, empties all but the last with popat, and then alternates push and pop makes every pop scan the whole list, which is about 10^10 steps at the stated limits.

## Retire the empties and the scan disappears

Hold the piles in a growable list. The retiring rule gives an invariant worth stating on its own:

either no pile exists, or the LAST pile is non-empty

With that invariant, pop never scans: the pile it wants is the last one, and it is guaranteed to hold a plate. push never scans either, because its target is the last pile or a brand new one. popat indexes directly. So the only loop in the whole structure is the retiring loop itself.

pop: take from the last pile, then retire trailing empties popat i: reject if out of range or that pile is empty otherwise take from pile i, then retire trailing empties count: the length of the list

## Why the retiring loop is cheap

It looks like an unbounded loop inside an operation, and it is: one pop can retire many piles. But a pile is created exactly once, by one push, and retired at most once, so across the whole run the loop body executes at most as many times as there were pushes. Every operation is therefore amortised O(1) even though one of them can be linear.

## Why the derived definition agrees

An equivalent way to say the whole rule is: the number of piles is one more than the index of the last non-empty pile. That is worth knowing because it gives a slow but obviously correct implementation to check against, and because it shows the retiring rule is not an extra policy bolted on. It is the only definition of the count that stays consistent with push always targeting the end.

## Overflow

Plate values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. h and the pile count both reach 2 * 10^5, and nothing is multiplied, so no accumulator here leaves 32 bit range. Do not compute a slot as pile * h + position: at the stated limits that product is 4 * 10^10, which does NOT fit, which is a reason to store each pile separately rather than carve one flat array into equal blocks.

## Cost

O(q) in total, amortised constant per operation, with memory proportional to the number of plates resident plus the number of piles.

Constraints - `1 ≤ h ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - `0 ≤ i ≤ 200000` - no pile exists at the start - each of `push`, `pop`, `popat` and `count` must run in amortised `O(1)`, so the whole run is `O(q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so scanning backwards for the last non-empty pile passes them while doing about `10^10` steps on a stream that leaves many gaps