In the last round Codeforces Round 1134 (Div. 4)
this submission got accepted for the problem E — Avalanche although after looking at the constraints we can clearly see that the code will face an integer overflow so, is it due to weak testcases or something else ? because mostly when I get an integer overflow I get a diagnostic warning if it is normal can any one tell for which integer overflows our code will run normal and for which it will not
and also there is also a submission I was seeing code of this person code
he has similar logic but he is having a wrong answer due to the integer overflow so my question is that did the code above passed by luck or is there something else behind the scenes!
Any insights would be appreciated!









when you have int variable it's only capable of storing 32 bits of information, when your number gets too big your integer is overflowed and you get this error. the solution is to use long long or if the problem asks to find the number modulo 10^9 + 7 you can take modulo every time adding some number to that variable so that it does not overflow.
if you have the read the first code the long long variable in the first code also gets beyond the limits of a long long so why is it not resulting in an integer overflow that is my main question.
parity is maintained with overflow (assuming standard compiler behavior, technically overflow is UB so the compiler could do anything), so the solution works.
nikka
did you make an account just to say this (and to ask vlad to add holyC ig)
actually yes and to say stuff about idontwannadothisanymore. the guy gives me the creeps
Singed integer overflow is undefined behavior, which means anything can happen theoretically. That is, the program may work as expected, it may silently return a wrong answer, it may crash, or it may "make demons fly out of your nose" (nasal demons).
Essentially the behavior of undefined behavior depends on how the compiler compiles the program. So in some sense the program passed by luck.
Unlike signed integers, overflow of unsigned integers is not undefined behavior.
But, _Kee why didn't the second code pass then ?
As I said, when a program hits undefined behavior, its behavior is unreliable. It's OK that the result is inconsistent.
Essentially, compilers don't care the code path that causes UB. Only the code path without UB must run correctly.
Compilers may do some surprising optimization if UB is involved. For example, think of this function:
The function
fcauses UB ifxis not zero. The code is valid only ifxis zero, so the compiler can optimize this function into the following (GCC actually does this if-O2is given):Note the call to
g()is entirely removed.ok thanks for telling
I am not really sure but this might have something to do with how mod and negative numbers work in C++. We know modern languages use two's complement to store negative numbers (check this out). This means number overflows into a negative number.
Since we know in C++, $$$-x$$$%$$$y=-(x$$$%$$$y)$$$, the condition
if(player==1)in the second code fails because player is equal to $$$-1$$$, and it wrongfully answersBob. However, in the first codeif (su&1)condition does not fail because even after overflow LSB remains same, which means that $$$2^0$$$ bit does not change so this parity check works.I believe this is also why my code works.
I tried both and they both worked (Code using & 1 to check parity: 398433361), (Code using % 2 to check parity: 398523537). Upd: I thought you were saying it was only because of using % 2, but this code failed when I used % 2 == 1: 398524373 u r right
yup
oh... I see thanks.