I'd try to do a binary search on answer and check correctness in the following way: iterate an array from left to right and if you see some element a_i such that a[i] <= a[i-1], then you assign a[i] to a[i-1]+1. And just count a number of such assignments.

If my idea is incorrect, please, provide a counter-example.

Oops, found: 3 1 2 3 4 5

Sorry.

Here is also an O(NlogN) solution. If the answer was to make non-decreasing array with minimum number of moves than that would just simply be N — longest_non_decreasing_subsequence(call it LIS for easy reference from now on).

Now, to make a strictly increasing array note that for every element at index i (starting from 1) there must be at least i-1 numbers less than it, this simply means for every i, a[i] > i — 1. If a[i] <= i — 1 then we have to change that number.

So now all we have to do is find LIS while ignoring those a[i] such that a[i] <= i — 1. Or to put it more formally:

1) make array b such that b consists only of those elements a[i] such that a[i] > i — 1, preserving order of course.

2) find LIS (longest increasing subsequence of b) in O(NlogN) time (it's easily googlable).

3) answer is N — LIS. N here is length of array a.

Test cases:

N = 5

a[] = 1 2 2 3 4

b[] = 1 2

length of LIS = 2

answer = 5 — 2 = 3

N = 6

a[] = 1 7 10 2 20 22

b[] = 1 7 10 20 22

length of LIS = 5

answer = 6 — 5 = 1

tl;dr Find LIS while ignoring those a[i] such that a[i] <= i — 1, answer is N — LIS.

@YellowNextYear i think b will be :[99,98] as formed by taking a[i]-i , so LIS will be 1..

thanks got it!!!

@c0d3junki3 i think the array b will be formed by taking a[i]-i for all a[i]>i-1...

thanks!!

There is an interesting solution — it's enough to find the longest increasing subarray in a new array, which is maked by the rule: b[i] = a[i]-i, where a[i] is the element of initial array. The answer will be the difference a.size — l.size, where l — the longest increasing subarray.

http://mirror.codeforces.com/blog/entry/56332