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
You input line is opposite, It should be
cin>>x>>n
instead ofcin>>n>>x;
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.)
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.
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)
Actually, it's more about cache locality: when you load
dp[i][j]
processor loads some kind of page with other elements from same vectordp[I]
, sodp[i][left]
might be actually in cache, so load to it might be fasterFor more info on this issue on this specific problem, see here.