### Lakh's blog

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

• -1

 » 7 weeks ago, # |   0 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
•  » » 7 weeks ago, # ^ |   0 Thanks a lot!!