Wqs Binary Search and other advanced DP optimisations

help
, , ,
#1

Can someone please point me to a good resource for higher-level DP optimizations with proofs for applicability conditions? I can’t find a formally reasoned proof for a lot of these things, anybody who is aware of these techniques, can you please point me to resources that helped you wrap your head around these things.

I’m aware of CHT. I am looking for links to understand wqs binary search (also known as Aliens trick), Knuth Optimization, and Divide and Conquer Optimization, and possibly others I haven’t heard of.

Thanks in advance.

2 Likes
#2

I think @galencolin @everule1 @carre will help u.

1 Like
#3

https://codeforces.com/blog/entry/8219

For wqs binary search, the easiest way to understand is you have a function f(x), and you want to find value at f(k). As an example consider maximum sum of at most k subarrays. So f(x) is the maximum sum if you are allowed x subarrays.

Now the condition you need is f(x+1) - f(x) \le f(x) - f(x-1) . As in, increasing x gives you diminishing returns. Now we binary search on the minimum increase we are willing to take. Instead of storing dp_{i,j}, We store
\{max(dp_{i,j} - jC), \arg\max_{j}(dp_{i,j} - jC)\}. These transitions can be done in O(n). now we binary search on C, to find C at which we use k of something. As you can see, C is basically the minimum gain we are willing to take for an increase in k.

Now to prove that it is convex for this example. This is basically finding maximum alternating - + sequence on the prefix sums. Now you can show that there is a for every best sequence of k + and -, there is a best sequence of k-1 + and -, that is a subset of that. This is shown by contradiction, and a bit of casework. And then you can show that this will obviously be convex, by removing least gap between some adjacent + and -.

2 Likes
#4

Hey Aditya. Thanks for the explanation. I have read a few blogs on wqs binary search. The intuition is clear but none of the blogs seem to cover the proof of convexity of the functions used in problems. I found a general method of proving the convexity/concavity of these functions (probably not very useful in a contest but theoretically enriching) in a very nice comment on CF.

Any cool problem suggestions on this topic ?

#5

Hey Aditya. I have a small implementational doubt. I have made two submissions to a CF problem using WQS binary search with very little modification. The modification is in the part of the calculation of the final answer. It has to do with the trick itself rather than the problem specifics, but if you want, you can go through the problem details as well. One solution gives WA, the other passes.

WA solution
AC solution

Note MaxPlace(a, b) in the code is equivalent to a = max(a, b).

The solution that actually gives WA was my initial attempt and to me, it is the more correct answer. But for some reason, CF disagrees with me. To get to AC I referred to someone else’s solution. I don’t quite understand why the original solution that I submitted is wrong. Thoughts?

#6

The real problem happens when you have f(x + 1) - f(x) = f(x) - f(x-1). dp[a].ss may never be equal to b here. Look at this.

To take care of that, you have to explicitly use b as the number of ultra balls. Obviously, when we use fewer ultra balls, this may cause it to be larger than the real answer, which we’ll have at the end, So we have to assign the value, and not take maximum.

#7

In the AC solution, if the last round comes from >b ultra balls case, we can say that we are overshooting the answer. Since we used > b ultra balls and then removed the penalty for only b of those ultra balls, the answer that we obtain this way is clearly more than the actual answer isn’t it? If it were <= the real answer, the real answer with a penalty for b ultra balls would have been an option and that would be chosen ahead of this one since the best answer is chosen by a pair of the (expected value with the penalty, -(number of ultra balls used)).

Actually using more ultra balls is actually always strictly better, coz we have more of a chance to catch pokemon. So maybe what is happening is we are always getting more than b ultra balls near the end. The penalty value for using lower than b ultra balls is very hard to achieve I guess because of precision issues?

In general, does the convexity of function f guarantee theoretically that there will be a penalty point on either side of which you use >b and <=b ultra balls for all reasonable values of b (between 0 and n)? I think it does but the issue occurs because we aren’t able to attain that value because of the limitations of computer decimal representations. Am I right?

#8

Thing is, it doesn’t matter if you use >b ultra balls and removed the penalty for exactly b ultra balls it is still correct.

Ok let us define it the problem better. We are binary searching for C = f(b) - f(b-1), where f(x) is the optimal answer for x ultra balls.

Now, we know f(x+1) - f(x) \le f(x) - f(x-1).

Next let us define l and r.
l is the smallest value such that f(l) -f(l-1) \approx f(b) - f(b-1).
r is the largest value such that f(r) - f(r-1) \approx f(b) - f(b-1).

We know l \le b \le r.

So when we choose some C < f(b) - f(b-1), we will get optimal number of ultra balls <l, and so we will increase C, and vice versa.

So we know that C \approx f(b) - f(b-1) at the end. Now, because they are almost equal, we may get the optimal number of ultra balls, l \le U \le r.

Remember, that we are storing max(f(k) - kC). Recall that for all i,i+1, such that l \le i \le r, and l \le i+1 \le r, f(i+1) - f(i) \approx C.

That means f(i+1) - C = f(i), and f(i+1) - (i+1)C = f(i) - iC.

So it doesn’t matter what value U has between l and r. F(U) - UC = f(b) - bC, so F(U) - UC + bC = f(b).

https://www.desmos.com/calculator/7hozjympgv
Try this. Remember, you are calculating the maximum value and when it happens, and you are trying to change C so that the maximum is at b.

1 Like
#9

This post was flagged by the community and is temporarily hidden.

#10

Nice. That helps a lot. If you have some time maybe you should write a blog about this technique and the implementation details that come with it, will probably be pretty useful to people. Until then, I will recommend people to just read this thread to understand the finer implementation details. Thanks again.