DONATE - Editorial

Donation - EDITORIAL:



Author: kishen1912000
Editorialist: kishen1912000




Dynamic Programming, Combinatorics, Stirling Numbers


Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number (1, 2 or 3) is fixed.]


Let dp[n][c] denote the number of ways of distributing n coins to c charities. Then, a recursion relation can be derived in each of these cases:

At least 1 coin each:

dp[n][c] = c*dp[n-1][c] + dp[n-1][c-1]
Where, the first term denotes the number of ways of distributing n-1 coins to c charities and then distribute the n^{th} to any one, which can be done in c ways. The second term denotes the number of ways of distributing n-1 coins to c-1 charities and the n^{th} coin is given to the c^{th} charity.
Similarly, we get the following recurrence relations in the other two cases:

At least 2 coins each:

dp[n][c] = c*dp[n-1][c] + (n-1)*dp[n-2][c-1]

At least 3 coins each:

dp[n][c] = c*dp[n-1][c] + \binom{n-1}{2}*dp[n-3][c-1]

The final answer required in each case is dp[N][C]. As the number is huge, use modular arithmetic appropriately where required.

Time Complexity:

O(T\times N\times C)


Setter's Solution
M = 10**9+7
def choose(n,k):
    if k==1:
        return n
    elif k==2:
        return (n*(n-1)//2)%M
        return 1

for _ in range(int(input())):
    n,c,q = [int(s) for s in input().split()]
    dp = [[0 for i in range(c+1)] for j in range(n+1)]
    for i in range(1,n+1):
        dp[i][1] = 0 if i<q else 1
    for j in range(2,c+1):
        for i in range(j*q,n+1):
            dp[i][j] = ((choose(i-1,q-1)*dp[i-q][j-1])%M + (j*dp[i-1][j])%M)%M

Editorial is top class. I just couldn’t get the recurrence relation used for the at least 2 and 3 coins. Like why did we multiply by (n-1) for at least 2 coins. I would be really obliged to you if you kindly reply. Much of my time would be saved.

Hey @kishen1912000,
I formulated a solution to this problem in a different way, and it is giving correct answer for small cases. I checked my code vs an AC code by generating 500 random test cases.
Although, I have a O(n* n* c) approach and my code is getting TLE which is understood but, atleast my answer should match.
It is matching for all the 500 test cases where the solution does not exceed the int limit.
TLE is one thing but if I somehow optimize my approach then also, I won’t get AC because of the mod thing.
So, this limits to solve this question by exactly using the above stated approach.
Here’s the link to my code.

1 Like

Thanks @insha2k.

As we know that the coins are unique, so, in the at least 2 coins case, first we find the number of ways of distributing n-1 coins to c charities, and then distribute the final coin to one of the charities. This gives the term c*dp[n-1][c] .
In the other case, we pay to c-1 charities, and then pay to the c^th charity. We need 2 coins to pay the c^th charity. Thus, along with the n^th coin, we choose one coin from the remaining n-1 coins to give to this c^th charity. Thus, no. of ways is (n-1)*dp[n-2][c-1].
At least 3 case can be handled similarly.
These recurrences can be proved by induction.

1 Like