nikolapesic2802's blog

By nikolapesic2802, history, 7 months ago, In English

Hello Codeforces!

I want to tell you about a little trick I discovered during Codeforces Round #649, and more specifically, while solving problem E - X-OR.

During the contest, I made a random solution that doesn't have the greatest of chances to pass on it's own. The problem was that it used too many queries when it gets unlucky with random index selection. In my next submission, I added a counter for the number of queries, and a while(true) loop if it exceeds the number of queries.

By doing this, the verdict will be Time Limit Exceeded and not Wrong Answer. Because of how Codeforces works, when a code gets TLE, it will rerun the code several times to see if the code is on the edge of the time limit. By doing this you increase the chances of your code passing significantly! Without this while loop, my code passed 0 out of 10 times, and with it, it passed 5 out of 5 times!

I'm not sure how useful this actually is, but I found it interesting so I'm sharing it, enjoy!

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

»
7 months ago, # |
  Vote: I like it +161 Vote: I do not like it

I hope that codeforces will not have tasks that use it in author's solution ;_;

»
7 months ago, # |
  Vote: I like it +121 Vote: I do not like it

this is genius

»
7 months ago, # |
  Vote: I like it -64 Vote: I do not like it

Congratulations, now people will abuse it, queues will get longer and longer and solutions that should not pass will. Instead, you could've sent a private message to Mike so that he can fix it.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +91 Vote: I do not like it

    It's not as op as you think. Your random solution still needs to have a decent chance to pass in order for this to work.

    Let's say your solution has a 90% chance to pass. If you only have one chance per test case. It's likely to fail after 10 test cases. But if you have 3 chances (i'm not sure how many times codeforces actually tests the code if it gets tle) per test case, you will have a 99.9% success rate per test, making it unlikely to fail.

    But if you have a 20% chance to pass, giving it 3 chances will make it a 50% chance to pass. Which will still fail on tests.

»
7 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Won't you regret exposing this hack if Mike decides to modify the re-judging thing to handle it? :P

»
7 months ago, # |
  Vote: I like it +148 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Nice trick, I have used it in a previous contest as well.

72346371

I think one can uphack your solution, but as long as it worked, you should feel happy about it :D

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

    I actually didn't know this trick during the contest and just wrote the while loop as a test to make sure my code used too many queries instead of something else failing.

    Only after the contest with some extra testing did I realise that this helped the code get AC.

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

      I was in exactly the same position xD

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when a code gets TLE, it will rerun the code several times to see if the code is on the edge of the time limit. By doing this you increase the chances of your code passing significantly

Can you please explain how it will increase chance for code to pass as your code will be rejudjed from the very beginning or am I missing something

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Afaik, when your code gets TLE, it will be re-run several times. If you get AC one time, then it counts as AC.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But the 1. process to recheck will be similar as of the previous one then again it should give tle how the verdict can change because his code was not like some near edge case that may change its verdict on recheck and as per my knowledge vecrdict of tle changes to ac if it is some near edge case

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If your code has a probability p of passing, meaning that it will fail with probability 1-p.

    Giving it 3 chances instead to pass instead of one will make the code fail only if it fails all 3 times. Which has a probability of (1-p)^3.

    So if you run the code x times, the probability of it being correct will be 1-(1-p)^x.

»
7 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Disclaimer: I may get some technical details wrong, don't quote me on the internal workings of testing systems.

I don't think that we can do anything about this. As far as I understand, Codeforces and many other systems try to run several solutions in parallel at first, but if a solution gets a TL verdict, it is rerun on a separate core in more favorable conditions to see whether it really gets TL or if it is the consequence of being run in not the same conditions as promised by the system. Theoretically, one can get rid of this optimisation, but that would increase the testing queue considerably.

In fact, an argument was made several times, that any rejected-type verdict should be rejudged on a separate core. For example, suppose that you have a "while (!TL()) {search for something, terminate if found}" clause in your code. Then, incorrect time measurement can lead to the cycle terminating too early and you getting a WA verdict, while it could be true that you would get AC without this clause, because you would get TL on the first invocation, but AC on the second one. Similarly, you can get RE because you asserted something, et cetera.