By ZiadEl-Gafy, history, 2 months ago,

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

• +21

 » 2 months ago, # |   +3 I took the submission as same as your old code(with no assert)。https://codeforces.com/contest/1735/submission/174460975 But it's AC. Maybe there's someting with other things.
•  » » 2 months ago, # ^ |   +3 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 :))
•  » » 2 months ago, # ^ |   0 Same...I got AC too.
 » 2 months ago, # |   +10 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.
•  » » 2 months ago, # ^ |   +9 Your efforts are much appreciated! <3
•  » » » 2 months ago, # ^ |   +13 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
•  » » » » 2 months ago, # ^ |   +3 Yes, you're probably right. Thank you!