cadmiumky's blog

By cadmiumky, 4 months ago, In English

Note: Treat this post as a joke. Or don't. It's really up to you. but whatever you do please don't downvote thx

Earlier this day, I attempted to solve 1537/E2 Erase and Extend (Hard Version). And I succeeded. But my main issue is the fact that I succeeded, because I feel that my solution (or my underlying proof) does not cover all possible situations (and as it appears, neither do the system tests). My solution can be found here.

The point of this blog is the following: If someone finds a rigourous mathematical proof that my solution is correct, or someone uphacks* it, they are bound to win a fruit eclair. They who find the solution will eventually have to share their PayPal account so I can wire their money for the respective product.

Good luck! Also, did you know KFC costs twice as much in Romania as it does in Russia?

*: as much as it appears to be impossible to uphack (at least at this time), consider uphacking just finding a counter-example

  • Vote: I like it
  • +28
  • Vote: I do not like it

4 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

This is a much simpler solution than the tutorial, though it was coded weirdly (for loops starting at 1<=k, and i is always minn)

So for the proof: From the tutorial we know that it must duplicate a prefix of the string. Then we go into the first loop of the code. If you find the jth character less then we always include it in the prefix because it makes it less. Also, if the jth character is greater than the corresponding character in the current best prefix, we cannot get a better prefix (this is also in the tutorial). Finally, if it's the same, that prefix (just stopping there) is either the same or worse than the current best prefix, so we don't set the new best yet. (If you have like bb or bbb or something then it's the same, if you have like bab then it's worse cuz babbab > bababa.)

This greedily always produces the current best prefix at every position so it works.

  • »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Not meaning to be a prick: it's just math. "rigourous" math

    How do you prove later equalities will always happen? I mean, intuitively it may look correct, but one could point out that similarly it is the case with the Jordan Curve Theorem -- the statemnt trivial and it intuitively is correct, but getting there is apparently somewhat hard. And I'd like that "hard" in this proof.

4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Try reading this comment.