..vince's blog

By ..vince, history, 5 years ago, In English

so i was solving https://codeforces.com/contest/1138/problem/E. the idea here is quite obvious. compress all SCC as a single node and solve it like a normal DAG

then something strange happening. at the beginning i got a RTE verdict for my solution. when i was trying to find bugs in my code, i tried to reverse engineer and add this code my first DFS function (i used kosaraju's algorithm) :

if(n == 99998 && m == 99999 && d == 50) { if(u.fi > 100000 || u.se > 50) { cout << "KOSA : " << u.fi << " " << u.se << "\n"; fflush(stdout); } }

magically, adding this piece of code to my solution give me an AC verdict.

RTE solution : https://codeforces.com/contest/1138/submission/51269031

AC solution : https://codeforces.com/contest/1138/submission/51268839

so what really happened? is there any error in CF?

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how u came to know you have to add this line

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

    i don't, i just randomly add this line to find bugs.

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

The problem is cursed, simple as that.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

No, it's a bug in your code which invokes undefined behaviour which makes your program spuriously fail or pass depending on unrelated stuff like presence of debug output or precise form of control flow. C++ does not guarantee runtime errors for signed overflow, array out-of-bounds or similar stuff (see "undefined behaviour").