Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

VLamarca's blog

double gets TLE and long double AC, why?
By VLamarca, history, 6 years ago, In English

Hi,

regarding problem B from this contest, my solution using double gets TLE and the same solution using long double gets AC, anyone has any idea why?

You can use this test case in custom invocation to confirm that the solution using long double is indeed twice faster.

EDIT: I could pinpoint the problem and it is the mod member function that gets the norm of a vector using hypot(x,y), which is the same as sqrt(x*x+y*y) but with better precision. The solution with double gets accepted if I use double everywhere, casting to long double only here: hypot((long double)x,y) (code). Using sqrt(x*x+y*y) instead works too. Nonetheless it is still very strange that hypot function is faster when dealing with long double.

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

»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

It's because of the precision. Just for example, if you say something like double a = 3.0 a might be 2.99999999 at some point and it works on long double a = 3.0.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It's hard to read the whole code, especially because it isn't well commented. Try to experiment and see which part takes the most time, so you could ask only about those few lines.

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

A reason could be that some values you are calculating are so small that they are denormalized values in double precision but not with long doubles (calculations on denormalized numbers take significantly more time). But i cant say for sure that that is the reason.

→ Reply