1123. Bricks and Ladders

Buildings stand in a row with heights h[0] to h[n-1]. You start on building 0 and may only step to the next one. Stepping from i to i + 1 is free when h[i+1] <= h[i]. Otherwise it costs either ONE LADDER, whatever the difference, or h[i+1] - h[i] BRICKS.

You hold bricks bricks and ladders ladders. Print the furthest 0-based index you can reach.

heights 4 2 7 6 9 14, bricks 10, ladders 2 -> 5 heights 5, bricks 0, ladders 0 -> 0 heights 5 4 3 2, bricks 0, ladders 0 -> 3 heights 1 2 3 4, bricks 0, ladders 0 -> 0

Trace the first line. The climbs are 2 -> 7 costing 5, 6 -> 9 costing 3, and 9 -> 14 costing 5. The steps 4 -> 2 and 7 -> 6 are free. Two ladders go to the two biggest climbs, which are the two 5s, and the remaining climb of 3 is paid in bricks, of which there are 10. Everything is affordable, so the answer is the last index, 5.

## What most people try first

Using a ladder on the first climb that needs one. On the first example that spends a ladder on the climb of 5 at the start and the other on the climb of 3, leaving the final climb of 5 to bricks, which happens to work here with 10 bricks. Make it 4 bricks and the first-come rule stops at index 4 while the correct answer is still 5.

The other instinct is to save the ladders for later "just in case", which stops even sooner.

Trying every way of allocating the ladders costs n choose ladders.

## The method

Walk forward and keep the climbs paid for by LADDERS in a min-heap. Whenever the heap holds more ladders than you own, the smallest of them is demoted to bricks.

heap = empty min-heap of climb sizes for i from 0 to n-2: climb = h[i+1] - h[i] if climb <= 0: continue push climb if size of heap > ladders: bricks = bricks - pop the smallest if bricks < 0: answer is i print n - 1

Each climb is pushed once and popped at most once, so O(n log n).

## Why demoting the smallest is correct

The invariant is: after processing the first i steps, the ladders sit on the ladders LARGEST climbs among them, and the bricks have paid for the rest, which is the smallest possible brick bill for reaching index i.

Reaching index i at all requires paying for every climb among the first i steps, and the only choice is which ladders of them the ladders cover. The brick bill is the total of the climbs minus the ones the ladders cover, so it is smallest exactly when the ladders cover the largest climbs. That is the exchange: swapping a ladder from a smaller climb to a larger one lowers the brick bill by the difference and changes nothing else.

The heap performs that swap online. When a new climb arrives and the ladders are already all in use, the smallest climb currently on a ladder is the one that should give it up, and it becomes a brick cost.

Reporting index i the moment the bricks go negative is right because the invariant says no cheaper allocation exists for reaching i + 1, so i + 1 is unreachable, and every index beyond it needs at least as much.

## The boundary that breaks a careless implementation

A step DOWN or to the same height is free and must not enter the heap. Pushing a non-positive climb wastes a ladder on nothing, and on 5 4 3 2 with no equipment it reports 0 instead of 3.

The failure is reported as i, the index you are standing on, not i + 1. Off by one here is the commonest wrong answer.

ladders may be 0, in which case every climb goes straight to bricks, and it may be at least the number of climbs, in which case the bricks are never touched. Both are in the tests.

## Sizes

n reaches 10^5, heights reach 10^9, and a single climb reaches 10^9. The bricks start at most 10^9 and only ever fall, so the brick counter stays between -10^9 and 10^9. Every one of those fits in a signed 32-bit integer, whose limit is 2147483647, so nothing here needs 64 bits. That is worth stating, because the neighbouring problems in this block all do.

## A related problem

Problem #1122 is the other "look back with a heap" problem here, and the difference is which end the heap is keyed at: there you take the LARGEST thing you passed, here you give up the SMALLEST thing you are holding. Both are the same trick of deciding late rather than early.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ bricks ≤ 1000000000` - `0 ≤ ladders ≤ n` - `0 ≤ h[i] ≤ 1000000000`