galen_colin's blog

By galen_colin, history, 4 years ago, In English

Link to contest

Author's editorial

This is a duplicate of my comment here. I've gotten a couple of requests to make it a blog (for some reason), so here it is. Note: this is unofficial, I was just a competitor


Full text and comments »

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

By galen_colin, 4 years 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...

Full text and comments »

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