Link to the problem on Timus Online Judge
After I read the problem statement, I tried to think of a popular technique. First I noticed the number of red balls and blue balls. I tried to fix the number of red balls and blue balls chosen to put in the boxes with two for loops. Now I have n boxes and A1 red balls and B1 blue balls which are the same and must be put in the boxes. Another observation is that the arrangement of red balls and blue balls are not related to each other, so the overall answer is the multiplication of the answer for red balls and blue balls, which is calculated separately.
Let's denote the number of balls in the i-th box with Xi, then the answer for red balls is the number of answers to this equation X1 + X2 + ... + Xn = A1 : st. Xi >= 0. This is a classic problem in combinatorics and the number of solutions to this equation is equal to Combination(n-1, A1 + n-1), the same holds for B1, and the number of solutions for Blue balls is Combination(n-1, B1 + n-1), so for this fixed A1 and fixed B1 the answer is Combination(n-1, A1 + n-1) * Combination(n-1, B1 + n-1).
But there is another Cute combinatorial solution which needs no for loops over the number of red balls and blue balls. Let's add another box, if some balls are not put in the first n boxes, then we put it in the last box. So the answer for Red balls is the number of solutions to this equation : X1 + X2 + ... + Xn + X(n+1) = A : st Xi >= 0. Answer to this problem is Combination(n, A+n), and finally the over all answer is Combination(n, n+A) * Combination(n, n+B).
There is another solution to this problem using Dynamic Programming.
The state to our solution in DP is dp[boxi][a][b], we are on boxi, we have a red balls and b blue balls, we choose how many balls we want for boxi.
dp[boxi][a][b] = SUM{ dp[boxi+1][a-i][b-j] : such that i=0...a j=0...b }
and we know dp[n+1][xx][yy] = 1, it means we have filled the first n boxes and there are xx red balls and yy blue balls chosen to be out of boxes :)
After I read the problem statement, I tried to think of a popular technique. First I noticed the number of red balls and blue balls. I tried to fix the number of red balls and blue balls chosen to put in the boxes with two for loops. Now I have n boxes and A1 red balls and B1 blue balls which are the same and must be put in the boxes. Another observation is that the arrangement of red balls and blue balls are not related to each other, so the overall answer is the multiplication of the answer for red balls and blue balls, which is calculated separately.
Let's denote the number of balls in the i-th box with Xi, then the answer for red balls is the number of answers to this equation X1 + X2 + ... + Xn = A1 : st. Xi >= 0. This is a classic problem in combinatorics and the number of solutions to this equation is equal to Combination(n-1, A1 + n-1), the same holds for B1, and the number of solutions for Blue balls is Combination(n-1, B1 + n-1), so for this fixed A1 and fixed B1 the answer is Combination(n-1, A1 + n-1) * Combination(n-1, B1 + n-1).
But there is another Cute combinatorial solution which needs no for loops over the number of red balls and blue balls. Let's add another box, if some balls are not put in the first n boxes, then we put it in the last box. So the answer for Red balls is the number of solutions to this equation : X1 + X2 + ... + Xn + X(n+1) = A : st Xi >= 0. Answer to this problem is Combination(n, A+n), and finally the over all answer is Combination(n, n+A) * Combination(n, n+B).
There is another solution to this problem using Dynamic Programming.
The state to our solution in DP is dp[boxi][a][b], we are on boxi, we have a red balls and b blue balls, we choose how many balls we want for boxi.
dp[boxi][a][b] = SUM{ dp[boxi+1][a-i][b-j] : such that i=0...a j=0...b }
and we know dp[n+1][xx][yy] = 1, it means we have filled the first n boxes and there are xx red balls and yy blue balls chosen to be out of boxes :)
No comments:
Post a Comment