Weird non-determinism in 2197E1 (Interactive Graph)
While solving 2197E1 (Interactive Graph – Simple Version) in the recent Div 2, I ran into something really confusing, the same logic gave both AC and WA depending on tiny, irrelevant code changes.
I had multiple submissions within minutes:
Some Accepted, some WA on test 8 / 9 / 20 / 21 / 22 / 23
No logic changes. Same idea. Same queries.
The strangest example
This version ACs:
if (q == -1) { return; }
This version WAs:
if (q == -2) { return; } Logically, if I'm getting accepted, both branches are dead code.
Either the checker is non deterministic or there's some UB shenanigans going on.
Links to submissions
362583126 WA
362583031 AC
Darsh_Jain also tried testing it, and the following two submissions
362582232 WA
362581962 AC
And the difference between the two is only that we have added a comment in the first one!
FelixArg and sevlll777 pls help
EDIT: It was indeed UB :(, fixed now. PS: Always use #define _GLIBCXX_DEBUG kids.
Auto comment: topic has been updated by clueless_girrafe (previous revision, new revision, compare).
The 2nd case is a dead case, but I don't think the 1st case is, since -1 is returned in case you exceed the number of permitted queries, and you get wrong answer if you keep querying after getting -1.
But still you should have gotten WA as you are returning on -1.
Yeah sorry if I wasn't clear, but I meant that if its getting accepted, it obviously isn't taking the q==-1 path, so both branches don't matter.
But it's solved now, it was indeed UB!
Auto comment: topic has been updated by clueless_girrafe (previous revision, new revision, compare).
#define _GLIBCXX_DEBUGWhat's the meaning of this?
It replaces your standard containers (like std::vector etc) to their debug versions, so it gives runtime error instead of UB if you do anything like accessing out of bounds etc. Though it will make your code slower as it's doing these checks.