Wednesday, September 14, 2011

declare var to the wrong type

I got caught by this issue when working on CF #82 div2, problem D, Treasure Island. It seems a straightforward problem and I implemented the naive idea. This will TLE but this is not my problem at this point. I got WA for testcase #38. However the testcase is too big to be shown fully on the submission page. I looked at my code, and a few AC code. Looks the only difference is that they precomputed dp[4][1000][1000], the max distance you can travel from cell[i][j] with direction[x]. This will speed up considerably, from 10^9 to 10^6. I know, but I got WA, not TLE. So what went wrong here.

Looking at my code, tried a couple of different things. Changing scanf to cin, change char[] to string, change [] to vector. None helps. Tried to generate some random input and run my code as well as some AC code. They agree. Plus to generate a nontrivial testcase for this problem is not that easy. I almost gave up and wrote a message to the problem setter for the complete testcase. Then something just kept pulling me back to the problem. Fix it.

My last resort was to hack the testcase. I tried to output some debugging information for that specific case. For CF it is not easy. I have to get around earlier testcases before reaching the testcase #38. Once I was there, something apparently wrong surfaces. Whenever inst.len > 128, the step went wrong. I still don't get it and switched between the naive impl and the speed-up version. Finally, I realized something. And that was it. I wrote
char dir=inst.dir, len=inst.len;
and then len is of type char and happens to be at most 128 on CF machine.

That was it.

Integer overflow are among the hardest bugs to ferret out. And when it bites, it hurts greatly.

No comments:

Post a Comment