Hi, while submitting 1535F - String Distance for the previous educational round I did observe a strange behaviour. I submitted the absolutely same code several times:
As you can see, submitting with C++17 was AC every single time. Submitting with C++17 (64bit) lead to timeouts on different testcases, like 18, 27 or 32 but also to several AC with all testcases 18,27,32 only needing <300ms in 64bit. I read my code about 20 times now checking for out of bounds errors or stupid mistakes. I have no random numbers generated. I also did several tests by generating a big number of random testcases with both 64bit and 32bit locally, but I couldn't reproduce this behaviour. I got consistent times all around. Now I'm clueless and want to ask whether someone has an idea why this happens.
AC 32bit: 118502792
AC 64bit: 118503021
TLE Testcase 18 64bit: 118502885
TLE Testcase 27 64bit: 118502935
TLE Testcase 36 64bit: 118502831
Thank you for your help!
Maybe there are different types of testing machines and depending on which one gets assigned to test your submissions, you get different times. If you can't reproduce it locally, it's mainly a question for CF staff.
So, what is the best way to reach CF staff? I searched the website, there seems to be no support-channel and no staff-site (or I just can't find them). Do I just tag Mike (and get lost in the flood of tags he probably gets regularly)?
Hi MikeMirzayanov there seems to be an inexplicable and seemingly random (from testcase to testcase) difference in execution time for the same submission in C++17 vs C++17 (64bit). Me and pajenegod tested locally and could absolutely not reproduce this behaviour, it only happens in CF-System. Could your team have a look into it? More detailed info is in the blog itself.
I wouldn't put too much emphasis on C++17 vs C++17 (64bit).
The issue is that your code submitted in C++17 (64bit) gets AC or TLE seemingly at random. Your AC submissions come in far below the TL (250ms / 2s), so the issue cannot simply be explained by small random fluctuations.
This is weird thing to have in global space. But it is not technically wrong.
Oh dear, that was good old copy-paste (I moved the input to global to do the local checks with random data)... To be sure I checked, but 64bit is still failing after fixing this.
I did some more digging into this, and I got ahold of the test cases. The test cases are generated in packs of 9, which explains why there is a pattern of TLE at 18, 27, 36.
I tried to run your program locally, both with sanitizers and debug flags. Locally everything simply works, no issues at all. It runs pretty quickly too, not even close to TLE. So my best guess is that something is wrong on CF's side.
One observation. If we remove reference
&from this loop:for(vector<string>& strs : strGroups), the code never gets TLE. Now it looks more like UB, but I wasn't able to find something illegal.I find it funny that we can have multiple red coders look at a piece of C++ code and can't tell if there's UB or not. I wonder why writing a comprehensive UB sanitizer is such a hard problem?
An update on this issue. I've tried two additional things.
I tested creating a mashup on CF where I manually increased the TL. It seems like the 64 bit C++ program randomly either gets AC in 0.2 s or 11 s. It takes consistently either 0.2 s or 11 s, and nothing in between.
On my windows laptop (which I believe to be similar spec compared to CF servers), I downloaded pbox.me (package manager by Mike) and installed the exact version of the 64 bit C++ compiler that CF uses. I've also gotten a hold of all the problematic test cases. Even doing all of this, I have not been able to recreate the issue locally.
I have no clue what could explain the program randomly running ~50 times slower. I've read the code, I've ran sanitizers. As far as I can tell there is no UB going on.