TopCoder Statistics - Problem Statement

Problem Statement

Recently, Philip bought a new audio player. After toying with it a bit, he noticed that the player was pretty strange. It is only capable of playing N different songs that were pre-loaded by the manufacturer. These songs are arranged in a playlist which contains N positions, numbered 0 to N-1. Each song is in a distinct position of the playlist.

The player has a "Shuffle" button which changes the order of songs in the playlist as follows:

The user is asked to enter an integer K, which must be between K1 and K2, inclusive.
The player generates a random permutation P = (p[0], p[1], ..., p[N-1]) of integers between 0 and N-1, inclusive. All possible permutations have the same probability of being generated.
The generated permutation P is applied to the playlist exactly K times. Each application works as follows: for each i, 0 <= i < N, the song at position i of the playlist is moved to position p[i] (these movements occur simultaneously for all N songs).

Philip considers a shuffle to be successful if the song at position X of the playlist before the shuffle appears at position Y after the shuffle. He discovered that the probability of a shuffle being successful may depend on the number K that he enters in the first step of the shuffle process. Return the value of K he must enter to achieve the maximum probability of a successful shuffle. If there are several such values, return the smallest one among them.

Definition

Class:: PlaylistShuffler
Method:: bestShuffle
Parameters:: int, int, int, long, long
Returns:: long
Method signature:: long bestShuffle(int N, int X, int Y, long K1, long K2)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
X will be between 0 and N-1, inclusive.
Y will be between 0 and N-1, inclusive.
K1 will be between 1 and 10,000,000,000 (10^10), inclusive.
K2 will be between K1 and 10,000,000,000 (10^10), inclusive.

Examples

2

0

1

2

4

Returns: 3

Suppose that the songs are called A and B and the initial order is A, B. If the generated permutation is {0, 1}, then the list is just left intact no matter what the value of K is. If the permutation is {1, 0}, the list keeps changing between A, B and B, A consecutively. We want to maximize the probability that the final list is B, A. For K = 2 and K = 4 this probability is 0, and for K = 3 the probability is 0.5.
2

1

1

1

10

Returns: 2

This time we want the final list to be A, B. This happens with probability 1 for every even value of K. The smallest one among them is 2.
1

0

0

1111111111

9999999999

Returns: 1111111111

Since there is just 1 song, all values of K lead to the same final result.
10

3

7

1000

10000

Returns: 1003
1

0

0

1

10000000000

Returns: 1
1

0

0

10000000000

10000000000

Returns: 10000000000
18

6

17

39

5235725

Returns: 41
9

6

5

34

817645

Returns: 37
7

1

5

893

8321950

Returns: 893
2

0

1

15263

71440

Returns: 15263
22

10

8

63

6233884404

Returns: 67
28

13

0

28

76654343

Returns: 29
17

13

12

503701

46722407

Returns: 503707
2

1

0

91

49460702

Returns: 91
41

33

0

54322014

668334434

Returns: 54322019
29

25

1

56725

82791652

Returns: 56731
9

5

0

139

797016

Returns: 139
23

14

1

279

87246239

Returns: 281
37

25

19

8

9

Returns: 9
2

0

1

210209

5915446

Returns: 210209
23

8

21

30

340

Returns: 31
6

0

1

7

417

Returns: 7
2

1

0

29

92993

Returns: 29
24

6

8

643

26356487

Returns: 643
29

6

26

18

34888413

Returns: 31
50

49

48

1000000000

1000000000

Returns: 1000000000
50

4

18

2

5369876541

Returns: 53
50

4

18

1

5369876541

Returns: 1
50

39

31

7889011464

10000000000

Returns: 7889011511
50

15

42

13370118

26811184

Returns: 13370171
12

11

6

5377963

95383908

Returns: 5377963
37

9

27

10000000000

10000000000

Returns: 10000000000
37

29

26

85

88

Returns: 86
49

2

36

610

612

Returns: 611
49

11

47

832

834

Returns: 833
49

27

40

644

646

Returns: 645
27

14

21

3

39747092

Returns: 29
6

0

1

1

874694

Returns: 1
14

9

10

5

15

Returns: 5
50

35

30

4302407360

10000000000

Returns: 4302407363
50

23

45

1527863882

10000000000

Returns: 1527863947
46

2

2

68569178

89187293

Returns: 73513440
40

16

16

300

440

Returns: 360
28

22

22

771

97773

Returns: 55440
6

4

4

4283

68729465

Returns: 4320
5

4

4

4298

8143339615

Returns: 4320
43

14

14

676398

4949981

Returns: 4324320
37

7

7

462152570

10000000000

Returns: 6983776800
44

24

24

47562

10000000000

Returns: 6983776800
44

8

8

3

10000000000

Returns: 6983776800
48

41

41

40647

80455

Returns: 55440
5

4

4

9950167994

10000000000

Returns: 9950168040
45

35

