DONATE - Editorial

Donation - EDITORIAL:

Practice

Contest

Author: kishen1912000
Editorialist: kishen1912000

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming, Combinatorics, Stirling Numbers

PROBLEM:

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

EXPLANATION:

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)

SOLUTIONS:

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
    else:
        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
    print(dp[n][c])
2 Likes

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.
dp[n][c]=c∗dp[n−1][c]+(n−1)∗dp[n−2][c−1]

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.

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.