### galen_colin's blog

By galen_colin, 12 months ago,

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...

• +61

 » 12 months ago, # |   +41 Understandable, but can we uhhh... execute test 66.
•  » » 12 months ago, # ^ |   +12