Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Kar98k's blog

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

https://codeforces.me/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

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

Random tasks get accepted with random lines.

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    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
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
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