Avoid WA by integer overflow

Правка en1, от MaxWelll, 2024-03-11 21:30:41

In the last contest (Codeforces Round 933 (Div. 3)), while solving the problem 1941F - Рудольф и дисбаланс, I got WA on my first attempt. On debugging, I found this bit of code was problematic

const int INF = 1 << 30; // this is equal to 1073741824

I've always used this as my infinite value for integers, but it was not large enough in this case.

Note 1: Be sure your infinity is actually an upper bound for your problem

Well, I made INF large enough and submitted it again 250809384. WA. Can you spot the issue in my code? I was pretty sure that I didn't need to make every integer 64 bits so that the problem passed. But I did it and it passed.

Note 2: If doubtful, go ahead and make every int a long long int. It's ok for CP; avoid the unsuccessful submission penalty

The bug in my code was pointed out to me by Codeforces when I played a bit more after the contest 250815419. And it's so silly because I introduced that bug by rewriting the condition in a way I thought could be more efficient obscuring what I was trying to check. The gain in efficiency there would be that I could compute a0 + a1 only once and that the compiler probably makes 2 * fd really fast with a left shift. But why!? That would have had a negligible effect on the program as a whole.

As Donald Knuth said

premature optimization is the root of all evil...

In my case, it was not only premature but meaningless.

Note 3: Don't bother cutting edges unless it's actually useful and, more importantly, needed

I guess I'll be making posts like this whenever I do something that I regret in a contest. If you have any advice feel free to share it!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский MaxWelll 2024-03-11 21:30:41 1782 Initial revision (published)