PROBLEM STATEMENT
A big box contains marbles of one or more colors. You're given a vector colors, each element
of which denotes the number of marbles there are of a particular color. You draw n marbles
randomly from the box, leaving each marble outside the box after taking it. Return the probability
that all marbles drawn will be the same color.
DEFINITION
Class:DrawingMarbles
Method:sameColor
Parameters:vector , int
Returns:double
Method signature:double sameColor(vector colors, int n)
NOTES
-Every time we draw a marble, all marbles in the box are equally likely to be chosen.
-A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
CONSTRAINTS
-colors will contain between 1 and 50 elements, inclusive.
-Each element of colors will be between 1 and 50, inclusive.
-n will be between 1 and the sum of all elements of colors, inclusive.
EXAMPLES
0)
{ 13 }
8
Returns: 1.0
All the marbles are the same color, so obviously all drawn marbles will be the same color too.
1)
{ 5, 7 }
1
Returns: 1.0
2)
{ 5, 6, 7 }
2
Returns: 0.3006535947712418
The probability that the first drawn marble will be of the color 0 is 5 / 18 (there are 5 marbles
of color 0 out of 18). If the first drawn marble is of the color 0, then the probability that the
second drawn marble will be of the color 0 is 4 / 17 (there are 4 marbles of color 0 left out of
17). So the probability that both drawn marbles will be of the color 0 is (5 / 18) * (4 / 17) =
0.0653594771... . Similarly, the probability that both drawn marbles will be of the color 1 is (6
/ 18) * (5 / 17) = 0.0980392156..., and that both drawn marbles will be of the color 2 is (7 / 18)
* (6 / 17) = 0.1372549019... . The answer is the sum of these 3 probabilities.
3)
{ 12, 2, 34, 13, 17 }
4
Returns: 0.035028830818304504
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.