Statistics

Problem Statement for "Collect"

Problem Statement

A die has 6 sides, numbered 1-6, and each side is equally likely to come up after a roll. In this problem, you are to consider rolling N dice in K rounds. In each round, you select a subset of the dice rolled in the previous round (you have to roll them all in the first round) and reroll that subset (note that a subset can be all the dice from the previous round). After K rounds, you pick a number between 1 and 6 inclusive and multiply it by the number of dice showing that number. Your goal is to maximize this value.

Assuming optimal play, what is the maximum expected score for a given N and K?

Definition

Class:
Collect
Method:
expected
Parameters:
int, int
Returns:
double
Method signature:
double expected(int N, int K)
(be sure your method is public)

Notes

  • If you elect not to reroll a die in one round, you may not reroll it in any subsequent round.

Constraints

  • N will be between 1 and 10, inclusive.
  • K will be between 1 and 100, inclusive.

Examples

  1. 1

    1

    Returns: 3.5

    Rolling 1 die once gives an expected value of 3.5.

  2. 1

    2

    Returns: 4.249999999999999

    If you can roll twice, you should keep a 4, 5, or 6 on the first round, and reroll a 1, 2, or 3. Thus, half the time you'll reroll and expect 3.5, while the other half the time you'll expect to get a 5 (the average of 4, 5 and 6). Thus, the overall expected value is (3.5+5)/2 = 4.25

  3. 2

    2

    Returns: 6.262345679012343

    On the first roll, lock both if you have two threes or better. Otherwise keep the higher of the two dice if it is over 3. Otherwise, reroll both.

  4. 1

    1

    Returns: 3.5

  5. 1

    2

    Returns: 4.249999999999999

  6. 1

    3

    Returns: 4.666666666666666

  7. 1

    4

    Returns: 4.944444444444444

  8. 1

    5

    Returns: 5.12962962962963

  9. 1

    6

    Returns: 5.2746913580246915

  10. 1

    7

    Returns: 5.395576131687243

  11. 1

    8

    Returns: 5.496313443072702

  12. 1

    9

    Returns: 5.580261202560585

  13. 1

    10

    Returns: 5.6502176688004875

  14. 2

    1

    Returns: 5.055555555555555

  15. 2

    2

    Returns: 6.262345679012343

  16. 2

    3

    Returns: 7.100051440329217

  17. 2

    4

    Returns: 7.765453532235938

  18. 2

    5

    Returns: 8.32417350156226

  19. 2

    6

    Returns: 8.82409749212518

  20. 2

    7

    Returns: 9.269012811393925

  21. 2

    8

    Returns: 9.658650239984302

  22. 2

    9

    Returns: 9.995931205498351

  23. 2

    10

    Returns: 10.285387415663653

  24. 3

    1

    Returns: 6.305555555555557

  25. 3

    2

    Returns: 8.179140946502056

  26. 3

    3

    Returns: 9.617161898910222

  27. 3

    4

    Returns: 10.76037900924973

  28. 3

    5

    Returns: 11.76010260471904

  29. 3

    6

    Returns: 12.651637093534129

  30. 3

    7

    Returns: 13.432240108671825

  31. 3

    8

    Returns: 14.104049699784603

  32. 3

    9

    Returns: 14.690360371841328

  33. 3

    10

    Returns: 15.202539717550376

  34. 4

    1

    Returns: 7.527777777777772

  35. 4

    2

    Returns: 10.130036865569272

  36. 4

    3

    Returns: 12.146952769098558

  37. 4

    4

    Returns: 13.796605642797712

  38. 4

    5

    Returns: 15.238061079961824

  39. 4

    6

    Returns: 16.518082427824375

  40. 4

    7

    Returns: 17.624976735942408

  41. 4

    8

    Returns: 18.598673176735577

  42. 4

    9

    Returns: 19.445776809976252

  43. 4

    10

    Returns: 20.17470271523939

  44. 5

    1

    Returns: 8.753858024691368

  45. 5

    2

    Returns: 12.069049810591629

  46. 5

    3

    Returns: 14.658863374242731

  47. 5

    4

    Returns: 16.796697501416258

  48. 5

    5

    Returns: 18.7123884162782

  49. 5

    6

    Returns: 20.385843893707193

  50. 5

    7

    Returns: 21.85277944061418

  51. 5

    8

    Returns: 23.133896871369494

  52. 5

    9

    Returns: 24.236377303704206

  53. 5

    10

    Returns: 25.17721144822596

  54. 6

    1

    Returns: 9.976466049382726

  55. 6

    2

    Returns: 13.977001332116638

  56. 6

    3

    Returns: 17.140890496142333

  57. 6

    4

    Returns: 19.808930872675422

  58. 6

    5

    Returns: 22.19734389213186

  59. 6

    6

    Returns: 24.273311622171306

  60. 6

    7

    Returns: 26.111899492813592

  61. 6

    8

    Returns: 27.693256289816784

  62. 6

    9

    Returns: 29.04790099534485

  63. 6

    10

    Returns: 30.19516357572349

  64. 7

    1

    Returns: 11.180905635573874

  65. 7

    2

    Returns: 15.86124300724142

  66. 7

    3

    Returns: 19.61347534338498

  67. 7

    4

    Returns: 22.843812522511303

  68. 7

    5

    Returns: 25.68943640121636

  69. 7

    6

    Returns: 28.20284981681153

  70. 7

    7

    Returns: 30.38606264899786

  71. 7

    8

    Returns: 32.27169701047571

  72. 7

    9

    Returns: 33.8730860708382

  73. 7

    10

    Returns: 35.2208845430909

  74. 8

    1

    Returns: 12.360391899100694

  75. 8

    2

    Returns: 17.727708416959647

  76. 8

    3

    Returns: 22.079067183852846

  77. 8

    4

    Returns: 25.876811069203157

  78. 8

    5

    Returns: 29.186658374022915

  79. 8

    6

    Returns: 32.138530530918736

  80. 8

    7

    Returns: 34.68218518430872

  81. 8

    8

    Returns: 36.860305910320356

  82. 8

    9

    Returns: 38.70370256036377

  83. 8

    10

    Returns: 40.24945757617778

  84. 9

    1

    Returns: 13.513727244798856

  85. 9

    2

    Returns: 19.578731166983065

  86. 9

    3

    Returns: 24.54400046630214

  87. 9

    4

    Returns: 28.907689893075926

  88. 9

    5

    Returns: 32.725896538218905

  89. 9

    6

    Returns: 36.08184079534306

  90. 9

    7

    Returns: 38.98527576516397

  91. 9

    8

    Returns: 41.45613652030628

  92. 9

    9

    Returns: 43.53778701811308

  93. 9

    10

    Returns: 45.2794545382755

  94. 10

    1

    Returns: 14.645377772856191

  95. 10

    2

    Returns: 21.421395316158353

  96. 10

    3

    Returns: 27.022207211024874

  97. 10

    4

    Returns: 31.943623609678664

  98. 10

    5

    Returns: 36.26972024765426

  99. 10

    6

    Returns: 40.04080822440012

  100. 10

    7

    Returns: 43.29227117637948

  101. 10

    8

    Returns: 46.05420296352534

  102. 10

    9

    Returns: 48.37321148985555

  103. 10

    10

    Returns: 50.30997381251698

  104. 9

    32

    Returns: 53.842022991258915

  105. 9

    37

    Returns: 53.936512583292405

  106. 9

    87

    Returns: 53.99999302369629

  107. 9

    24

    Returns: 53.320727778559935

  108. 9

    63

    Returns: 53.99944540588239

  109. 9

    28

    Returns: 53.6724188746753

  110. 9

    83

    Returns: 53.999985533937746

  111. 9

    26

    Returns: 53.52828317953664

  112. 9

    54

    Returns: 53.99713841616867

  113. 9

    24

    Returns: 53.320727778559935

  114. 10

    32

    Returns: 59.82446999028846

  115. 10

    37

    Returns: 59.92945842588096

  116. 10

    87

    Returns: 59.99999224855147

  117. 10

    24

    Returns: 59.24525308725432

  118. 10

    63

    Returns: 59.999383784313544

  119. 10

    28

    Returns: 59.63602097186159

  120. 10

    83

    Returns: 59.999983926597416

  121. 10

    26

    Returns: 59.47587019948096

  122. 10

    54

    Returns: 59.9968204624101

  123. 10

    24

    Returns: 59.24525308725432

  124. 2

    37

    Returns: 11.9859035265378

  125. 7

    24

    Returns: 41.47167716663245

  126. 5

    28

    Returns: 29.818010560019825

  127. 7

    26

    Returns: 41.633109140717416

  128. 4

    24

    Returns: 23.698112422787872

  129. 3

    55

    Returns: 17.999205117706875

  130. 8

    34

    Returns: 47.90248332793756

  131. 8

    30

    Returns: 47.797789428813196

  132. 6

    62

    Returns: 35.9995563247059

  133. 3

    20

    Returns: 17.53156407069376

  134. 5

    62

    Returns: 29.999630270588238

  135. 7

    14

    Returns: 38.7288173495781

  136. 1

    68

    Returns: 5.999991061068747

  137. 1

    75

    Returns: 5.999997505308339

  138. 1

    54

    Returns: 5.999885231411142

  139. 3

    71

    Returns: 17.999957006383948

  140. 8

    79

    Returns: 47.99997333615378

  141. 6

    92

    Returns: 35.999998130920034

  142. 8

    44

    Returns: 47.98425051303703

  143. 8

    81

    Returns: 47.999981483439804

  144. 10

    100

    Returns: 59.99999927551891

  145. 10

    99

    Returns: 59.999999130623515

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: