http://ww2.codechef.com/viewsolution/2159135 . Can any one please tell me why this solution is getting TLE. I am new to python so any help is most welcome. I have seen some solutions following the same approach have been passed ( http://ww2.codechef.com/viewsolution/2104387 ). Thanks in advance.
1 Like
You need to precalculate the combinations(n,k) table.
But in the passed solution he has not pre calculated that.
Really?
dp = [[0 for i in range(1009)]for i in xrange(1009)]
for i in range (0,1006):
dp[i][0]=1
dp[i][i]=1
for i in range(1,1006):
for j in range(1,1006):
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]Sorry, the link that I given was wrong. Check the 2nd accepted solution of the same user.
http://ww2.codechef.com/viewsolution/2135358 . Please refer this solution. In this he has not pre calculated. But still it is accepted.
Seems he’s caching the Factorial instead of “n choose k”
first I thought this too, but timepass123 is doing the same as far as I can see…
Hello @timepass123 ,
I also did not precompute anything in this problem and got it accepted in Java . You can optimize your code and improve performance by a factor 4 times at the least. To calculate n C k . You should not compute all 3 factorials . That will take 2 * n steps of multiplication . Instead calculate n * ( n-1 ) * (n-2 ) … Math.max(k,n-k) . So if k is n/2 i make n/2 calculations and if k is 1 or 2 then I made i make only 1 or 2 calculations instead of making 2 * n calculations for every combinatorial number calculation .
@srihari : I tried same approach to calculate nCr as you. Still I got TLE. http://ww2.codechef.com/viewsolution/2157930 . I think my luck is bad 
@srihari : http://ww2.codechef.com/viewsolution/2157930 . nCr is calculated in the same method as you have done. Still I am getting TLE 
I also precomputed factorials instead of ncr and I got a TLE in Python. Why would that happen? Is it because of the long multiplications everytime or because of Python?
In Java I also tried precalculating factorials, but still computing nCr was incredibly slow. Interesting that the above solution got AC.
@vineetpalwal : I dint calculate factorial every time . I calculated and stored it.
Indeed odd. Am no expert in python either. Had switched to python after being fed up precision issues with my C++ solution and had my non-cached version itself get AC. Got both your probs also AC after few minor modifications (loop checks): http://ww2.codechef.com/viewsolution/2163138 [ 2.19s, cached]
@kshitij8 >> What do you mean long multiplications? Here’s my AC python solution http://ww2.codechef.com/viewsolution/2105273
In your submission http://ww2.codechef.com/viewsolution/2161375 maybe the f.append() is taking more time, but I am not yet satisfied with why it says TLE as append() is mostly O(1) http://wiki.python.org/moin/TimeComplexity