X-O__O-X's blog

strange bug causes TLE !
By X-O__O-X, history, 4 years ago, In English

I was solving the problem: coin combination II from CSES. https://cses.fi/problemset/task/1636/

My solution leads to TLE. 

#include <bits/stdc++.h> 
using namespace std; 
 
 
int 
main() {
 
    int mod = 1e9+7;
	int n, x; 
    cin>>n>>x; 
    vector<int> c(n);
    for (int &a : c) cin >> a;
 
    vector<vector<int>> dp(x+1,vector<int>(n+1,0));
    dp[0][0] = 1;
    for (int i = 0; i <= x; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i][j-1]; 
            int up = i - c[j-1]; 
            if (up >= 0)
            {
                (dp[i][j] += dp[up][j]) %= mod; 
            }
        }
    }
    cout << dp[x][n] << endl;
}

But solution in this editorial leads to AC..

#include <bits/stdc++.h>
using namespace std;

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int&v : x) cin >> v;

  vector<vector<int>> dp(n+1,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  cout << dp[n][target] << endl;
}

The only difference I see is the why the DP table is set.. and consequently the way in which we compute it.

in my solution, dp[i][j] => number of ways to make sum i using first j coins.

in editorial solution, dp[i][j] => number of ways to make sum j using first i coins.

but, the number of iterations is exactly the same..

any explanations ?

thanks

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You input line is opposite, It should be cin>>x>>n instead of cin>>n>>x;

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I believe your issue is that you're creating one million vectors with 100 entries which carries allot more overhead than 100 vectors with one million entries each. Switching which vector you look at one million times is probably what's causing it to take so long (8 seconds when I tested it locally vs 0.5 seconds with the editorial solution.)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    That's probably correct.. thanks so much..

    When i use a global array int dp[1000001][101] for my solution.. again TLE.

    yet if i use a global array int dp[101][1000001] for editorial solution.. it works fine..

    I think same reason may apply.. creating 101 array each 1000001 cells is cheaper than 1000001 array each 101 cells.. for some reason!

    UPD; I was wrong, Both cost same.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Creating these arrays cost same,because in c++ all that matter is total size of structure (note that vector has some overhead for size and capacity)

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, it's more about cache locality: when you load dp[i][j] processor loads some kind of page with other elements from same vector dp[I], so dp[i][left] might be actually in cache, so load to it might be faster

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For more info on this issue on this specific problem, see here.

→ Reply