35

449132226

2555240408

Returns: 1396755360
47

31

31

734

9710370

Returns: 4324320
41

9

9

98

68793

Returns: 55440
48

37

37

557

595216

Returns: 332640
35

26

26

7

850102

Returns: 332640
50

47

47

49958

699764407

Returns: 367567200
22

18

18

93

10000000000

Returns: 232792560
46

2

2

368

6836011910

Returns: 1396755360
29

24

24

6008

5805887295

Returns: 3491888400
35

0

0

41915

55812136

Returns: 21621600
13

7

7

14725897

9616695693

Returns: 14774760
12

10

10

699

7866933

Returns: 27720
22

2

2

5

30

Returns: 24
11

4

4

58

10000000000

Returns: 27720
20

10

10

8914

680296

Returns: 55440
45

11

11

41

10000000000

Returns: 6983776800
25

6

6

7

754045971

Returns: 61261200
47

37

37

34782

209952922

Returns: 73513440
19

15

15

9322

775328356

Returns: 232792560
24

1

1

9310

7481759

Returns: 720720
5

3

3

82992688

983231669

Returns: 82992720
6

1

1

794019

7344994172

Returns: 794040
41

32

32

4698534

79507879

Returns: 73513440
36

19

19

1956877

1592115514

Returns: 367567200
27

2

2

596

549835390

Returns: 183783600
43

14

14

9

35071

Returns: 27720
2

1

1

30039575

9703494154

Returns: 30039576
10

2

2

695

10892849

Returns: 2520
14

1

1

947396

6132245474

Returns: 1081080
33

1

1

9

4392826809

Returns: 367567200
49

14

14

3

10000000000

Returns: 6983776800
29

25

25

479

2575142411

Returns: 183783600
2

0

0

163

2793971717

Returns: 164
34

31

31

902972

10000000000

Returns: 6983776800
31

25

25

149

724

Returns: 720
31

19

19

11063132

193222871

Returns: 183783600
27

17

17

400772

432997226

Returns: 183783600
8

4

4

55

884

Returns: 840
13

9

9

8112

767657975

Returns: 360360
46

1

1

1

7358016237

Returns: 6983776800
44

1

1

1972644213

1972644237

Returns: 1972644220
46

40

40

2569199158

2569199222

Returns: 2569199220
50

3

3

542864495

542864502

Returns: 542864496
45

27

27

7318436143

7318436144

Returns: 7318436144
45

27

27

7318436143

7318436144

Returns: 7318436144
47

28

28

7291069885

7291069908

Returns: 7291069896
50

46

46

1264145756

1264145775

Returns: 1264145760
43

3

3

6014867032

6014867708

Returns: 6014867040
42

4

4

7889487045

7889487051

Returns: 7889487048
42

12

12

5282366433

5282366602

Returns: 5282366544
49

28

28

8588049988

8588050292

Returns: 8588050020
45

23

23

1172732511

1172732511

Returns: 1172732511
42

16

16

1052678445

1052678448

Returns: 1052678448
41

15

15

1646069428

1646069429

Returns: 1646069428
41

14

14

4672479157

4732481820

Returns: 4724319600
47

8

8

136379070

136397973

Returns: 136382400
42

20

20

4420250386

4420250391

Returns: 4420250388
41

18

18

4081120905

4081129659

Returns: 4081123200
43

40

40

2228791843

2228792529

Returns: 2228792160
49

44

44

4375340885

4375340956

Returns: 4375340928
46

23

23

4741730386

4741730466

Returns: 4741730400
42

4

4

9018225032

9018250315

Returns: 9018248400
42

32

32

8599492451

8599591064

Returns: 8599500000
43

3

3

3262035588

3262035590

Returns: 3262035588
45

35

35

3589893241

3589893302

Returns: 3589893300
46

40

40

8628189495

8628189566

Returns: 8628189504
41

30

30

1

10000000000

Returns: 6983776800
41

21

21

1501056639

2551400575

Returns: 2327925600
41

18

18

1453565894

1545478343

Returns: 1470268800
41

29

29

3130008624

3135734904

Returns: 3135132000
42

11

11

1

10000000000

Returns: 6983776800
42

2

2

2198512267

5841640892

Returns: 2327925600
42

26

26

6731897933

6749886275

Returns: 6737290560
42

33

33

1956127630

1962628350

Returns: 1960358400
43

16

16

1

10000000000

Returns: 6983776800
43

32

32

2179523891

3458767326

Returns: 2327925600
43

16

16

2898355527

3049652559

Returns: 2940537600
43

7

7

1073469492

1077022395

Returns: 1074427200
44

21

21

1

10000000000

Returns: 6983776800
44

17

17

8896052354

9740183157

Returns: 9311702400
44

28

28

6266288269

6875995061

Returns: 6285399120
44

6

6

3612079442

3615236076

Returns: 3615131520
45

5

5

1

