Shinigami and Apples - Editorial

editorial
, , , ,
1

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
2

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

3

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