https://codeforces.net/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.
Random tasks get accepted with random lines.
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
Auto comment: topic has been updated by Kar98k (previous revision, new revision, compare).
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.
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.
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=0for two distinct floating-point numbersa,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.
Thanks, I understood the reason !