TopCoder problem "ModeProbability" used in TCO05 Semi 3 (Division I Level One)



Problem Statement

    You have a skewed random number generator that outputs the number i with percentage probs[i]. Given that you have generated n numbers, return the probability (between 0 and 1) that value has been generated more times than any of the other numbers.
 

Definition

    
Class:ModeProbability
Method:getProb
Parameters:int[], int, int
Returns:double
Method signature:double getProb(int[] probs, int n, int value)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to 1e-9 relative or absolute.
 

Constraints

-probs will contain between 1 and 5 elements inclusive.
-Each element of probs will be between 1 and 100 inclusive.
-The elements of probs will sum to 100.
-n will be between 1 and 15 inclusive.
-value will be between 0 and N-1 inclusive, where N is the number of elements in probs.
 

Examples

0)
    
{50,50}
2
0
Returns: 0.25
Two equally occurring numbers. For 0 to occur more than 1 it needs to be generated twice in a row. Hence, the probability is 1/4.
1)
    
{50,50}
9
0
Returns: 0.5
Since we generate 9 numbers, one number will always occur more times than the other. By symmetry, 0 occurs more frequently with probability 1/2.
2)
    
{5,50,20,25}
15
1
Returns: 0.7947486656372071

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8093&pm=4643

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Yarin , Olexiy

Problem categories:

Advanced Math