I have a problem in which we have an array of numbers and we have to make it strictly increasing by making zero or more changes to the array elements.

We are asked the minimum number of changes required to make the array strictly increasing.

problem link : http://www.codechef.com/SMHT2014/problems/SMHTD

Thanks!!!

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.

What about this test case

N=3

a=[100,1,101]

b=[100,101]

length of LIS = 2

answer=3-2=1 ... Which is wrong i think ... answer should be 2

Im sorry i didn't mention that you should subtract i-1 from elements, this assures that you filled that many elements before it.

Here is my solution btw http://ideone.com/R7n6Hn

(this is the same problem, so you can test your solutions) http://www.spoj.com/problems/DOSA/

You should be doing

It is faster.

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

thanks got it!!!

Yeah i think it makes more sense like that.

@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://codeforces.com/blog/entry/56332