txingml's blog

Two ACs codes output different result
By txingml, history, 6 years ago, In English

I found a very strange thing in Educational Codeforces Round 50 F. Relatively Prime Powers.

First, here is a AC code written by me. https://mirror.codeforces.com/contest/1036/submission/42680029

And If you add a line "assert(val != 999999999999999956LL);", then this code will fail on test 3. It means test 3 has a case that num = 999999999999999956. https://mirror.codeforces.com/contest/1036/submission/42680073

But This is another AC code written by @alonefight, https://mirror.codeforces.com/contest/1036/submission/42657108. I ran it in my local environment and compared with my code. The result is surprised.

I used the test case as follow. 1 999999999999999956

My result is 999999998998996625 But @alonefight's result is 999999998998996624

I submitted his code and it still passed all test case. https://mirror.codeforces.com/contest/1036/submission/42680102

FYI, my environment is macbook, clion, c++14.

Can anyone tell me why this strange thing happened?

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by txingml (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In custom test his code gives 999999998998996625 with g++14 but in Clang++17 Diagnostics it gives 999999998998996624. I think it is smth like undefined behavior

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is really strange. I've tested his code in custom test under Clang++17 Diagnostics. And look at this pictures scrt(n) gives 999999999, but if i comment one line that doesn't influence to the output it outputs 1000000000! first, second

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I found another strange thing with codeforces g++14. If you run this code in custom test g++14 you will get that sqrt(n) yields different results 999999999 vs 1000000000

    → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it +6 Vote: I do not like it

Thank you all for replying my question.

sqrt(999999999999999956LL) will get 1000000000.0000000000 in my environment, and sqrt((long double)999999999999999956) will get 999999999.9999999780.

So it seems that if we need to use sqrt() and trucate result into integer, we must do some check. Such as:

long long safe_sqrt(long long n) {
    long long res = sqrt((long double) n);
    if (res*res == n) return res;
    const long double eps = 1e-8;
    if ((long double)(res+1)*(res+1) < n + eps) return res+1;
    if ((long double)res*res + eps > n) return res-1;
    return res;
}
→ Reply