Problem Name: Boxes
Judge: timus online judge
Problem ID: 1114 ( vol 2 )
Link to the problem: http://acm.timus.ru/problem.aspx?space=1&num=1114
Techniques Required: Combinatorics, DP
Problem Statement:
N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blue ones) are exactly the same. You can place the balls in the boxes. It is allowed to put in a box, balls of the two kinds, or only from one kind. You can also leave some of the boxes empty. It's not necessary to place all the balls in the boxes. Write a program, which finds the number of different ways to place the balls in the boxes in the described way.
My Solution:
Initially I have thought of solving this using a 3-D DP table with the states as no.of boxes,no. of red balls and no. of blue balls. But I was unable to form a correct recurrence equation. After some thinking I have found a method to solve this using a 2-D DP itself. Before doing the actual calculation let us calculate the value of nCi using the pascal triangle i.e nCi = (n-1)Ci+(n-1)C(i-1). One thing I noticed is that we can solve the simpler version of this problem easily i.e consider that there were only balls of red color. This can be computed easily using a 2-D DP table with states as no. of boxes and no. of red balls.Here dp[i][j] = no. of ways in which we can place ‘j’ red balls in ‘i’ boxes. This value is just the value which we have precomputed i.e (i+j-1) C (i-1). Hurreah!! We have solved a simpler version of the original problem. Just one more step and we are Complete. One symmetrical property which we can notice is that the type of the ball here doesn’t matter and hence we can compute the answer for the original question using this single DP table which we have calculated. Convince yourself that the answer to the entire question is just the following one line code:
for(i=0;i<=r;i++) {
for(j=0;j<=b;j++) ans+=dp[n][i]*dp[n][j];
}
Where r -> no. of red balls
b -> no. of blue balls
n -> no. of boxes
The above equation is just an application of product rule. As a last tip don’t forget to use unsigned long long.
Notice how powerful of DP. Most of the DP solutions will have utmost 2 or 3 lines of code but figuring out that 3 lines will be the mammoth task!!! Finally, Have fun coding!!! J J
Judge: timus online judge
Problem ID: 1114 ( vol 2 )
Link to the problem: http://acm.timus.ru/problem.aspx?space=1&num=1114
Techniques Required: Combinatorics, DP
Problem Statement:
N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blue ones) are exactly the same. You can place the balls in the boxes. It is allowed to put in a box, balls of the two kinds, or only from one kind. You can also leave some of the boxes empty. It's not necessary to place all the balls in the boxes. Write a program, which finds the number of different ways to place the balls in the boxes in the described way.
My Solution:
Initially I have thought of solving this using a 3-D DP table with the states as no.of boxes,no. of red balls and no. of blue balls. But I was unable to form a correct recurrence equation. After some thinking I have found a method to solve this using a 2-D DP itself. Before doing the actual calculation let us calculate the value of nCi using the pascal triangle i.e nCi = (n-1)Ci+(n-1)C(i-1). One thing I noticed is that we can solve the simpler version of this problem easily i.e consider that there were only balls of red color. This can be computed easily using a 2-D DP table with states as no. of boxes and no. of red balls.Here dp[i][j] = no. of ways in which we can place ‘j’ red balls in ‘i’ boxes. This value is just the value which we have precomputed i.e (i+j-1) C (i-1). Hurreah!! We have solved a simpler version of the original problem. Just one more step and we are Complete. One symmetrical property which we can notice is that the type of the ball here doesn’t matter and hence we can compute the answer for the original question using this single DP table which we have calculated. Convince yourself that the answer to the entire question is just the following one line code:
for(i=0;i<=r;i++) {
for(j=0;j<=b;j++) ans+=dp[n][i]*dp[n][j];
}
Where r -> no. of red balls
b -> no. of blue balls
n -> no. of boxes
The above equation is just an application of product rule. As a last tip don’t forget to use unsigned long long.
Notice how powerful of DP. Most of the DP solutions will have utmost 2 or 3 lines of code but figuring out that 3 lines will be the mammoth task!!! Finally, Have fun coding!!! J J