So I was trying to blitz my way through ABC in the last Div 2 as per usual, when, shockingly, I received the verdict "Wrong answer on test 8" for B(actually, a quite regular occurrence). I just thought it was an issue with the sqrt() function, so I coded a binary search version for the sqrt and moved on. However, after the contest, I resubmitted in C++17(I was using C++20), and it somehow passes? Also, when prompted by my friend, I added #pragma GCC target("avx2") to that submission, and it somehow failed again. Could someone please explain what's happening here?
Failing submission(C++20)
Accepted submission(C++17)
Failing submission(with pragma)
had the same issue, will just never trust floating point math again lol
Use sqrtl for long long i use it for your first falling submission and got AC
It's basically just a rounding error. C++20 believes for some reason that sqrt(854258780613619262) = 924261208, even though 924261208 * 924261208 = 854258780613619264 (the difference is only two). Here are the two submissions which I used to debug that. However, after checking the value of sqrt(854258780613619262) in a separate submission under C++17, it also prints out the wrong value, which makes even less sense.
sqrt() sometimes fails to sqareRoot long long values. Use sqrtl() instead.
That's not the question that OP asks in the blog. I think that at this point we all know that using sqrtl is more reliable than using sqrt. What I (and the OP) would like to know is the reason why this behaviour occurs exactly, why C++17 sometimes produces the correct result and sometimes doesn't, what is happening behind the scenes of all of this.
Floating point numbers in 32 bit C++ are really weird. Take this code for example. There is a way to make this function return
True(assuming you submit using C++17):At first glance this should seem completely absurd. I claim that it is possible to somehow make
ybe< 1.0,>= 1.0and== 1.0all at the same time.Make x be tiny and negative, for example -0.000000000000000001.
If you want an explanation to why this works, then see my blog on the topic. The explanation has to do with excess precision.
I think the problem is with floating point. Therefore, I used $$$n=i^2+x$$$, where $$$x \le 2k+1$$$, for each $$$\lfloor\sqrt{k}\rfloor\le i\le k$$$ until I get the minimum. And it indeed worked. So, I think the problem is with floating points.
I too have encountered the same. And that's the reason I've permanently stuck to using C++ 17.
In the B problem of this contest, I just used floor(sqrt(num)) in C++ 17 and it worked fine for me.
So I tried to submit the same solution that got AC in C++ 17, and surprisingly, I too got WA in test 3 using both C++ 20 and C++ 23.
Submissions:
C++ 17- (https://mirror.codeforces.com/contest/2020/submission/283655724) C++ 20- (https://mirror.codeforces.com/contest/2020/submission/283690895) C++ 23- (https://mirror.codeforces.com/contest/2020/submission/283690871)
So it seems that it's something to do with the rounding and precision, how different versions of C++ have implemented sqrt.
Also I too would recommend using the binary search approach as it gets rid of all the float precision issues and also is fast enough.
sqrt usually has lots of precision issues and unpredictable behavior. In general, for solving $$$\lfloor \sqrt{N} \rfloor$$$ you can use this reliably:
Can you explain why (N+5) and not a value less than 5?
I don't think the value matters too much, I've seen people use 2 as a constant, and tourist's solution for B uses 10. For large values of $$$N$$$ the constant shouldnt affect the runtime much, the point is just to slightly raise the output enough to avoid situations where sqrt() gives a lower value than intended (e.g. 49.9999 instead of 50.0001), which would give the wrong result when casting to an integer.
For some unknown reasons, my code even with C++ 17 also gave WA on test case 8. Could it be because of some mysterious behavior of floor function over sqrt()?
SAME HAPPENED WITH ME! Then I converted my C++ code into python using GPT then it worked!
Same Here! C++ Code : https://mirror.codeforces.com/contest/2020/submission/283708389 Python Code : https://mirror.codeforces.com/contest/2020/submission/283713285
I converted my C++ code to python then it worked.
just do binary search lol
Floating point numbers work completely differently in 32 bit and 64 bit. Currently on CF, C++17 is 32 bit and C++20 and C++23 are 64 bit. I've previously written a blog about this quirk here. TLDR: 32 bit uses long double for computations even if you ask it to use doubles (refered to as "excess precision"). But when stored, the double variables are still stored as doubles, making floating point numbers in 32 bit horribly unreliable.
Your submission here is a perfect example of this. For example, with these two lines your submission gets AC in C++17(32 bit) 283814989
However, forcing
resto be stored by adding some arbitrary floating point computation before theint a = resline causes the submission to WA in C++17(32 bit) 283815050.I highly recommend that you use
long doubleand submit in 64 bit. That is much better than relying on excess precision.The same thing happened with me. I had to code a binary search square root function as well. I will never be using the sqrt function again.