CF 431C: k-Tree problem DP recurrence giving WA on large test cases

Revision en2, by vrintle, 2021-12-10 08:23:08

Problem: https://codeforces.me/problemset/problem/431/C

I started solving this one by thinking a $$$DP[sum][level]$$$ state, which means ways to achieve a given sum on a given level, and the maximum number occurring in the sum. And, I coded its recurrence similar to subset sum as,

vector<vector<pair<ll,ll>>> dp(n+1, vector<pair<ll,ll>>(n+1, { 0, 0 })); 
// dp[i][l]: sum i at level l, { ways, max }
dp[0][0] = { 1, 0 };

for(ll i = 1; i <= n; i++) { // level
  for(ll j = 1; j <= k; j++) { // number
    for(ll s = n; s-j >= 0; s--) { // sum
      if(dp[s-j][i-1].first > 0) {
        // j is added to s-j sum from prev level, making a sum of s in the curr level
        dp[s][i].first = (dp[s][i].first + dp[s-j][i-1].first) % M;
        // adjusting the max of curr level with j
        dp[s][i].second = max(j, dp[s-j][i-1].second);
      }
    }
  }
}

And, after computing the required DP states, I am adding the ways of making sum $$$n$$$ from each level $$$i$$$, when $$$max >= d$$$ as,

ll ans = 0;
for(ll i = 1; i <= n; i++) {
  if(dp[n][i].second >= d) ans = (ans + dp[n][i].first) % M;
}
cout << ans;

For some reasons, this is giving wrong answer verdict on test 5, can anyone kindly explain me why it is incorrect and how to improve it?

Submission link: https://codeforces.me/contest/431/submission/138596746

Tags dynamic programming, 431c, recurrence, trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vrintle 2021-12-10 08:23:08 0 (published)
en1 English vrintle 2021-12-10 08:22:01 1432 Initial revision (saved to drafts)