1925. How Many Copies of the Smallest Value

Build a stack with four operations, one per line:

push v put v on top, printing nothing pop remove the top value and print it getmin print the smallest value currently held countmin print how many entries equal that smallest value

7 push 4 -> push 2 -> push 2 -> getmin -> 2 countmin -> 2 two entries hold the value 2 pop -> 2 countmin -> 1 now only one does

## The rules, stated so the answer is decidable

• push prints nothing. The other three each print one line.
• pop on an empty stack prints empty. getmin on an empty stack prints
• empty. countmin on an empty stack prints 0, because zero entries equal
• a minimum that does not exist, and that is a count rather than an absence.
• Duplicates are kept. Pushing the same value twice gives two entries, and
• countmin must say two.

Problem 164 is this stack without countmin. It is solved by a parallel stack holding the running minimum at each depth, and that parallel stack is exactly what cannot answer this question, which is why the problem is here.

## What most people try first

Scan the whole stack on every query, taking the minimum and then counting matches. Correct, and O(n) per query. With q at 2 * 10^5 and a stream that is mostly queries, that is about 4 * 10^10 comparisons.

The second thing people try is the parallel running-minimum stack from problem 164, then answering countmin by counting how many entries of THAT stack hold the current minimum. It looks right and it is wrong, because the parallel stack records the minimum at each depth, not the values. Push 1, then 5, then 5: the parallel stack is 1 1 1, which counts three, while only one entry holds the value 1.

## Carry the count alongside the minimum

Make each parallel entry a PAIR: the minimum at that depth and how many entries at or below that depth equal it.

push v: if the stack was empty -> (v, 1) else let (m, c) be the top pair if v < m -> (v, 1) if v == m -> (v, c + 1) if v > m -> (m, c) unchanged, copied up pop: discard both top entries

## Why it is correct

Induction on depth. The pair at depth k describes the first k entries only, and it is built from the pair at depth k - 1 plus the single new value, which is enough: a new value smaller than the old minimum resets the count to one, a new value equal to it adds one, and a larger value changes neither. Because a pop discards the top pair, the pair exposed afterwards is the one that was computed for exactly the entries that remain. Nothing is ever recomputed, so no query can see a stale answer.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. The count reaches 2 * 10^5 and is never multiplied by anything, so no accumulator here can leave 32 bit range. Nothing in this problem needs 64 bit arithmetic.

## Cost

O(1) per operation, with memory proportional to the number of entries. The pair stack doubles the memory of the plain stack, which is the trade this problem is about.

Constraints - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - the stack starts empty - each of `push`, `pop`, `getmin` and `countmin` must run in `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 a scanning solution passes them. At `q = 200000` with every second operation a `countmin` a scan does about `10^10` comparisons, which is the bound the contract is really about