shisukenohara's blog

I need help in problem: Codeforces 431C — k-Tree
By shisukenohara, history, 5 weeks ago, In English

I am new at CP, and have only given one contest Can someone please help me and tell me what is wrong in my approach for the question 431C - k-Tree. I am trying Dynamic Programming.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

const int MOD = 1000000007;
vector<vector<int>> memo;

int dp(int k, int n, int d, int found)
{
  if(n==0)
  {
    if(found) return 1;
    else return 0;
  }
  if(n<0)
  {
    return 0;
  }
  if(memo[n][found]!=-1)
  {
    return memo[n][found];
  }
  int total = 0;
  for(int i=1; i<=k; i++)
  {
    if(n-i < 0) break;
    total = (total%MOD + dp(k, n-i, d, found || i>=d)%MOD)%MOD;
  }
  return memo[n][found] = total%MOD;
  
}

int32_t main() 
{
  int k, n, d;
  cin >> k >> n >> d;
  memo = vector<vector<int>>(n+1, vector<int>(2, -1));
  cout << dp(k, n, d, 0) << "\n";
  return 0;
}

Fails on Test case 5: 4 3 2

Expected: 6

Output: 3

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

do cin >> n >> k >> d;

→ Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Apart from your question, which I think was resolved, a side note you can observe is that this problem really is a knapsack in disguise. This is same as having an unlimited supply of numbers in the range 1 to k and we are suppose to count ways in which we can sum numbers to n, while using an element >= d at least once. You can prove that each path in the tree which sums to $$$n$$$ and each solution to $$$x_1 + x_2 +... x_j = n$$$ has a one to one correspondence.

Such a problem will have an implementation like this:
→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unbounded knapsack indeed Aspergillus :)

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

    Bro I am facing problem in new question

    please help me

    My Blog For Discussion

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

      sorry man a little tired right now, also I prefer iterative dp over memoisation unless I literally cant do it any other way so yeah... maybe check out my solution? I think I added a comment for understanding, it's clean too look at it once this if you wish.

      → Reply