BHARAT from ‘Ramayan’

1

How to solve it ?

2

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 CodeChef: Practical coding for everyone

1 Like
3

can anybody share their dynamic programming approach ?

4

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)

1 Like
5

refer this link,

6

Thanks for help !
Apparently I did the same using recursion + memo but TLEd !
What am I doing wrong ?
https://www.codechef.com/viewsolution/33159734

7

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

8

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

9

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

10

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).

2 Likes
11

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

12

@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).

1 Like
13

Thanks man! That is a really cool solution

14

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