Hi everyone!

I've just solved 739E - Gosha is hunting in an easy but interesting way. However, it's quite different from what's described in the editorial, and I couldn't find any accepted codes that use this approach. That's why I'm curious if anyone solved this problem like me, and if this is a well-known trick :)

First, there's an easy O(n³) DP solution to the problem: for each (i, x, y) compute the best score using x PokeBalls and y UltraBalls on i first Pokemon.

How to improve it? Let's randomly shuffle all Pokemon. If we looked at the first i of them, then we'd expect to use around PokeBalls, and UltraBalls there (a and b are the total amount of balls of each type), because the places where we used them in the optimal solution are now randomly distributed... even though positions where we use PokeBalls are not independent from positions where we use UltraBalls.

Now, using some random walk properties we can (I hope!) say, that it's really unlikely that we'll deviate from those expected values by more than . So we can just do the brutal DP, but constrain ourselves to x and y from a specific range of size . After that the solution is O(n²) and get's accepted: 24153740

All opinions are welcome. Thanks :)