mjhun's blog

By mjhun, 2 years ago, ,

A couple of days ago, I was trying to solve 739E - Гоша выходит на охоту. My approach was similar than that of the editorial . My first submission (22589895) gave WA. After a while struggling to find what was wrong, I looked the case that was failing. I tested it on my computer but it gave the right answer!

After some debugging in Ideone (which gave the same answer as Codeforces), I realized that the problem was this: Somewhere in my code I insert into a set a pair<double,int> , where the double is the result of some operation (line 35).

ca.insert(mp((1-p[j].snd)*p[j].fst,j));


During execution I may move that pair to another set called wa, and somewhere else I erase some value from one of these sets (lines 62-68).

if(wa.count(mp((1-p[j].snd)*p[j].fst,j))){
...
wa.erase(mp((1-p[j].snd)*p[j].fst,j));
}
else {
ca.erase(mp((1-p[j].snd)*p[j].fst,j));
}


What was happening is that it wasn't erasing when it should. Then I created an auxiliary double array kk, where I store the value before inserting it into the set, and from which I read when I want to erase it from the set. This solved the problem (submission 22590238: AC).

So, the thing is: The operation (1-p[j].snd)*p[j].fst wasn't giving the same result as before, even though it's done with the exact same values and the exact same order than before. Just to be sure, I did another submission, which (before erasing from the set) asserted that the computed value is exactly the value stored in the auxiliary array (submission 22601078: RTE, so: the assertion failed).

I thought that floating point operations are supposed to be deterministic (they should give the same result, given that they are made with the same values, in the same order and on the same platform), as they were on my computer.

It may be that I'm mistaken, that there is some other error in my code which I didn't realize, or that there is some problem with the compiler (maybe an optimization bug). I thought that probably someone here could help me understand what is going on.