Memory Manager

Key observation

This is pure simulation. Full stop. With $t,m \le 100$, anything asymptotically fancy is just showing off to the wall.

So we model the memory exactly as it is described.

Let mem[i] denote byte $i$ of memory:

• 0 if the byte is free,
• the block id otherwise.

Also keep:

• alive[id] — whether this identifier currently refers to a live block,
• nextId — the next identifier to give to a successful alloc.

That is enough.

alloc n

We need the leftmost free segment of length $n$.

A left-to-right scan with a running count of consecutive free bytes does the job:

• if mem[i] == 0, increase the current free-run length,
• otherwise reset it to $0$.

The first time the run length becomes $n$, we found the earliest valid segment. Its start is

$$start = i - n + 1.$$

If no such segment exists, print NULL.

Otherwise:

1. fill mem[start ... start+n-1] with nextId,
2. mark alive[nextId] = true,
3. print nextId,
4. increment nextId.

And yeah, unsuccessful allocations do not increment the id counter. That little detail is where people randomly trip and eat dirt.

erase x

An erase is legal iff $x$ is the id of a currently alive block.

So it is illegal when

$$x \le 0 \quad \text{or} \quad x \ge \text{nextId} \quad \text{or} \quad \neg alive[x].$$

In that case, print ILLEGAL_ERASE_ARGUMENT.

Otherwise:

• set alive[x] = false,
• scan the whole memory and replace every occurrence of $x$ with $0$.

Because each live block occupies one contiguous segment, this removes exactly that block.

defragment

After defragmentation, all occupied bytes must be moved as far left as possible, while preserving the order of blocks.

The easiest way to think about it: just remove all zeroes from the memory array and keep the nonzero values in the same order.

Example:

$$[1,1,0,2,2,2,0,3] \rightarrow [1,1,2,2,2,3,0,0].$$

An in-place stable compaction does exactly this:

• keep a write pointer w = 0,
• scan i = 0..m-1,
• whenever mem[i] != 0, write mem[w++] = mem[i],
• after the scan, fill mem[w ... m-1] with 0.

Why does this preserve block structure?

Because before defragmentation, memory is a sequence of contiguous block-runs separated by zero-runs. Removing all zero-runs simply concatenates the block-runs in the same order. No block gets reordered, and no block gets split. Nice and clean.

Correctness sketch

We maintain this invariant after every operation:

1. each live block id appears in mem as one contiguous segment,
2. alive[id] is true iff that block exists and has not been erased,
3. free bytes are exactly the positions where mem[i] = 0.

Now check the operations:

• alloc writes one new contiguous segment into the leftmost valid gap,
• erase removes exactly one existing segment,
• defragment deletes all gaps while preserving the order of occupied bytes.

So every operation matches the statement exactly.

Complexity

Each command scans at most $m$ bytes, so each one costs $O(m)$. Hence total complexity is

$$O(t \cdot m).$$

Given $t,m \le 100$, this is at most

$$O(10^4),$$

which is hilariously small.

Memory usage is $O(m + t)$.