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

Автор nikolapesic2802, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +671
  • Проголосовать: не нравится

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

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

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

this is genius

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

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +91 Проголосовать: не нравится

    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.

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

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

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

    Maybe xD

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

    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.

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

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

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

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

    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.

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

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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.