Let's look at the following DP: $$$d_{i,j,k}$$$ is the largest expected value if we used $$$j$$$ Poke Balls and $$$k$$$ Ultra Balls on the first $$$i$$$ Pokemon. There are four transitions from each state, corresponding to whether or not we used or didn't use a Poke Ball and an Ultra Ball on the $$$i$$$-th Pokemon. Clearly this solution has time complexity $$$O(n^3)$$$. However, if we shuffle the input, the optimal solution (imagined as a path through the 3D DP space) will not deviate much from the straight line connecting $$$(0,0,0)$$$ and $$$(n,a,b)$$$. If we only compute DP values inside a "tube" with some radius $$$r$$$ containing this straight line, it will have very high probability of containing the optimal solution, so the computed solution will be correct. By "tube", I mean the set of points $$$(i,x,y)$$$ such that $$$|x - \frac{ia}{n}| \leq R$$$, and $$$|y - \frac{ib}{n}| \leq R$$$. The complexity is $$$O(nr^2)$$$. Right now I don't have a rigorous proof but I think that in general a good value for $$$r$$$ is on the order of $$$\sqrt n$$$, which leads to an $$$O(n^2)$$$ solution.
For this problem, I originally used $$$r = 128$$$, however, even $$$r = 32$$$ worked and $$$r = 16$$$ only failed on the 84th testcase. Note that this approach does not depend on testcases being "weak". No matter what the testcases are, a lower bound on the probability of success can be computed.
Same problem, same method, same blog: https://codeforces.com/blog/entry/50036
Heck, guess this is another thing that I discovered independently
Should I delete this blog then?
idk, find another problem that is solvable with this method and add it to the blog :D then it's brand new and valuable
And now I am very surprised by just how much our posts look alike :P
Anyway I think I have an idea for another problem which can be solved using this technique, I'll write about it a bit later
But why it will always be correct, since u r taking about proability there can also be some probability that answer will be out of radius r. ivan100sic
It won't always be correct, but it will be correct with very high probability, independent of the testcases, as long as the used shuffle function is sufficiently good.
I love this trick, it's really nice. I think you shouldn't delete this blog. People who didn't know about it (like me) can notice it now.
This solution is sick man, just sick. Absolutely don't delete this blog. I wouldn't have discovered it if you had erased it.