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, In English

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?

Thanks for taking your time and reading this!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

% 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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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;
        }
    }