problem in solving "Stupid question" from shastra online contest

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 :slight_smile:

PS: If you like the answer, upvote it. :slight_smile:

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 :slight_smile:

1 Like

@code_hard123 good explanation :slight_smile:

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.

@code_hard123 thankyou

4 Likes
//