Блог пользователя Not_Abdul_Munim

Автор Not_Abdul_Munim, 4 дня назад, По-английски

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!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 дня назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 дня назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
4 дня назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

parity is maintained with overflow (assuming standard compiler behavior, technically overflow is UB so the compiler could do anything), so the solution works.

»
4 дня назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 дня назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 answers Bob. However, in the first code if (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.