Shinigami and Apples - Editorial

Prerequisites : DP , Maths

Difficulty : Medium

Expected Complexity : O(N*M + T).

Editorial :

The very first thing to observe is that since each of the apple received is distinct , one of the ways is surely going to be of the form : a1 < a2 < a3 < … < an , where ai denotes apples received by ith shinigami. If we find the number of ways to arrange this , we can multiply this by N! to find all possible distinct ways. So our problem reduces to finding the number of ways to distribute M apples such that a1 + a2 + a3 + … + an = M and 0 < a1 < a2 < … < an.

Let’s rewrite each ai as ai = a(i-1) + 1 + yi , where yi >= 0.

a1 = 1 + y1;

a2 = a1 + 1 + y2;

a3 = a2 + 1 + y3;

an = a(n-1) + 1 + yn;

Replacing all a(i-1) in ai , we get :

a1 = 1 + y1;

a2 = 2 + y1 + y2;

a3 = 3 + y1 + y2 + y3;

an = n + y1 + y2 + … + yn;

summation of all ai = 1 + 2 + 3 + … + n + n*y1 + (n-1) * y2 + (n-2) * y3 + … yn;

renaming our yi as y(n-i+1) , we can get :

sum = n*(n+1)/2 + summation i*yi;

M - n*(n+1)/2 = summation i*yi;

now if lhs < 0 , then answer is 0.

otherwise K = summation i*yi , where yi >= 0;

we can easily solve this using the recurrence : solve(i,K) = solve(i-1,K) + solve(i,K-i).

In short, the answer is : N! * solve(n , m - n(n+1)/2).*

2 Likes

Hi

Thanks for the editorial. I am unable to understand the solve function you used. I was stuck on that part for about half of the contest time. can you please elaborate your recurrence part of solution.

thanks

Hi, sorry for the late reply. Let’s suppose you have to find the number of ways to partition a number “X” such that y1 + (2 * y2) + (3 * y3) + … (n * yn) = X , and all yi >= 0. The states of our dp is (i,k) which denotes that we have to partition for all yj (j <= i) the sum left to partition is k. Our transitions are :

  1. (i , k) -> (i - 1 , k) : We can add 0 to the current yi and move to solve the problem for (i-1 , k).
  2. (i , k) -> (i , k - i) : Suppose we try to add 1 to the current yi , then its contribution in the sum would be i * 1 = i. So the sumleft would be current sum - i.
1 Like
//