Anybody, please write the editorial for this problem.
and also refer me to some good resources to learn combinatorics. I always give up on such problems.
1 Like
Hi @arpit728 ,
First of all , let you know that this is not a combinatorics problem.
It’s a simple dp problem.
Let me explain you…
let dp[i][j] = number of ways of arranging j people into i spaceships.
where i = number of spaceship used
j = number of people
So the ith spaceship can hold only at max of a[i] people.
i.e ith spaceship may hold 0 or 1 or 2 or 3 or… a[i] people.
We should try to consider each possible arrangement.
So, the dp formation goes like this :
dp[i][0] = 1 (for all i) since it is always possible to hold 0 people in any spaceship.
dp[0][i] = 0 (for all i > 0) since it is never possible to hold one or more people using no spaceship.
for( i = 1 to n) {
for( j = 1 to n) {
for( k = 0 to min( j , arr[i])) {
dp[i][j]+ = dp[i-1][j-k];
// upto (i-1)th spaceships we have arranged (j-k) people so , the remaining k people will be seated on ith spaceship.
}
}
}
ans = dp[n][m] // number of ways of arranging m people into n spaceships.
Here’s my ACed solution : https://www.codechef.com/viewsolution/8985425
Happy Coding 
PS: If you like the answer, upvote it.
6 Likes
@code_hard123
Suppose there are two space ships and each can hold 5,5 people and there are total three people than this pseudo code will yield following matrix:-
1 1 1 1
0 1 3 4
0 1 4 8
then ans=8 but in this case answer should be 4 as per the test given in the condition.
@arpit728 No ! the dimension of dp formed will be N X M . For the sample testcase , size of dp will be 2 X 3 .
Table formed will be this :
1 1 1
2 3 4
so dp[n][m] = 4 is the ans.
3 Likes
ok and please explain, how are we taking max capacity of each spaceship into consideration.and also explain logic behind this inner for loop
for( k = 0 to min( j , arr[i])) {}
refer my code for better understanding. and upvote the answer and mark it correct if you feel so
1 Like
@code_hard123
I understood your aced solution but I am not getting why this is correct, can you please explain it’s correctness.