TopCoder problem "KthProbableElement" used in TCO09 Round 1 (Division I Level Two)



Problem Statement

    M integers are randomly independently chosen from the interval lowerBound...upperBound, inclusive. Return the probability that the K-th smallest element of the generated set is equal to N. K=1 refers to the smallest element, K=2 refers to the second smallest element, and so on.
 

Definition

    
Class:KthProbableElement
Method:probability
Parameters:int, int, int, int, int
Returns:double
Method signature:double probability(int M, int lowerBound, int upperBound, int N, int K)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-M will be between 1 and 100, inclusive.
-lowerBound will be between 1 and 1000, inclusive.
-upperBound will be between lowerBound and 1000, inclusive.
-N will be between lowerBound and upperBound, inclusive.
-K will be between 1 and M, inclusive.
 

Examples

0)
    
1
1
10
3
1
Returns: 0.1
The probability that the only chosen number will be equal to 3 is 0.1.
1)
    
3
1
2
2
2
Returns: 0.5
There are 8 ways to choose 3 numbers from the interval 1..2: 
Numbers | 2nd smallest element
 1 1 1  |  1
 1 1 2  |  1
 1 2 1  |  1
 1 2 2  |  2
 2 1 1  |  1
 2 1 2  |  2
 2 2 1  |  2
 2 2 2  |  2
Exactly 4 of the ways have the 2nd smallest element equal to 2.
2)
    
3
1
3
2
2
Returns: 0.48148148148148145
There are 27 ways to choose 3 numbers from the interval 1..3, 13 of them have the 2nd smallest element equal to 2.
3)
    
10
1
10
1
10
Returns: 1.0000000000000003E-10
Only one of 1010 ways to choose 10 numbers from the interval 1..10 has 1 as the 10th smallest element.
4)
    
4
61
65
62
3
Returns: 0.15200000000000002

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13759&pm=10335

Writer:

Nickolas

Testers:

PabloGilberto , Jan_Kuipers , ivan_metelsky

Problem categories:

Dynamic Programming, Math