xuanquang1999's blog

By xuanquang1999, history, 7 years ago, In English

I'm solving 27E — Number With The Given Amount Of Divisors. My code involved a function mul(a, b) that will return 1018 + 7 if multiplying a and b will lead to overflow, and min(1018 + 7, a * b) otherwise. I checked for overflow using the condition a*b div a != b.

When I submit my solution using C++14, it seemed that the overflow check failed, which lead to WA on test 5.

34068376

However, when I uncomment the if statement in the mul function (which, theoretically don't print anything out), it get accepted.

34068431

I resubmitted the WA code with C++11 and C++17 Diagnostics, and it get accepted too.

I don't know what happened here. I suspected that some kind of optimization from compiler caused this strange behavior, but unfoturnately I know nothing about compiler optimization. Can anyone give me a proper explanation about this strange behavior? Thanks in advance.

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

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You can check for overflows something like: a > inf / b. I think it's a better practice and it involves only one division instead of a multiplication and a division (so should be faster)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks for the suggestion

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alternatively, you can just multiply them as floats, although I'm not sure about the performance.

»
7 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Signed overflow is undefined behavior, read here about that.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I've never thought that overflow is undefined behavior, thanks for informing me this.

    Also, I glad that this happened when I'm practicing, not in an actual contest.

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Actually you can use -fsanitize=undefined to check for overflow as it will indicate you which line does the overflow happen. (Warning: About 2 to 3 times slower compile time, only recommend when you are trying to debug). Moreover, fsanitize also highlight any errors you might have in your code (such as out-of-index access or any undefined behaviors like that ...). Hope it helps!