Q1.
You are given an array of N integers. Suppose you are allowed to change an element into any integer with one operation. Find the minimum number of operations to make the array strictly increasing. (Note that the elements can become <1). The given array contains N positive integers.
- 1 ≤ N ≤ 10^5
- 1 ≤ ai ≤ 10^9 for 1 <= i <= N
Example:
1) N = 5
1 2 2 3 6
Sol: 1 2 3 5 6. So the answer is 2
2) N = 3
1 1 1
Sol: −1 1 2. So the answer is 2
3) N = 6
4 2 4 4 6 8
Sol: 1 2 4 5 6 8. So the answer is 2
4) N = 7
1 2 2 2 3 4 5
Sol: -1 0 1 2 3 4 5. So the answer is 3.
Here is how we can solve this problem:
Suppose the problem was simply named Non-decreasing Array. Obviously, you want to keep as many numbers as possible unchanged. It follows that you can select the longest non-decreasing subsequence and modify all the other elements so that they'll respect the rule (by making them equal to values from the subsequence we've extracted accordingly). Back to our problem now, we're looking for a Strictly Increasing Array. If we make another ci = ai - i, the answer is the equal to (n - the longest of the non-decreasing subsequence with no negative number) and for the longest non-decreasing subsequence, a O(nlogn) solution can be used.
Why does this work?
Consider for some i and j, ci <= cj then ai - i <= aj - j that implies ai + j - i <= aj , which means we have enough space to fit a strictly increasing array between i and j.
Q2.
Now consider the same problem but with the condition that the resulting sequence should only contain positive integers.
Here is how we can solve this problem:
For each element of the modified(or resulting) sequence we have bi >= i (1<=i<=n) and we need to find the longest increasing subsequence of the original sequence ai and ai >= i. We keep such ai unchanged and other values can be changed into the value as their index.
Then we should modify the above solution such that we have to consider longest non-decreasing subsequence only among those numbers such that ai - i >=0 but not the whole array ci. This ensures that the resulting array has the integers which are positive and forms strictly increasing sequence. Because in this way we make sure that all the elements such that ai < i initially have to be changed.
Another way is to modify the algorithm to only use positive numbers is to append a whole lot of numbers at the start of the array .i.e. change 1,2,9,10,3,15 to -5,-4,-3,-2,-1,1,2,9,10,3,15. Then you can be sure that the optimal answer will never decide to make the 1 go negative because it would cost so much to make all the negative numbers smaller. You only need to add N dummy nodes (the same as the length of the sequence, not the maximum number i.e 10^9 ).
Example:
Original sequence 1,2,2,2,3,4,5
Add dummy elements at start -5,-4,-3,-2,-1,1,2,2,2,3,4,5
Subtract off position in array -5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6
Find longest non-decreasing sequence -5,-5,-5,-5,-5,-4,-4,*,*,*,*,*
So answer is to change 5 numbers. 1 2 3 4 5 6 7
[REF.]
https://www.codechef.com/SMHT2014/problems/SMHTD
https://www.hackerearth.com/problem/algorithm/find-path/
