FILLBOX - Editorial

Problem Link : CodeChef: Practical coding for everyone

Let A be the array that consist of number of nodes ending at Q at a particular level
A = { 0, 1 , 1, 3 }

Let B be the array that consist of number of nodes NOT ending at Q at a particular level
B = {1, 1 , 3, 5 }

Convention : Favourable nodes ( ending at Q )
Non Favourable nodes (NOT ending at Q)

On carefull observation it may be noted that:

  1. A[i] = B[i-1]
    Reason :
    All the favourable nodes ( ending at Q ) will only be produced by non favourable nodes of the previous level.

  2. B[i] = A[i-1] X (K – 1) + B[i-1] X (K – 2)
    Reason :
    a) For A[i-1]*(K – 1) , some of the non favourable nodes are produced by favourable nodes of the previous level , multiply by (K – 1 ) as each favourable node will produce K-1 non favourable nodes

b) For B[i-1]*(K – 2) , rest of the non favourable nodes are produced by non favourable nodes of previous level, multiply by (K-2) , as one produced node is favourable, so we subtract 2 from this.

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

class element
    long long int a;
    long long int b;
int main()
{   long long int test;
    cin >> test;
        long long int n, k, p, q;
        cin >> n >> k >> p >> q;
        element *dp = new element[n];
        // if the number of balls in the first box is same as in the last box
        // then
        if (p == q)
            dp[0].a = 1;
            dp[0].b = 0;
            dp[0].a = 0;
            dp[0].b = 1;

        // dp approach as mentioned in the text
        for (int i = 1; i < n; i++)
            dp[i].a = dp[i - 1].b;
            dp[i].b = (dp[i - 1].a * (k - 1)) % MOD + (dp[i - 1].b * (k - 2)) % MOD;
            dp[i].b %= MOD;
        cout << dp[n - 1].a << endl;

Isn’t this problem almost same as this problem?

1 Like

Thanks, awesome editorial. but there is a typo in if(p==q) it should be dp[0].a=1 and dp[0].b=0;


There are millions of cp questions and many of them revolve around the same philosophy.
CP is practice. So the moto is ,you were not able to google questions and get the solution.

It is only the practice and presence of mind that will gear you up. :upside_down_face: :upside_down_face:

1 Like

@piyushbhutani But you should not give a copied problem in a public contest(with prizes/laddus).
because many person could have copied the solution from hackerrank.

1 Like

Yes, it is about practice, and I already had encountered this problem in hackerrank (and couldn.'t solve) while practicing some days ago, so seeing the problem it reminded me of the same and got the solution by googling this, but I didn’t submit the solution.

1 Like

I will pay heed to your words. This is our first contest. But this is not a copied problem.
Thanks buddy. I will learn from my this mistake.:blush::blush:


If the above explanation is still unclear to anyone, follow this- Solution Video

Your diagram is a bit wrong, which can bring others into confusion, just update the node numbers

the node numbers shouldn’t be 2->3->3->(2 or 1)
but must be 2->3->2->(3 or 1)

1 Like

This is very much similar to Tetrahedron problem on codeforces. :smile: