I recently submitted twice to problem 865C/866C (same problem), Gotta Go Fast.
http://codeforces.net/contest/866/submission/30954904
http://codeforces.net/contest/865/submission/30956252
The first submission got wrong answer on test 1 on Codeforces. But I tested the solution both locally and on Ideone, and the answer was correct.
In the second submission my only change was adding the following one "useless" line of code to a for loop:
if (hi > 2 && hi < 1) cout << "this should never run" << endl;
It got AC.
My question is, why is this happening? I've tried debugging it locally and looking at the assembly, but there are no bugs when it runs on my local machine or on Ideone; it's only acting strangely on Codeforces. I've been staring at this code for many hours now thinking it might be undefined behavior, but I've tried many slightly different submissions (with long double, without the call to min) that work just fine without the extra useless if statement.
Tl;dr: I am utterly confused and would greatly appreciate if you could help me find where my UB is, or if there's some other problem with floating-point precision :-)
Thanks!
I suggest starting with floating point section here.
Seems to be optimizer precision error. With
#pragma GCC optimize ("O0")
it works as expected.As I know it and can explain: registers for floating point arithmetic are larger then
double
, they are like along double
. So you may expect some precision errors even after simple assignment:I think, The best way to avoid this error is next comparison: