ZiadEl-Gafy's blog

Same code got both Accepted and TLE...?
By ZiadEl-Gafy, history, 2 years ago, In English

I took part in round #824 and my submission in 824C during the round later failed the system tests with verdict TLE. I thought fair enough, and later wanted to check if somewhere in the code it got stuck in an endless loop.

I added a variable to count the number of iterations of a loop and an assert statement to ensure it doesn't run longer than expected, as is shown in the picture below.

I submitted the code to see if it would get TLE again or if the assertion would fail, and to my surprise it got Accepted.

This is the link of the submission made during the round which later failed system tests: link

This is the link of the submission made after the round which got Accepted: link

The only changes made to the code are the ones shown in the picture above. So, I was hoping someone would have an explanation as to why my solution failed system tests.

MikeMirzayanov

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

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

I took the submission as same as your old code(with no assert)。https://mirror.codeforces.com/contest/1735/submission/174460975 But it's AC. Maybe there's someting with other things.

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

    I tried it as well with the same language and same exact copied code and it got Accepted. Seems like it was only meant to fail the system tests, sucks to see these things happen :))

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

    Same...I got AC too.

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

I ran your code 13 times and got TLE on the last attempt, while the AC submissions used anywhere from 2776 to 2994 milliseconds. There seems to be a lot of variance between the running times of the submissions, which may have something to do with the Ofast optimization, but your TLE is probably attributed to relatively bad luck instead of a fault in the system.

I haven't figured out the exact reason yet, and I'll keep trying. I'll get back when i figure it out.

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

    Your efforts are much appreciated! <3

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

      I've figured it out; your code was memset-ing a 2e5-size array for every test case, and the running speed of memset may be slightly different depending on the code block that allows the optimization.

      Note that you actually don't need 2e5 elements in pre and nxt; you only need 26. Changing N to 26 comfortably ACs in 46ms: 174467802

      → Reply