TopCoder problem "DrawingMarbles" used in SRM 370 (Division I Level One , Division II Level Two)



Problem Statement

    A big box contains marbles of one or more colors. You're given a int[] 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:int[], int
Returns:double
Method signature:double sameColor(int[] colors, int n)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8016

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10786&pm=8016

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Math