codeshaker's blog

How to solve this problem??
By codeshaker, 11 years ago, In English

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!!!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

thanks got it!!!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

thanks!!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.net/blog/entry/56332

→ Reply