Блог пользователя ivan100sic

Автор ivan100sic, 5 лет назад, По-английски

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...
  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Same problem, same method, same blog: https://mirror.codeforces.com/blog/entry/50036

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

This solution is sick man, just sick. Absolutely don't delete this blog. I wouldn't have discovered it if you had erased it.