ivan100sic's blog

By ivan100sic, 2 years ago, In English

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...
 
 
 
 
  • Vote: I like it
  • +69
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Heck, guess this is another thing that I discovered independently

    Should I delete this blog then?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      idk, find another problem that is solvable with this method and add it to the blog :D then it's brand new and valuable

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it +44 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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