Connection Status:
Competition Arena > KthProbableElement

KthProbableElement

TCO09 Round 1 · 2009-02-24 · by Nickolas

TCO09 Round 1 · 2009-02-24 · by Nickolas · Dynamic Programming, Math
Class Name: KthProbableElement
Return Type: double
Method Name: probability
Arg Types: (int, int, int, int, int)
Problem Statement

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.

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
5)
100
1
1000
500
50
Returns: 0.007966361929464066

maxtest

18)
100
1000
1000
1000
33
Returns: 1.0

interval of length 1

Submissions are judged against all 86 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KthProbableElement with a public method double probability(int M, int lowerBound, int upperBound, int N, int K) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous