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
poggers
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.
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://codeforces.net/contest/2020/submission/283655724) C++ 20- (https://codeforces.net/contest/2020/submission/283690895) C++ 23- (https://codeforces.net/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.