WhaleVomit's blog

Changing bounds makes WA solution AC for unknown reason
By WhaleVomit, history, 6 years ago, In English

I was working on the problem Xenia and Tree here: http://codeforces.com/problemset/problem/342/E

But the problem statement doesn't actually matter.

My first solution gets WA: http://codeforces.com/contest/342/submission/33140735

and my second gets AC: http://codeforces.com/contest/342/submission/33140905

The only difference between the two submissions that mattered is that I increased MAX_N from 100000 to 100005. This should not have changed anything, because I'm pretty sure my array sizes were all large enough. So why did this happen?

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

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

For your WA submission on test #4 the input set has n = 105. So when your code tries to access the 105 th node it should get RTE because the last node you can access is 9999. But sometimes it access the next value in the memory after 9999 th index and this gives a WA. This behavior is undefined.

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

    I subtract 1 when I read in, so this shouldn't matter.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This gets AC: http://codeforces.com/contest/342/submission/33200103. The change is line 99:

M00(i, numNodes) child[par[i]].PB(i);

becomes

M00(i, numNodes) if (par[i] != -1) child[par[i]].PB(i);

(I just launched valgrind on the input example with MAX_N = 5! ;))

→ Reply