pritishn's blog

Help needed in DP transitions for this problem.
By pritishn, 4 years ago, In English

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?

Tags #dp
  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like 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)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i is unchanged

    $$$i$$$ or $$$A_i$$$ ?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for the explanation! It seems so easy now.

    → Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks a lot for sharing the source. :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    No, the name of the character is different.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply