How to solve it ?

https://www.codechef.com/PCR12020/problems/BHARAT

The problem can be simplified to number of solutions of

x1 + x2 + x3 +. . . . +xn =k. where each xi is the number of times i appears in the array of length k;

here there is no need to arrange them because they need only be selected (the arrangement is fixed). now the answer is simply (n-1+k)C(k). Just make sure you use modular arithmetic correctly.

link to my submission https://www.codechef.com/viewsolution/33159613

can anybody share their dynamic programming approach ?

Let dp_{ij} denote the number of ways to write an array of length j which end with i. Now we can see dp_{ij}=\sum_{k=i}^N dp_{k(j-1)}. We can calculate this quickly using prefix sums.

This solution is O(nk) whereas the combinatoric solution is O(n+k)

refer this link,

https://www.quora.com/If-a+b+c+d-20-how-many-unique-non-negative-integer-solutions-exist-for-a-b-c-d

Thanks for help !

Apparently I did the same using recursion + memo but TLEd !

What am I doing wrong ?

https://www.codechef.com/viewsolution/33159734

You have to use prefix sums to calculate dp. If you calculate the sum every time, your code is O(n^2 k)

how can I modify this recur + memo approach to make it O(nk) ?

How did you get (n-k+1)Ck ?

You can modify it by recurring over (last - 1, length) + (last, length + 1) instead of calculating the prefix sum for every n, that way you get the common prefix by just recurring over (last - 1,length) and the extra part to be added is (last,length + 1). Also you would need to work from 1 to n in the solve function instead of n to 1 as we iterate over (last - 1, length).

Here is my very easy and understandable DP solution with space as well as time complexity of O(n.k).

simply apply dp[i][j]=dp[i-1][j]+dp[i][j-1]…

where i=number of elements from 1 to i that can be used to put as values in array

j=size of array

https://www.codechef.com/viewsolution/33160653

@sharath1999 let’s look at the problem again no. of solutions of : x1+ … + xn=k.

The answer for this can be understoodby the following model

consider a string with (n-1) no. of ls and k Os we have to find no. of permutations. In each permutation the ls divide the string into n parts where each part has some Os (0 to k) for eample with 3 ls and 5 Os OOlOlOOl here the %Os are divided as 3,1,2,0.

This example shows that our logic is correct and both problems have the same answer.

which is **no. of permutations of (n-1) things of one type and k things of another type.**

**ANSWER (n-1+k) ! /(n-1) ! * (k) ! which happens to be (n-1+k)C(k).**

Thanks man! That is a really cool solution

Can you explain how the statement consider root as Node-1 in problem hanuman and tree meant root is 1