1048. Nudging the Row Into Increasing Order
A row of n non-negative numbers is given. One move adds 1 to any single
entry; entries may never be lowered. Print the fewest moves that make the row STRICTLY
increasing, so every entry is larger than the one before it.
1 1 1 -> 3 becomes 1 2 3
1 5 2 4 1 -> 14 becomes 1 5 6 7 8
1 2 3 4 -> 0
7 7 -> 1
## What most people try first
Repeat until the row is legal: find the first place where a[i] <= a[i-1] and add 1 there.
That terminates and gives the right answer, and the answer itself reaches 10^14, so the
number of loop iterations does too. It is the brute force this problem was checked against, on
tiny inputs only.
The second instinct is a table over "what value does entry i end up at", which is a table
over 10^9 columns.
## Each entry is pinned by the one before it
Sweep left to right carrying prev, the value the previous entry ENDED at.
prev = a[0], ops = 0
for i in 1 .. n-1:
if a[i] > prev:
prev = a[i] already legal, leave it alone
else:
ops += prev + 1 - a[i]
prev = prev + 1 raise it to the smallest legal value
## Why raising to the smallest legal value is right
Two halves.
It is FORCED to be at least prev + 1, because entry i must exceed entry i-1, and
entry i-1 has already been fixed at prev.
And raising it any HIGHER is never better. Suppose an optimal answer ends entry i at some
v > prev + 1. Lower it to prev + 1. The entry before is still smaller, and the entry
after was required to exceed v, which it still does because prev + 1 < v. So the row is
still legal and the total has fallen by v - (prev + 1), contradicting optimality. Every
later entry may also then be lowered, which only helps.
So the greedy choice at each step is the unique smallest legal one, and no later step is harmed by it. That is the exact sense in which a local choice "does not foreclose", and it is what has to be argued rather than assumed.
## The first entry is never raised
prev starts at a[0] itself. Raising the first entry can only make later entries more
expensive, so it is never done, and a version that starts prev at -1 or at 0 and then
"fixes" a[0] produces the wrong total on 1 1 1.
## Overflow
With n at 100000 and a[0] at 10^9, a row of 10^9 followed by zeros costs about
10^14 moves, which is fifty thousand times the signed 32 bit limit of 2147483647. The
running total must be 64 bit, and so must prev, which climbs past 10^9 as soon as the
row is long.
The short test 1000000000 0 0 0 already totals 3000000006, which wraps a 32 bit
accumulator to a negative number. Three zeros is the fewest that will do it: two zeros total
2000000003, which still fits.
## Cost
Time O(n). Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated non-negative integers.
Output
Print one integer alone on a line: the fewest single-unit increments needed to make the row strictly increasing. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.