TopCoder Statistics - 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.

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

1

1

10

3

1

Returns: 0.1

The probability that the only chosen number will be equal to 3 is 0.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.
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.
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

61

65

62

3

Returns: 0.15200000000000002
100

1

1000

500

50

Returns: 0.007966361929464066

maxtest
100

1

1000

1

1

Returns: 0.09520785288629094
100

1

1000

1

100

Returns: 1.0E-300
100

1

1000

1

50

Returns: 9.606268454690683E-122
4

632

636

634

2

Returns: 0.296
4

917

921

921

4

Returns: 0.5904
5

2

6

5

2

Returns: 0.08032
5

11

15

11

5

Returns: 3.2E-4
5

101

105

105

3

Returns: 0.05792
6

201

206

201

1

Returns: 0.6651020233196159
6

311

316

316

2

Returns: 6.64437585733882E-4
6

421

426

423

3

Returns: 0.3366340877914952
6

565

570

565

6

Returns: 2.143347050754458E-5
100

1000

1000

1000

33

Returns: 1.0

interval of length 1
31

844

993

976

21

Returns: 2.4410934856848945E-4
81

909

991

927

20

Returns: 0.09672626995235419
72

531

676

531

25

Returns: 8.709986491599602E-36
54

266

488

271

24

Returns: 1.3069237986161574E-23
36

366

770

493

33

Returns: 1.6253731535135496E-14
59

75

357

317

24

Returns: 1.511649899844821E-16
37

193

943

581

4

Returns: 1.7728842618735425E-9
86

959

990

977

35

Returns: 0.0011748460186088903
78

283

744

451

17

Returns: 2.1662707078633084E-4
99

741

919

791

74

Returns: 1.5375367935014205E-21
88

584

813

617

43

Returns: 3.0344407378151394E-14
87

551

786

567

20

Returns: 1.7918985679634836E-6
4

349

453

378

4

Returns: 8.450717550814731E-4
75

887

908

902

32

Returns: 1.502306081345972E-6
41

693

962

921

41

Returns: 1.9180424257705174E-4
6

228

394

370

2

Returns: 7.105944523053263E-5
62

986

996

988

12

Returns: 0.4866431259989519
62

104

263

149

25

Returns: 0.007578540781342927
41

657

750

709

15

Returns: 0.0017124365994765445
70

366

672

493

49

Returns: 3.7797298119725116E-7
30

792

832

815

22

Returns: 0.02919337815682956
73

526

735

607

49

Returns: 3.923749903953902E-7
37

955

960

960

34

Returns: 0.8857226499270989
31

67

698

211

7

Returns: 0.008191174665270574
52

646

877

697

18

Returns: 0.005025930602215322
67

122

921

315

17

Returns: 0.00954225407661824
76

847

933

909

44

Returns: 0.0022517279454050292
100

982

989

987

34

Returns: 2.187305092245873E-9
72

567

940

823

50

Returns: 0.01956325792000116
46

688

775

707

23

Returns: 2.7726866887126968E-5
90

299

824

514

48

Returns: 0.0011523390727700194
25

544

550

549

14

Returns: 0.030767487020746716
65

343

794

423

17

Returns: 0.0058694515512543455
51

838

856

843

21

Returns: 0.07977095631044251
33

997

1000

997

29

Returns: 4.698232905150923E-14
7

35

378

257

1

Returns: 3.9507848754109936E-5
30

697

996

960

15

Returns: 2.4018317132750463E-8
28

595

755

652

5

Returns: 0.0019185400887988824
47

705

850

794

31

Returns: 0.03397507035264611
68

1

330

270

58

Returns: 0.021251127498134875
88

437

940

442

12

Returns: 6.272380220445104E-10
51

135

870

746

37

Returns: 0.0012930353641581137
35

651

798

737

5

Returns: 4.665386520579159E-9
6

128

489

251

1

Returns: 0.002057539145107407
45

190

729

249

17

Returns: 6.24794453994245E-7
5

193

970

957

1

Returns: 5.842478259373176E-10
93

187

913

852

80

Returns: 0.003011569563270904
39

358

549

367

18

Returns: 1.4295217949795347E-13
9

225

255

255

6

Returns: 1.1975060202296201E-4
52

784

812

787

24

Returns: 1.819542712928326E-8
79

474

964

782

71

Returns: 1.025244975745344E-8
2

410

663

638

1

Returns: 7.905015810031619E-4
90

799

995

935

35

Returns: 4.951435266538617E-10
67

505

783

768

9

Returns: 2.2653426719583266E-64
72

883

947

904

48

Returns: 1.1099047512266815E-8
45

956

960

959

26

Returns: 0.32119940984109846
95

143

928

484

36

Returns: 0.004850828801181114
100

1

1000

55

55

Returns: 1.639444713828366E-42
100

1

1000

501

49

Returns: 0.0076234120574343875
100

1

1000

239

50

Returns: 1.9212615090849463E-9
100

5

900

400

50

Returns: 0.005039716184207096
100

500

1000

750

50

Returns: 0.01588504163497092
100

2

1000

499

55

Returns: 0.005144497290222894
97

1

998

497

47

Returns: 0.007407330768740586
100

1

1

1

50

Returns: 1.0
100

1

1000

400

50

Returns: 0.001267117562018484
100

1

1000

553

47

Returns: 0.0017291818423937587

Statistics

Problem Statement for "KthProbableElement"

Problem Statement

Definition

Notes

Constraints

Examples