I came across an interesting problem while giving Junglee CodeFest at HackerEarth. I could not solve the problem in the contest. Is anyone up with any approach?
Given an array arr of N integers. Each array has some hardness
hardness = max abs(arr[i+1]-arr[i]) for all 1<=i<=N-1
And hardness = 0 if N<=1
You are given a number K you can change at most K elements of the array. You have to minimize the hardness of the array
Both N and K were less than 2000
Array elements are less than 1e9
Give the problem's link
Since it was a hiring contest. So the problem link is not public.
It can be seen that in the case of replacing one element of the array, one of the most optimal options will be the average of its two neighbors (a, b, c -> a, (a + b) / 2, c), then the hardness of the array decreases by (( abs(a-b)+abs(b-c))-abs(a-c)). Such a replacement is equivalent to removing the element b from the array. Probably, such an analogy can be extended to the entire array, then the task is reduced to choosing N-K elements of the array, which we will not delete, with the minimum difference of neighboring elements, which, under such restrictions, can be solved by dp[N-K][N-K]. Complexity — O(N^2)