Field Trip ,getting TLE

general
,
1

CodeChef: Practical coding for everyone . 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 ( CodeChef: Practical coding for everyone ). Thanks in advance.

1 Like
2

You need to precalculate the combinations(n,k) table.

3

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 .

4

@timepass123 :

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

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

But in the passed solution he has not pre calculated that.

6

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]
7

Sorry, the link that I given was wrong. Check the 2nd accepted solution of the same user.

8

CodeChef: Practical coding for everyone . Please refer this solution. In this he has not pre calculated. But still it is accepted.

9

Seems he’s caching the Factorial instead of “n choose k”

10

first I thought this too, but timepass123 is doing the same as far as I can see…

11

@srihari : I tried same approach to calculate nCr as you. Still I got TLE. CodeChef: Practical coding for everyone . I think my luck is bad :slight_smile:

12

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

13

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?

14

In Java I also tried precalculating factorials, but still computing nCr was incredibly slow. Interesting that the above solution got AC.

15

@vineetpalwal : I dint calculate factorial every time . I calculated and stored it.

16

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): CodeChef: Practical coding for everyone [ 2.19s, cached]

17

@kshitij8 >> What do you mean long multiplications? Here’s my AC python solution CodeChef: Practical coding for everyone

In your submission CodeChef: Practical coding for everyone 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) TimeComplexity - Python Wiki