Why am I getting TLE on CSES Coin Combination 2?

Question

I was trying CSES problem set and I ran into this dynamic programming problem. i couldn't figure out how to optimize it further.

Here is the link to the original question.

#include <iostream>
    
using namespace std;
    
typedef long long ll;
    
ll dp[1000005], mod=1e9+7, coins[105];
    
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, x;
  cin>>n>>x;

  for (int i=0; i<n; i++) {
    cin>>coins[i];
  }

  dp[0]=1;

  for (int j=0; j<n; j++) {
    for (int i=1; i<=x; i++) {
      if (coins[j] <= i)
        dp[i] = (dp[i] + dp[i - coins[j]])%mod;
    }
  }

  cout<<dp[x]<<endl;
  return 0;
}

My Submission Screenshot:

Dou know wheher the coins values are given in an ordered sequence? If not sort the coins array. Then the loop-loop-if-construct can be unnested a little. — Yunnosch, Dec 24 '20 at 11:32
@Yunnosch I have missed the algorithm part before, now I have come up with the new answer. Thanks — Shovo, Dec 24 '20 at 11:50

Shovo · Answer 1 · 2020-12-24T12:04:38.557

0

According to the question and your solution n can be 100 and x can be 10^6. Your solution has a nested for loop which will eventually make the complexity of your program O(n*x) which can be 10^8 in the worst case.

for (int j=0;j<n;j++){
    for (int i=1;i<=x;i++){
        if (coins[j]<=i)
            dp[i]=(dp[i]+dp[i-coins[j]])%mod;
    }
}

I think you can sort the coin value which will optimize your time complexity.

And after this, you can give it a try using scanf? Using cin can be costly (in terms of time) though you have taken certain measures.

edited Dec 24 '20 at 12:04

answered Dec 24 '20 at 11:49

Shovo

133
2
9

@Yunnosch, I should have edited the answer instead of deleting it, my mistake. – Shovo Dec 24 '20 at 11:55
The first part of your answer points out something which obviously is related to the TLE, but i do not see the insight you provide on hwo to solve that. – Yunnosch Dec 24 '20 at 11:55
@Yunnosch if the coin value is sorted before the nested loop calculation, I guess it would optimize the complexity. – Shovo Dec 24 '20 at 12:03
You are aware that you are practically quoting my comment and my answer with that, aren't you? And sorting alone does not help. (Well it might help, but then you need to discuss why.or refer to https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array?rq=1 .) – Yunnosch Dec 24 '20 at 12:04
I have solved this type of problem before, that's why gave that insight and your comment also helped me to come to conclusion. But thank you, I will consider these issues while answering the question next time. – Shovo Dec 24 '20 at 12:12
I switched to scanf and it still appears to be TLE, as cin and scanf aren't really called in the loop, it shouldn't matter much to the time right? – Maizhe Yang Dec 24 '20 at 12:24
Also, a time complexity of 10^8 should pass on a modern day computer right? – Maizhe Yang Dec 24 '20 at 12:30
@MaizheYang it depends on the machine where the setter is running. But from my experience, I can say that 10^8 won't run in those machines within this time constraint. and for scanf, you are right as the number of times cin is used, it would not matter that much. – Shovo Dec 24 '20 at 12:34

score 0 · Answer 2 · answered Dec 24 '20 at 12:01

0

Consider this test case

500 10
1 10 20 30 40 50 60 70 80 90 ... 4990

How many way do you see to make 10 from those coins?
There are only 2 and I never have to think about using coins > 10.
You need to be able to take a short cut in weird cases like this.
A well-aimed condition can skip a lot.
And if, like in my case, you can rely on the coin values being sorted you can even get the loops noticably shorter. Try it. If it fails try sorting the coin values first, that should pay of.

answered Dec 24 '20 at 12:01

Yunnosch

26,130
9
42
54

It is interesting to do sorting here, but I think those test cases aren't that special like yours, is there perhaps other conditions that I can employ? Here is my code which is still TLE. https://cses.fi/paste/b96c7449103d8d4515b2c5/ – Maizhe Yang Dec 24 '20 at 12:26
I would not dismiss weird test cases. Those challenges make a point of considerung edge cases and they are absolutely sure to have large test cases. Remember that dynamic programming is not only about assembling solutions from "smaller" solutions (similar to recursion), but also about avoiding the unnecessary ones. – Yunnosch Dec 24 '20 at 12:31

score 0 · Answer 3 · answered Dec 25 '20 at 05:32

Thanks everyone for help! I finally figured out what caused my program to go TLE. Turns out it was the use of long long in the arrays. I changed it to int type and now it is accepted. Here is my final code. I found an explanation here as to why.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000005], mod=1e9+7, coins[105];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x;
    cin>>n>>x;
    for (int i=0;i<n;i++){
        cin>>coins[i];
    }
    dp[0]=1;
    for (int j=0;j<n;j++){
        for (int i=1;i<=x;i++){
            if (coins[j]<=i)
                dp[i]=(dp[i]+dp[i-coins[j]])%mod;
        }
    }
    cout<<dp[x]<<endl;
    return 0;
}

can you write recusive approach ? I had written a recrusive approach using 2 vairable for a state and getting tle because of the same reason that n can be 100 and target can be 1000000. Here is my code https://cses.fi/paste/e690e97bf8068ba92cf0cf/ — randomUser, Oct 04 '21 at 19:35

Why am I getting TLE on CSES Coin Combination 2?

3 Answers3