1930. The Ring That Overwrites Instead of Refusing

A fixed ring holds at most c entries. When a write arrives and the ring is already full, the OLDEST entry is thrown out to make room, and the write reports which value it destroyed. Three operations arrive, one per line:

write v store v as the newest entry read remove and print the oldest entry peek k print the k-th oldest entry, 1-indexed, without removing it

c = 3 write 10 -> ok write 20 -> ok write 30 -> ok the ring holds 10 20 30, oldest first write 40 -> 10 full, so 10 is destroyed; the ring is 20 30 40 peek 1 -> 20 read -> 20 peek 3 -> oor only 30 and 40 remain

## The rules, stated so the answer is decidable

• write prints ok when there was room, or the destroyed value when there
• was not. It never prints anything else and never fails.
• read prints the oldest entry and removes it, or empty.
• peek k prints the k-th oldest entry counting from 1, or oor if k is
• below 1 or above the number of entries currently held. peek removes
• nothing.
• A peek of a position that was destroyed by an overwrite is simply out of
• range. Positions are counted over what is held NOW, not over everything ever
• written.
• c is at least 1, so there is no degenerate ring that can hold nothing.

Problems 176 and 200 are the fixed-capacity queue and deque, and both REFUSE the add when full. That refusal is the easy policy, because nothing is lost and no index moves. Overwriting is the policy a log buffer and an audio ring actually use, and it is the one that forces the oldest position to advance on a WRITE as well as on a read.

## What most people try first

Keep a list, append on write, and remove from the front when it is too long. That is correct and the removal from the front is O(n), because every remaining entry shifts down one place. With q at 2 * 10^5 writes into a ring of 10^5, that is about 2 * 10^10 moves. A peek k on such a list is O(1), so the list is not the wrong shape, only the wrong cost.

## One array, two numbers, and modular arithmetic

buf[0 .. c-1] the storage, never shifted head the index the oldest entry sits at size how many entries are held

write when size < c: buf[(head + size) % c] = v; size += 1 write when size == c: old = buf[head]; buf[head] = v; head = (head+1) % c read: v = buf[head]; head = (head+1) % c; size -= 1 peek k: buf[(head + k - 1) % c]

## Why it is correct

The invariant is that the entries held are exactly buf[head], buf[(head+1) % c], up to buf[(head+size-1) % c], in order from oldest to newest. Every line above preserves it.

A write with room appends at the first unused slot, which is head + size positions along, and raises size by one. A write without room is the interesting case: the slot head holds the oldest entry, which is also the slot the next entry should occupy once that oldest entry is gone, so one assignment both destroys the victim and stores the newcomer. Advancing head then makes the newcomer the LAST element of the window rather than the first, because the window wraps: head + size - 1 with size equal to c is exactly the slot just written. That single step is what the whole problem turns on, and getting it wrong by one makes the ring report entries in the wrong order while still passing a test that never fills it.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. head + size and head + k - 1 reach at most 3 * 10^5, so nothing here needs 64 bits. Note % c must be applied to a non-negative sum: head only ever increases before the modulus, so there is no negative-modulus question, and the answer does not depend on the language's sign convention.

## Cost

O(1) per operation, with memory exactly c entries however long the stream is, which is the reason a ring is used at all.

Constraints - `1 ≤ c ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - `0 ≤ k ≤ 200000` - the ring starts empty - each of `write`, `read` and `peek` must run in `O(1)`, and the memory used must be `O(c)` rather than `O(q)` - the judge cannot enforce either bound: the declared tests are small and there is no test generator yet, so a list that shifts down on every removal passes them while doing about `2 * 10^10` moves at the stated limits