Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

### Kaleab_Asfaw's blog

By Kaleab_Asfaw, history, 12 months ago,

Getting TLE with a python solution for Coin Combination problem in here

I know that python is slow ..., but have seen other python users solving it here

My Code

Creating the dp 2D array is even taking much time. Is there a way it can be optimized?

 » 12 months ago, # | ← Rev. 2 →   0 % operator is slower than addition and subtraction, so for addition, let's try to do something better, which might slightly optimize the code. We know if we add A and B where $A, B < MOD$, then what this tells us about $A + B$ is that $0 <= A + B < 2*MOD - 1$, so we can just subtract mod from our result if it is >= MOD, because we know that this will make our result less than mod and greater than equal to 0. dp[i][j] += dp[i-1][j];if(dp[i][j] >= mod) dp[i][j] -= mod;rather than always using a mod operation
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 Thanks, for the idea I have edit it and tried but still, I got TLE. dp = [] for i in range(n+1): temp = [1] + [0]*x dp.append(temp) This part is taking around 6 sec to create the array. Is there something been done to optimize it?
 » 12 months ago, # |   0 The dp can be 1 dimensional, let c[] be the coins and x the sum, then dp[x] is the answer:  dp[0]=1; for(int a : c) { for(int i=0; i+a<=x; i++) { dp[i+a]+=dp[i]; dp[i+a]%=MOD; } }