Find the minimum cost

Given an array of integers, find the minimum cost to make the array either increasing or decreasing(not strictly).

Cost is defined as absolute difference of the old value of the element and the new value of the element.

Ex: 9 8 7 2 3 3
Minimum Cost: 1
In the above array, 4th element ‘2’ can be changed to ‘3’ to make the array decreasing. So cost = abs(3 - 2) = 1.

Ex: 10 6 3 2 2000
Minimum Cost: 11
1st element 10 can be changed to 6. Cost = abs(10 - 6) = 4.
3rd element 3 can be changed to 6. Cost = abs(3 - 6) = 3.
4th element 2 can be changed to 6. Cost = abs(2 - 6) = 4.
So total cost = 11

No. of elements: 10^4
Range of elements: [1, 10^9]

This question was asked in a contest(which is now over) and I wasn’t able to solve it. Please help.

Edit: As @ganesh92 pointed out, this question was asked in a closed Hackerrank hiring test. So, unfortunately I don’t have the actual link to the question.

always state where is this ques frm
otherwise how can we make sure that its not from any ongoing contest

Maybe this can give you some insight:- https://www.geeksforgeeks.org/convert-to-strictly-increasing-integer-array-with-minimum-changes/

@anon55659401 I think my question is a different than what is there in this link. In geeksforgeeks link, “change” is reffered to as number of elements being changed, in my question “change” is defined as cost which is difference between the value of old element, and value of new element. I tried thinking in terms of counting the number of increasing and decreasing ranges, but it didnt help(take the two examples that I provided for reference).
I also thought of this LIS/ LDS during the exam, but couldn’t figure out how to take it forward.

I think dynamic programming is the answer; I’ll post it when I come up with the answer :slight_smile:

Yup, somewhere dp is involved. Greedy will give us wrong answers(2nd example itself). I’m pretty confused as to keep what in the state though.

1 Like

Solution to your problem : - https://codeforces.com/contest/713/problem/C :slight_smile:

1 Like

Thank you so much. But how should we decide whether to make the array increasing or decreasing? Should we calculate for both the cases and then compare? Or can there exist a more efficient approach?

Also I saw some submissions for this problem. Given an array A, what does (A[i] - i) help achieve? Almost all of the solutions I saw everyone stored the array in this way. No one stored the original value.

Do both of them separately. Answer=min(x,y) :slight_smile:

1 Like

I haven’t checked the solution yet…Will solve it after 2-3 days :slight_smile:

1 Like