WayBig's blog

By WayBig, history, 11 months ago, In English

I am facing Time Limit Exceeded in the problem Coin Combinations II of cses.

Code:

Full code

My approach: We define rec(x, r) as the number of ordered ways to make a sum x by using up to rth coin (0-indexing). Now we are iterating from the last coin. We can either take rth coin and add up rec(x — c[r], r) to our answer or we can not take the rth coin and simply add up rec(x, r-1) (the answer by taking up to (r-1)th coin). So we have:

dp[i][j] = dp[i - c[j]][j] + dp[i][j - 1]

We also do dp[i][j] %= MOD to prevent overflow.

What could be the possible reason for Time Limit Exceeded? Thank you.

UPD: One person in the comments told that it is because constraints on CSES are tight and that's why recursion might give a TLE on CSES. I think that answers the question.

UPD: This is the exact reason for the TLE

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's about the recursive code. Most of the recursive solution for DP doesn't work on the CSES Dp problem set.

Write the same logic as Iterative DP, you are good to go.

Reason: I think the Constraints on CSES are very tight, that's why It throws TLE on Recursive calling.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh. Yeah, I also submitted the iterative code and it did get accepted. But I was wondering why the recursive one is throwing TLE?

    Thanks a lot.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by WayBig (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by WayBig (previous revision, new revision, compare).

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

What is the size of your memoization array? I saw the iterative solution but that has only one stat, where my recursive solution has two stats.

I used to believe that recursive and iterative approach only differ by constant factor in time conplexity. But Now I think recursive solution needs more stats too. As I used a 2D dp array of size n * x, I already knew it was not going to work. But seeing the tabulation is running with only one stat, I tried to implement that in recursive way but couldn't get any clue.