mjhun's blog

By mjhun, history, 5 years ago, In English

Hello Codeforces, what wave?

I want to publicaly congratulate the best team with the worst name "GG Dem", composed of The Cuco MarcosK, The Beast SebaMarin and thr Wonder Boy MateoCV, aka the "Lucianos Castros" coached by "Que pingo es concha" Vladislao, with the invaluable help of "The anti-mufa talisman" ec24, for qualifying to the ICPC world finals 2020.

I'm so picaport.

Sorry for the spam. Feel free to doenvote meee. Weh weh weh

Specials thabks to Demetrio, and to Codeoforcew and pilygon platforms.

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By mjhun, 8 years ago, In English

A couple of days ago, I was trying to solve 739E - Gosha is hunting. 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.

Full text and comments »

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