Original problem link: https://www.codechef.com/CRK32020/problems/KEVIN
Kevin has an array a consisting of $$$N$$$ elements. He defines an operation $$$f$$$ as maximum of absolute difference between the adjacent elements of the array. If $$$0 \leq N \leq 1$$$ then $$$f$$$ is 0. He wants to minimize the value of $$$f$$$ for the array $$$A$$$. For this, he is allowed to replace at most $$$K$$$ elements of the array with any integer. Help Kevin to find the minimum value of $$$f$$$ for the array.
$$$1 \leq K \leq N \leq 2000$$$
$$$ -1e9 ≤ A[i] ≤ 1e9 $$$
The solutions (https://www.codechef.com/viewsolution/39101909) to the problem are using DP but I'm not able to understand the state transitions. Can anyone help please?
Tbh it's hard to tell without an editorial lol. I'm not sure how to do this problem either, but it would be nice to know.
What I think I'm able to get from the code is that it looks like the author of the code is using binary search where
chk(val)determins whether it is possible to get cost <= val with at most k operations. But theif((abs(a[i]-a[j])+(i-j)-1)/(i-j)<=val)part looks cryptic / beyond me as of now. Anyone have a solution for this problem? (or is there any discussion thread for this problem? I wasn't able to find any with a google search)Yeah, during the contest we were able to come to the fact that it will be solved using BinarySeach+DP but couldn't implement it. Other solutions also follow the same pattern. That (i-j) part is totally going over my head.
So far I couldn't find any editorial or similar problem. I was hoping people here will be able to provide an approach. :P Lets hope someone knows how to solve it.
What I see is, is that we binary search om answer. Let's say if we want to check if $$$x$$$ is the answer.
Let $$$dp_i$$$ be the least number of moves such that $$$i$$$ is unchanged, and all adjacent differences are $$$\le x$$$. Now lets say we want to find $$$dp_i$$$. Let the position of the last unchanged value be $$$j$$$. Then we can have $$$dp_i = dp_j + (i-j-1)$$$, if we can set the values in between in such a way that it satisfies are answer. For each value, we can have a maximum increase/decrease of $$$x$$$. So we need $$$|A_i - A_j| - (i-j-1) \times x \le x$$$. So this dp can be computed in $$$O(n^2)$$$.
$$$i$$$ or $$$A_i$$$ ?
Thanks a lot for the explanation! It seems so easy now.
This problem is an exact copy of https://mirror.codeforces.com/problemset/problem/360/B
Thanks a lot for sharing the source. :)
No, the name of the character is different.
Are there other problems that use a similar kind of idea for transitions (i.e. where your subproblem relies on keeping the right endpoint of your prefix fixed)? I thought this was a cool / unusual kind of problem, and was just curious if this idea shows up in other places.
675E - Trains and Statistic
1327F - AND Segments