Lakh's blog

By Lakh, history, 7 weeks 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

7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For slope trick you should use a priority queue. Otherwise for small N, you can use dp. You can go test out your code here: 713C - Sonya and Problem Wihtout a Legend