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 : CodeChef: Practical coding for everyone

Happy Coding :slight_smile:

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

6 Likes

@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

@code_hard123 good explanation :slight_smile:

1 Like

@code_hard123 thankyou

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

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
I understood your aced solution but I am not getting why this is correct, can you please explain it’s correctness.