In the problem k-tree on codeforces, i tried the following approach but it doesn’t seem to work, can someone please take a look at it and tell me where I’m wrong?
My Approach:
We’re asked to calculate the number of paths starting from the root have a total weight n, with a slight twist that each path must consist of at least one edge with weight at least d.
So what i thought is that I essentially need to calculate all the paths starting from the root having the required weight(without any restrictions), and subtract from it the number of paths where no edge has a weight greater than or equal to k.
the function formulation was as follows:
let f(sum,k) be the paths from root with weight equal to sum and the maximum weight that any edge can have as k, then the required answer should be:
f(n,k)-f(n,d-1) where n is the weight required, k is the maximum weight of any edge and d is the weight, such that at least one edge with weight greater than or equal to this must be present.
I’ve checked the code several times and couldn’t find any deviation in it from my thinking so I wondered if you guys could help me figure out what’s wrong with my approach.
Thanks.
Here’s my approach:
State
dp[N][D] denotes number of paths to make sum N with D as max edge weight
Transition
Let i be the current sum, j be the max edge weight on the last path, and l be the current edge weight that is to be used, then,
dp[i][max(j, l)] = dp[i][max(j,l)] + dp[i-l][j]
Complexity
O(NK^2)
Code
void solve(int tc = 0) {
cin>>n>>k>>m;
//dp[N][K] Sum N, K used
ll dp[n+1][k+1];
memset(dp, 0, sizeof(dp));
dp[0][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
for(int l=1;l<=min(k, (ll) i);l++){
dp[i][max(j, l)] = (dp[i][max(j,l)] + dp[i-l][j])%mod;
}
}
}
ans=0;
for(int i=m;i<=k;i++)ans= (ans + dp[n][i])%mod;
cout<<ans<<'\n';
}