Kar98k's blog

How did the solution get accepted by adding just this line ?
By Kar98k, history, 6 years ago, In English

https://mirror.codeforces.com/problemset/problem/498/B

For the above question, this was my TLE solution : 55865422 : time=1000ms and this was my Accepted solution : 55865596 : time=155ms

In TLE solution, i just added one line: if( dp[i][j] < (1e-12) ) dp[i][j]=0;

and it got accepted.

I am not able to understand that how this one line is able to reduce the time complexity ( and also by such huge margin ) as it is not involved in any of the loops.

P.S : i have added this line after looking that many of the Tle solutions got accepted after adding this line same as mine did.

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

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

Random tasks get accepted with random lines.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Well a lot of people had used this line in their submission for this problem. I dont think this line would be truely random if a lot of people are writing "same" random line

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

Auto comment: topic has been updated by Kar98k (previous revision, new revision, compare).

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

That was probably because of the constant factor of "double." When it is less than 1e-12, it has to mess up with more than 12 digits. Also, there are 5000^2 doubles. Each of having a significant number of digits makes the running time slower.

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

    Doubles aren't stored as some sort of string, so it doesn't make any real difference here.

    The actual reason is working with denormalized numbers (as you get DP values which are outside of double range), which are really slow. Compare 55866840 and 55866850. Here you can as well fix it by using wider data type to not suffer from those overflows: 55867184.

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

Denormal numbers, probably.

There is a class of floating-point numbers very close to zero which has been incorporated into the standard to avoid the situation where a-b=0 for two distinct floating-point numbers a, b. The problem is, the computation on these numbers can be very slow. Like, very, very, very slow. Like, a dozen or so times slower than usually. However, these numbers are very close to zero (probably something like 1e-300 in double-precision floats), so replacing small float values by zeroes helps us avoid them.

When I replaced your epsilon with 1e-100 (very tiny epsilon, but still huge in comparison to the denormal numbers), the solution passed without any problem as well: 55866944.

→ Reply