Fewest Changes to Make It Increasing
One operation replaces any element with any integer, positive or negative. Print the fewest operations needed to make the array STRICTLY increasing.
1 5 3 4 -> 1 change the 5 to something below 3, such as 2
3 2 1 -> 2 only one element can be kept
Counting the changes directly is awkward, so count what you KEEP instead and subtract. Minimising changes is maximising the number of untouched elements.
## When a set of keepers is legal
Suppose indices i < j are both kept, with no kept index between them. The j - i - 1
positions between them must be filled with strictly increasing integers strictly between
a[i] and a[j]. That is possible exactly when
a[j] - a[i] >= j - i
There are j - i - 1 slots and the values must all differ by at least 1, so the gap has
to be at least j - i.
Nothing constrains the ends. Before the first keeper any number of strictly increasing
integers below a[i] is available because integers run downward without limit, and the
same holds after the last.
## The transform
Rewrite the condition:
a[j] - a[i] >= j - i becomes a[j] - j >= a[i] - i
So set b[i] = a[i] - i. A set of keepers is legal exactly when the corresponding
b values are NON-DECREASING.
The largest legal set of keepers is therefore the longest non-decreasing subsequence of
b, and
answer = n - (length of the longest non-decreasing subsequence of b)
Every trace of the original problem is gone. That is what makes this worth studying: the work was entirely in finding the right thing to measure.
## Non-decreasing, not increasing
b is compared with <=, not <. The original values are strictly increasing but the
index subtraction absorbs exactly the strictness, so equal b values are legal and
correspond to consecutive kept indices differing by exactly the index gap.
4 2 4 5 6 is the test for this. It answers 1: b is 4 1 2 2 2, whose longest
non-decreasing subsequence is 1 2 2 2 of length 4. With strict comparison that drops
to 2 and the answer comes out as 3.
## Cost
The O(n^2) version is a direct double loop. For n = 200000 use the patience
scan: keep the list of smallest achievable tails and place each b[i] with an
UPPER-bound binary search, which is what admits the equal case. A lower-bound search
there silently computes the strictly increasing version.