nikolapesic2802's blog

Increase the chance of a random algorithm passing by abusing TLE verdict on Codeforces
By nikolapesic2802, history, 4 years 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

Comments Comments (19)
| Write comment?
»
4 years 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 ;_;

→ Reply
»
4 years ago, # |
  Vote: I like it +121 Vote: I do not like it

this is genius

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Maybe xD

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    He can easily be able to make us not able to generate randomized seeds. If Mike made us not able to access current time, and disabled clock() commands and any thing which can cause a randomized seed. As I remember, in Codejam, clock() command is already disabled. Mike can pretty much do the same with a disabled access for external time.

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

      There are no hacks at Codejam so you can't solve this problem like this

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +45 Vote: I do not like it

      You can use the address of a random variable on the heap as a seed. And I think there are other ways too.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Wow, didn't think of that xD. That is a pretty smart idea.

        → Reply
»
4 years ago, # |
  Vote: I like it +148 Vote: I do not like it

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I was in exactly the same position xD

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Here umnik explained it in a very good manner

    → Reply
»
4 years 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.

→ Reply