search

zen0wu / topcoder-greed

greedy editor for topcoder arena
Apache License 2.0
229 stars 45 forks source link

Fixed bug that made the testers believe x = -x when comparing doubles. #39

Closed vexorian closed 11 years ago

vexorian commented 11 years ago

Turns out that when the expected result was -1.5, for example, and your result was 1.5, Greed thought it was correct. I replaced the comparison method with the one used in KawigiEdit, which doesn't have this bug.

vexorian commented 11 years ago

c++ has isnan I just copied what KawigiEdit does. I think it needs it in case a custom test case also has nan as result, but we can do !isnan(received) && !isnan(expected) will change.

Let dx be the absolute error, then the relative error is dx/ abs(x). TC requires that the minimum of them is <= 1e-9.

min(dx, dx / abs(x) ) is dx when abs(x) >= 1 and dx / abs(x) otherwise.

if (abs(x) >= 1.0), we want dx/abs(x) <= 1e-9 -> dx <= 1e-9 * abs(x)

if (abs(x) < 1.0) we want dx < 1e-9

zen0wu commented 11 years ago

Looks good, I'm OK with these. @wookayin What do you think?