DBradac's blog

By DBradac, history, 19 months ago, In English,

Everyone has had a bug in their code because of accessing out of array bounds. However, in some cases, the program will run as expected.

I have two examples from today's contest: problem B — 24829988 problem C — 24831518

In both of these problems, I had stupid bugs. For problem B, it's possible that the argument k of the function is zero and this line

if (ind == f[k-1]) return (int) (n % 2)

will access f[ - 1] which is undefined.

I have found this bug, and after some stress testing locally and on CodeForces, I decided not to resubmit because it seemed fine.

Now, in problem C, I iterated up to 1029 and the value of i xor x can become larger than the size of the array. However, this is only an issue if that piece of memory is not used by the process and it will result in seg fault.

Otherwise, nothing will be changed because we add zero.

I only found this bug while I was trying to hack someone else's solution so I couldn't resubmit and I was pretty sure it was going to fail system tests because locally it resulted in seg fault for some cases.

To my surprise, both submissions were actually successful, and my F failed (but that's irrelevant to this post xD) My question is this: what do you usually do when you find a bug like this during the contest and do you stress test your solutions before submitting to prevent it?

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

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I had a similar issue in the first round of the last 8VC cup on problem D — 23856738 on this line

lli y = query(MAXN) — query(b) + query(a — 1);

as this query(MAXN) would access position MAXN of an array whose indexes go from 0 to MAXN — 1

I had no confidence it would pass systest so I decided to give up some points and submit it again by changing the line to

lli y = query(MAXN — 1) — query(b) + query(a — 1);

I didn't stress tested because several minutes had already passed when I found the bug, I was confident in the solution idea, and in division combined I usually benefit from writing faster code rather than solving more problems (I can't solve more so I get points from speed) — I also though that resubmitting was giving me guarantee of gaining those points, and humans tend to be risk averse when thinking about positive factors. In the end both passed — 2386002223869775

»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

The same thing happened to me in the last SRM. I had a chance to resumbit, but I didn't want to resubmit because I had a chance to get the first place. Luckily, my solution passed the systest.