Minimum changes required to make a given array strictly increasing

Question

I am trying to solve this problem of SPOJ http://www.spoj.com/problems/DOSA which is also a question of some interview.

My logic is from the given array take the elements which satisfies a[i]>i (0 based indexing) since others always need to be changed.

Now find the Longest Strictly Increasing Sub Sequence from these selected elements and the final answer is original length of the array-calculated LIS example : the original array is : 1 7 10 2 20 22
The new array calculated as per a[i]>i is 1 7 10 20 22

Now, the LIS of this array is 5
So, the final answer is 6-5=1
but its giving Wrong answer can anyone point me out where is my logic wrong.

EDIT: Problem Statement : Lalith is going to have dinner and he has N dosas in front of him with their prices represented by sequence of integers a1,a2,a3...an.

And he has decided to eat in a different manner . You are free to replace the price of any dosa with any positive integer.

How many prices(integers) must be replaced to make the resulting sequence strictly increasing?

Sample Input : 6

1 7 10 2 20 22

Sample output : 1

Answer 1

Your reasoning might be a bit flawed.

Consider the following example:

10
2 3 4 2 5 6 7 8 9 10

Here, the answer is 4 (one needs to change the first 4 inputs), but according to original poster's logic, if we strip out:

A[i] less than or equals i

we'll get a residual list of numbers:

2 3 4 5 6 7 8 9 10

which obviously gives an answer of 1 if LIS is directly applied to it (the entire sequence is strictly increasing, and you are discarding only A[3] in the original array)

Approach

My approach would be as follows:

1. Try to build LIS. That is, keep an array A[i], such that A[i] = lowest i-th item in an increasing subsequence found so far that ALSO obeys the law that its index in the input array of the value of A[i] has a difference with index of A[i-1] such that:

   • The difference between their respective values is >= this difference of their indices in the original array. If that is not the case, then unfortunately one can't squeeze in integral values in between them.

   • As a special case, if i is 0, that is it is first item in the LIS array, then it is mandatory that its value be > its index in the input array (your logic does apply here)

2. For each item, binary search for greatest item which is less than the current input item AND that satisfies point#1 above. One can always binary search like this because if the premise holds for a certain value, then it recursively holds for ALL value less than the current binary search value under consideration.

I pass test cases with this approach.

---

[Edit]: Adding more explanation since comment section won't allow verbose comments.

Detailed explanation

Let LIS[] be the LIS that we maintain. Then after **ALL** Dosas have been processed, the final answer = N - size(LIS)

Now, the challenge boils down to find how to create and maintain this array -> LIS, that too efficiently. It can be done in O(N^2), but that will timeout for a large N, possibly with value upto 10^6. We'll try to solve it in O(N*log(N))

Proposal

I propose the following invariant:

Let LIS[i] = 2-tuple (pair) containing price of Dosa that is just (minimally possible value) higher than value of Dosa at LIS[i-1] and whose "index difference" with Dosa at LIS[i-1] is less than or equal to "price difference" with Dosa at LIS[i-1]

That is, if: LIS[i-1] = pair(a,b), where a = value of Dosa and b = its index in original input array

Then the following must hold:

If LIS[i] = pair(u,v), where u = value of Dosa and v = its index in original input array

Then the following should always hold true:

1. u > a (i.e., price of Dosa in LIS[i] must be strictly greater than value of Dosa at LIS[i-1]. Why? Well, that's what we want in the first place, don't we? A strictly increasing sub sequence)

2. u - a ≥ v - b (Now, you might need to ponder a little bit why this MUST hold)

Consider a contradiction. Let's say, u - a < v - b. Then there is no way you can uniquely fit in Dosas between indices b and a in the original array. Since it would require at least one duplicate Dosa by Pigeon Hole Principle.

Now, the above properties lend themselves beautifully to binary search. Why? While trying to fit the current Dosa (from the original array) in the LIS at a certain position by comparing it to the elements in the LIS, say, with pair value (u, v).

The following conditions should satisfy for the dosa to be an element in the LIS.

1. Current Dosa value > u (because we want strictly increasing sub sequence)

2. Difference between their indices should be less than or equal to difference between their Dosa values (as explained in #2 above)

If this doesn't hold, then we are sure that either of the following is true:

1. Either the current Dosa value <= u or,

2. The Index diff between current Dosa and the Dosa at binary search position (value v) < their respective Dosa value difference

If it is #1, then we need to search on the left partition of the LIS through binary search (since we've gone too far to the right)

If it is #2, then even if current Dosa value > u, even by going right. It means the current Dosa value is u + d (d = a[i] - u), so, the magnitude of the index difference must be at least v + d. Hence, there is no way it can have the index difference <= value difference by continuing proceeding towards right. So, we must stop and search in the left partition.

[Pause. Read again if it's still unclear]

---

[EDIT]: SPOILER - Adding working code (scroll to uncover)

[Sorry, I was unable to add code here without getting "Your post appears to contain code that is not properly formatted" errors. So, putting ideone.com link]

Sample code here: http://ideone.com/tPkUWk
[Edit]: I don't want to spoil for others, so I'm making the code private.