Блог пользователя pritishn

Автор pritishn, 4 года назад, По-английски

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?

Теги #dp
  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 the if((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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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)$$$.

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

This problem is an exact copy of https://codeforces.net/problemset/problem/360/B

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.