galen_colin's blog

By galen_colin, 12 months ago, In English

If you failed on test 66 on (this problem | div2 version), you probably haven't reset enough of your array in between. This problem gives rise to a very unique type of bug, since we access the array beyond the part where we initially read elements into. What I mean is, if you have a large case followed by a small one, on the small one, you'll read the first $$$2^n - 1$$$ elements in, but the elements in indices $$$2^n$$$ to $$$2^{n+1}-1$$$ may also be filled with values from the last test case. Many people adapted the function definition from the problem statement, treating an index like a leaf iff the two elements 'below' it (i.e. $$$a_{2i}$$$ and $$$a_{2i+1}$$$) are both $$$0$$$. But if the array isn't reset, then values that are supposed to be leaves may be treated differently. Unfortunately, I made this mistake too :(

Not resetting the state between test cases is common. But this is a very unique type of mistake, specific to this problem. I don't think it's reasonable to blame the setter for overlooking this in the pretests. Surprising that none of the testers made this same mistake, though...

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

12 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Understandable, but can we uhhh... execute test 66.