Not_Abdul_Munim's blog

By Not_Abdul_Munim, 3 days ago, In English

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!

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 days ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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.

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 days ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it 0 Vote: I do not like it

    But, _Kee why didn't the second code pass then ?

    • »
      »
      »
      2 days ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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:

      #include <climits>
      void g();
      int f(unsigned short x)
      {
          int a = INT_MAX;
          a += x;  // Causes UB if x != 0
          if (a < INT_MAX) {
              g();
          }
          return a;
      }
      

      The function f causes UB if x is not zero. The code is valid only if x is zero, so the compiler can optimize this function into the following (GCC actually does this if -O2 is given):

      int f(unsigned short x)
      {
          return INT_MAX;
      }
      

      Note the call to g() is entirely removed.

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.