10000000000

Returns: 6983776800
45

8

8

2303527547

2920674386

Returns: 2327925600
45

41

41

8516668044

9083506123

Returns: 8527559040
45

7

7

6906873560

6968321196

Returns: 6910263360
46

12

12

5657974302

8041058885

Returns: 6983776800
46

32

32

5334545839

5540838041

Returns: 5354228880
46

38

38

48754356

502075974

Returns: 367567200
46

33

33

4917834975

4926880148

Returns: 4925400480
47

14

14

1

10000000000

Returns: 6983776800
47

27

27

1763271920

6138145547

Returns: 1889727840
47

31

31

7026276908

7073513981

Returns: 7045038000
47

4

4

1910909100

1956939989

Returns: 1911349440
48

13

13

1

10000000000

Returns: 6983776800
48

8

8

7396185748

8197913439

Returns: 7558911360
48

12

12

7591806202

7799904013

Returns: 7596388800
48

15

15

8034043684

8041115184

Returns: 8037469440
49

12

12

1

10000000000

Returns: 6983776800
49

20

20

5736174635

6579704240

Returns: 5751345600
49

28

28

5263738427

5269672390

Returns: 5268463200
49

9

9

3617962711

3627991395

Returns: 3626663040
50

43

43

277748490

7789901316

Returns: 6983776800
50

25

25

7640740809

7907302679

Returns: 7718911200
50

36

36

1470032381

1501428199

Returns: 1470268800
50

12

12

7256005997

7257922060

Returns: 7257650400
50

20

20

1

10000000000

Returns: 6983776800
50

31

31

6983776801

10000000000

Returns: 8454045600
50

12

12

8454045601

10000000000

Returns: 9448639200
50

0

0

9448639201

10000000000

Returns: 9777287520
50

35

35

9777287521

10000000000

Returns: 9863053200
50

47

47

9863053201

10000000000

Returns: 9924314400
50

36

36

9924314401

10000000000

Returns: 9945936000
50

13

13

9945936001

10000000000

Returns: 9948818880
50

24

24

9948818881

10000000000

Returns: 9979089120
50

26

26

9979089121

10000000000

Returns: 9989179200
50

0

0

9989179201

10000000000

Returns: 9996386400
50

21

21

9996386401

10000000000

Returns: 9997827840
50

16

16

9997827841

10000000000

Returns: 9999990000
50

5

5

9999990001

10000000000

Returns: 9999998400
50

36

36

9999998401

10000000000

Returns: 9999999240
50

34

34

9999999241

10000000000

Returns: 9999999360
50

20

20

9999999361

10000000000

Returns: 9999999900
50

37

37

9999999901

10000000000

Returns: 9999999936
50

15

15

9999999937

10000000000

Returns: 9999999984
50

13

13

9999999985

10000000000

Returns: 9999999990
50

21

21

9999999991

10000000000

Returns: 10000000000
50

3

3

9999999967

9999999967

Returns: 9999999967
45

7

7

723582125

6014720017

Returns: 1396755360
44

2

2

7251824738

8335336103

Returns: 7351344000
40

38

38

156506880

237249412

Returns: 164324160
45

1

1

9193019764

9282704708

Returns: 9199990800
45

5

5

9202853150

9301098168

Returns: 9238188960
50

32

32

549972636

650794049

Returns: 551350800
44

19

19

8392662279

8407537959

Returns: 8392784400
40

26

26

1698435720

1702195975

Returns: 1699457760
44

18

18

3279043

9874663

Returns: 4324320
45

36

36

8823085212

8832087852

Returns: 8825216400
43

14

14

9045065376

9063635835

Returns: 9048639600
44

2

2

5834352807

5867840244

Returns: 5837832000
40

7

7

629710676

675998829

Returns: 629909280
43

15

15

8861462356

8951430152

Returns: 8864856000
44

23

23

259728679

272493430

Returns: 266666400
46

39

39

1157117110

1159484200

Returns: 1159250400
47

22

22

3755503

3759194

Returns: 3756480
48

10

10

8664989553

8664989561

Returns: 8664989560
47

7

7

2329810294

2339043898

Returns: 2337294960
48

36

36

9449051767

9456087344

Returns: 9450801360
50

0

0

138378241

1241092747

Returns: 367567200
6

0

1

3

6

Returns: 3
50

0

1

1111111111

1111111120

Returns: 1111111115
5

1

1

1

100

Returns: 60
8

3

2

4

10

Returns: 5
50

1

1

1

10000000000

Returns: 6983776800
50

1

1

5435434334

10000000000

Returns: 6983776800
16

1

1

13

16

Returns: 16
5

2

2

7

20

Returns: 12
50

0

0

3123341138

7427793198

Returns: 6983776800
10

2

2

7

20

Returns: 12

Statistics

Problem Statement for "PlaylistShuffler"

Problem Statement

Definition

Constraints

Examples