Field Trip ,getting TLE

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.

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 .

@timepass123 :

Have a look. Corrected your code. http://ideone.com/qw87iB

  • May be tle due to i/o style.
4 Likes

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…

@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 :slight_smile:

@srihari : http://ww2.codechef.com/viewsolution/2157930 . 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): 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