I was solving this problem and I came up with an interesting idea which may in some cases be generalized to other DP problems. I don't think it's well known so that motivated me to write this.
Once you've read the problem, understood it and want to know what I did, continue reading...
Same problem, same method, same blog: https://codeforces.me/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.