Lakh's blog

Minimum no. of operations to make array strictly increasing
By Lakh, history, 4 years ago, In English 
An array of length N is given . In one operation we can increment/decrement any array element. We have to find minimum no. of such operations to make array strictly increasing.

For e.g. N = 5
         5 4 3 2 1
         Ans: 12

I tried this problem using concept known as Slope trick where first we convert all array elements in following fashion : A[i] = A[i] — i;

After this I tried finding LIS of new sequence and then updating the elements which are not a part of LIS. However, there may be multiple LIS sequences present in the tranformed array. In that case how to decide which sequence to take.

Also let me know if my approach is correct or if any other approach is there to solve this task. Thanks in advance :)

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know how to do it???

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    This problem is same as this.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain what is the intuition behind +1,-1

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Sorry for the late reply. I had misread the original problem. I have added a link to the original problem from where you can read its editorial.

        → Reply