Minimum no of changes required to make array stric

问题:

I have a problem in which we have an array of positive 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.

Example

if array is 1 2 9 10 3 15

so ans=1 if change 3 to some number between 12 to 14.

if 1 2 2 2 3 4 5

ans=5

since changing 2 to 3 then 2 to 4 then 3 to 5 then 4 to 6 then 5 to 7

Constraints:

Number of elements in array <= 10^6

Each element <= 10^9

Note:

This is not a homework, it was asked in my interview and I was unable to give an algorithm for it.

Can somebody give me an algorithm?

Link to the detailed problem with sample test cases https://www.hackerearth.com/problem/algorithm/find-path/

Since it is mini/max problem, so it sounds dynamic programming to me, but I need help.

回答1:

HINT 1

This is very close to the standard longest increasing subsequence problem which is solvable in O(nlogn).

If you could change the numbers to decimals then the answer would be identical. (Min number of changes = length of string-length of longest increasing subsequence)

However, as you need distinct integral values in between you will have to slightly modify the standard algorithm.

HINT 2

Consider what happens if you change the array by doing x[i]=x[i]-i.

You now need to modify this changed array by making the smallest number of changes such that each element increases, or stays the same.

You can now search for the longest non-decreasing subsequence in this array and this will tell you how many elements can stay the same.

However, this may still use negative integers.

HINT 3

One easy way 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 can also modify the longest increasing subsequence algorithm to have the additional constraint, but this might be harder to code correctly in an interview situation.)

EXAMPLE 1

Following this through on the initial example:

Original sequence

1,2,9,10,3,15

Add dummy elements at start

-5,-4,-3,-2,-1,1,2,9,10,3,15

Subtract off position in array

-5,-5,-5,-5,-5,-4,-4,2,2,-6,5

Find longest non-decreasing sequence

-5,-5,-5,-5,-5,-4,-4,2,2,*,5

So answer is to change one number.

EXAMPLE 2

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.

回答2:

O(nlogn) Running time

import java.util.ArrayList;
    import java.util.Scanner;

    public class Modify_The_Sequence {
        private static int n;
        private static int[] a;
        private static ArrayList<Integer> b;
        private static ArrayList<Integer> c;

        public static void main(String args[]) {
            Scanner d = new Scanner(System.in);

            n = d.nextInt();

            b = new ArrayList<>();
            c = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int x = d.nextInt();
                if (x - (i + 1) >= 0) {
                    b.add(x - (i + 1));
                }

            }

            /*
             * b.clear(); b.add(1); b.add(7); b.add(10); b.add(2); b.add(3);
             */
            // System.out.println(b);
            c.add(b.get(0));
            solve();
            System.out.println(n - c.size());
            // System.out.println(c);
        }

        private static void solve() {
            // TODO Auto-generated method stub
            for (int i = 1; i < b.size(); i++) {
                binaerysearch(0, c.size() - 1, i);
            }
        }

        private static void binaerysearch(int i, int j, int k) {
            // TODO Auto-generated method stub
            int p = (i + j) / 2;
            if (i == j) {

                if (c.get(i) <= b.get(k)) {
                    if (i == c.size() - 1)
                        c.add(b.get(k));
                    else {

                        c.add(i + 1, b.get(k));
                        c.remove(i + 2);
                    }
                } else if (c.get(i) > b.get(k)) {
                    c.add(i, b.get(k));
                    c.remove(i + 1);

                }

            } else {
                if (c.get(p) > b.get(k)) {
                    if (p - 1 > i)
                        binaerysearch(i, p - 1, k);
                    else
                        binaerysearch(i, i, k);
                } else if (c.get(p) <= b.get(k)) {
                    if (p + 1 < j)
                        binaerysearch(p + 1, j, k);
                    else
                        binaerysearch(j, j, k);
                }
            }
        }
    }

回答3:

Changing Longest Increasing Sequence to accommodate for squeezing integral values between two successive increasing elements can ensure that we have integral values at appropriate places.

Modified LIS code:

int convert(vector<int> v){
vector<int> lis(v.size(), 1);  
for(int i = 1; i < v.size(); i++){   
    for(int j = 0; j < i; j++){  
        if(v[i] > v[j] && lis[i] < lis[j]+1 && (i-j) <= (v[i]-v[j]))   
            lis[i] = lis[j]+1;  
    }  
}  
int max_lis = 0;  
for(int i = 0; i < v.size(); i++)  
    max_lis = max(max_lis, lis[i]);  
int ans = v.size() - max_lis;
return ans;
}

回答4:

inspired by the hits of @Peter de Rivaz,

I found the key condition of this problem is : num[i]-i >= num[j]-j >= 0 (i > j).

The following Java code (O(NlgN)) is the slight modification to the standard longest increasing subsequence algorithm, here we skip all the num[i] where num[i]-i < 0.

  static int resolve(int... nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int right = 0;
    for (int i = 1; i < nums.length; i++) {
      if (nums[i] >= i) {
        int realNum = nums[i] - i;
        if (realNum >= dp[right]) {
          right++;
          dp[right] = realNum;
        } else {
          dp[binarySearch(dp, 0, right, realNum)] = realNum;
        }
      }
    }
    return nums.length - (right + 1);
  }

  static int binarySearch(int[] nums, int left, int right, int key) {
    while (left <= right) {
      int mid = (left + right) >>> 1;
      if (nums[mid] > key) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }

回答5:

O(n) Running time:

def min_changes(li):
  change, check = 0, 0
  li_len = len(li)
  if li_len in [0,1]:
    return change
  else:
    check = li[0]
  for i in range(1, len(li)):
    if check >= li[i]:
      li[i] = check +1
      change += 1
      check += 1
    else:
      check = li[i]
  return change