Field Trip ,getting TLE . 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 ( ). 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.


dp = [[0 for i in range(1009)]for i in xrange(1009)]

for i in range (0,1006):

for i in range(1,1006):
	for j in range(1,1006):

Sorry, the link that I given was wrong. Check the 2nd accepted solution of the same user. . 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. . I think my luck is bad :slight_smile:

@srihari : . nCr is calculated in the same method as you have done. Still I am getting TLE :frowning:

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): [ 2.19s, cached]

@kshitij8 >> What do you mean long multiplications? Here’s my AC python solution

In your submission 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)

@timepass123 :

Have a look. Corrected your code.

  • May be tle due to i/o style.