notSpad2e's blog

Bizarre Judging Behavior ?
By notSpad2e, history, 3 days ago, In English

So I was solving problem D from the latest contest when I encounter a bizarre behavior. In this 306416672 the output to the second testcase is clearly incorrect.

The jury's answer is 0 2 4 2

My code's output is 0 2 4 4

Well, my code output the exact same thing as the jury in on my pc. Maybe an uninitialized variable?? No worries, it's the first testcase, I can just debug using the jury's output. In this 306417865 I print some additional variables to debug my code. The output is the line where there is only 1 integer, otherwise that line is a debug.

This time the answers came out to be

8 11
0 // First number
13 11
6 4
2 5
2 // Second number
27 11
4 // Third number
15 11
4 4
0 5
2 // Fourth number

It's the correct answer, but I changed nothing except the debug line. Then I removed the debug line and the answers became wrong again. At this point I don't even know what to do so I add some random cout << " "; to the code in this 306419133. And, amazingly, it worked. WHYYYYYYYYYYYYYYYYYYYY??????

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

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by notSpad2e (previous revision, new revision, compare).

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by notSpad2e (previous revision, new revision, compare).

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i had the exact same behaviour, it was happening because of case where x became 0,
if ((x ^ sufxor[curpos + 1]) == 0) { ans = n — curpos — 1; break; } you can check if something like this is happening in your code https://codeforces.net/contest/2064/submission/306417426

→ Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

See this, passing 0 into __builtin_clz(x) is undefined behavior.

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks! That explains it! I still don't know why printing other element led to correct output, but it's undefined behavior so I won't ask.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can use the standard library function std::countl_zero.
      It wont cause undefined behaviour when the input is zero.
      You should use <bit> functions instead of gcc instrinsics.

      → Reply