Statistics

Problem Statement for "CyclicGame"

Problem Statement

You are playing a one-player game where several cells are arranged around a circle, and each cell contains a value. You have a bank that is initially empty, and you start on the 0-th cell. On each turn, you throw a typical six-sided die (each side has a distinct number between 1 and 6), and you move clockwise the number of cells indicated on the die. The value in the cell that you land on will be added to the bank. The goal is maximize the value of the bank.

Unfortunately, the sum of all the values on the cells is negative, so the expected value of the bank after a long game is also negative. Therefore, you should stop the game at the proper time.

You will be given a int[] cells that contains the values of the cells in clockwise order. The 0-th element of cells is the value of the 0-th cell. Return the expected value of the bank if you play optimally. See examples for further clarification.

Definition

Class:
CyclicGame
Method:
estimateBank
Parameters:
int[]
Returns:
double
Method signature:
double estimateBank(int[] cells)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • cells will contain between 2 and 15 elements, inclusive.
  • Each element of cells will be between -100 and 100, inclusive.
  • The sum of all elements in cells will be negative.

Examples

  1. {-10, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 1.3611111111111112

    You are guaranteed get 1 point on the first turn. When you're on cell 1 or 2 (0-indexed), you can safely take another turn to get one more point, but if you're on cells 3 through 8, your best option is to stop the game. The expected result for the bank value is 1 + 1/6*(1 + 1/6*1) + 1/6 = 1.36.

  2. {-10, 7, -5, 7}

    Returns: 0.30434782608695654

    You should stop the game if you're on cell 2 or 3.

  3. {-1, -2, 2}

    Returns: 0.0

    The expected result of any move is 1/3*(-1)+1/3*(-2)+1/3*2 = -1/3, so the best choice is not play at all.

  4. {-40, 9, 9, 9, 9, 9, -44, 9, 9, 9, 9, 9, -40, 15, 15}

    Returns: 3.5653612433724144

    You should stop the game if you're on cells 9 through 11 (where two cells with value -40 are reachable in one turn).

  5. {-36, 95, -77, -95, 49, -52, 42, -34, -1, 98, -20, 96, -96, 23, -52}

    Returns: 12.395613307567126

  6. {-5, 4}

    Returns: 0.0

  7. {-5, -7}

    Returns: 0.0

  8. {-100, -100, -100, -100, -100, -100, -100, -100, -100, -100, -100, -100, -100, -100, -100}

    Returns: 0.0

  9. {-100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 3.0433247837600974

  10. {-15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 3.2521655637481754

  11. {-81,88,-31,60,52,-73,-92,44,-38,-36}

    Returns: 0.6666666666666666

  12. {49,-95,53,-8,-92,-83,-69,-26,-50,100,-75,35,-30,-18}

    Returns: 0.0

  13. {46,-99,-89,-47}

    Returns: 0.0

  14. {-5,-23,-53,27,18,-41,-22,-13,-64}

    Returns: 0.0

  15. {8,-97,-82,59,27,-52,52,0,93,-78,76,-9}

    Returns: 22.150259067358657

  16. {-64,-19,-49,48,29}

    Returns: 0.0

  17. {-61,28,-98,17}

    Returns: 0.0

  18. {88,53,-10,60,22,-47,-67,-73,-18,-57,96,-83}

    Returns: 5.34959658570511

  19. {-46,78,-95,-79,88,-58,17,-25}

    Returns: 0.0

  20. {-35,74,-26,34,11,-100,-59,73,-99,-89,83,67,-61,-47}

    Returns: 0.0

  21. {-34,-71,-46,93,23,-61,-13,29,88,36,-60,-24}

    Returns: 3.906523898308044

  22. {-11,82,-33,66,-50,-60}

    Returns: 0.0

  23. {-91,-57,46,62,40,8,-36,-16}

    Returns: 14.374032674118657

  24. {-43,-71,18,74,-34,80,-48,17,-3}

    Returns: 11.959996328735514

  25. {57,-30,26,-99,-96,35,52,-9,-14,-98,-15,100,-29,9,-57}

    Returns: 0.0

  26. {-43,-24,9,19,20,-77,-63,94,-79,32,55,-93}

    Returns: 0.0

  27. {-51,34,-21,94,-12,-64,-16,-73,-52,36,57}

    Returns: 2.713709134938786

  28. {-52,-66,18,-22,-39,17,-12,89,-16,-84,-66,5,25,3}

    Returns: 0.0

  29. {89,-74,-76,92,-53,-71,38,91,-90,-15,-43,-50,-11,40,51}

    Returns: 0.0

  30. {-34,-20,-53,93}

    Returns: 0.0

  31. {-54,52,98,-12,55,24,-81,32,13,-51,-85}

    Returns: 36.361704523733465

  32. {-54,58,43,29,88,15,-8,0,-82,-38,36,70,23,-91,-95}

    Returns: 46.81365755576341

  33. {-57,-65,-67,65,-1,76,15,-79,-62,95,59,-5,11}

    Returns: 20.680224112642982

  34. {-73,35,50,-48,-28,-24,-64,92,76,21,-28,-20,8,-3}

    Returns: 13.659950225581929

  35. {-70,-15,53,61,87,-15,59,-94,29,-99}

    Returns: 54.330525479458274

  36. {-89,-23,46,75,26,4,-42,-84,37,39}

    Returns: 22.887126244785918

  37. {-62,49,26,71,-35,-90,2,78,32,-99,-4,-20,55,15,-22}

    Returns: 19.57580546200294

  38. {-95,62,59,20,-62,-3,-9,-80,-24,-62,94,98}

    Returns: 27.363523316062864

  39. {-99,63,-11,45,-90,78,0,6,67,-52,-38,-10,93,-62}

    Returns: 35.25588796524326

  40. {-60,-37,44,-9,16,31,58,67,-49,-44,10,7,-47}

    Returns: 40.56200611441158

  41. {-59,-6,-82,82,27,-18,14,-45,54,-26,-9,74,-33,8}

    Returns: 12.200059040792155

  42. {-84,21,65,-96,-1,10,60,-87,-56,9,39,52,57}

    Returns: 21.862317573790843

  43. {-63,42,80,24,-53,-30,-48,46,1,-14}

    Returns: 9.168882715830348

  44. {-52,33,-79,68,22,28,-88,89,-55,-62,64,26}

    Returns: 3.9854725892269904

  45. {-96,70,-37,-84,-38,79,-17,-81,86,59,65,51,-62}

    Returns: 35.83831850544249

  46. {-58,66,-15,1,-65,-92,22,-31,37,-68,88,37,77}

    Returns: 18.39295674382962

  47. {-84,81,38,-33,-74,-61,-29,81,-1,82,-18,2,2}

    Returns: 3.8332816868747157

  48. {-99,-36,-92,-73,90,-16,-63,60,45,-15,81,63,51}

    Returns: 16.550360592941978

  49. {-99,42,-28,-79,-88,86,-52,-17,32,84,41,64}

    Returns: 9.183214265624672

  50. {-64,71,19,80,27,-41,24,-50,-78,-94,58,75,-14,-4,-10}

    Returns: 50.06273534946682

  51. {-79,-77,-55,-74,-81,-27,31,99,61,31,73,97}

    Returns: 24.164974093263456

  52. {-41,83,-28,-74,61,-44,27,-94,-88,10,92,-78,70,100}

    Returns: 19.247375915077313

  53. {-90,32,76,19,-6,27,-97,-71,58,76,-24,-66,89,-26}

    Returns: 16.727757888712816

  54. {-62,-71,42,-6,96,-9,-83,95,49,-82,-36,-54,34,60,24}

    Returns: 12.758983691035573

  55. {-94,-79,62,26,-54,1,69,-60,-37,46,41,-79,66,88,2}

    Returns: 26.37292811043223

  56. {-23,-29,36,72,-24,-52,3,73,-63,-6,10}

    Returns: 8.647064138262543

  57. {-60,-92,55,-11,80,-21,1,60,-62,42,21,-16}

    Returns: 29.061139896374023

  58. {-36,-24,-35,11,55,-91,-93,1,93,60,61,66,-72}

    Returns: 0.6801642419722491

  59. {-40,38,82,-73,14,-80,31,-89,24,91}

    Returns: 18.88184267546326

  60. {-38,-64,-84,49,33,-11,-9,89,78,93,-43,-48,-47}

    Returns: 50.33916341504108

  61. {-81,52,31,-58,-64,-69,88,-13,49,-69,43,45,59,-16}

    Returns: 28.25454289799432

  62. {-52,4,-75,-13,-82,4,77,20,-61,-3,66,80,10,-40,62}

    Returns: 23.45623028234846

  63. {-58,-58,-65,19,95,-17,24,60,-31,27}

    Returns: 19.840207413017442

  64. {-38,-54,56,21,-49,70,17,93,-87,22,-55}

    Returns: 27.544348069083537

  65. {-22,83,-85,-17,49,-47,1,-1,-25,37,34,-28,18}

    Returns: 9.001951920663585

  66. {-83,-18,58,-97,10,74,63,68,-98,-25,-19,-32,-27,84,38}

    Returns: 33.760521565138646

  67. {-35,35,83,-87,51,53,7,22,38,-1,-94,-77}

    Returns: 41.2625302356978

  68. {-22,-53,-71,75,-46,-16,-80,90,-100,97,73,49}

    Returns: 0.0

  69. {-64,99,-100,-82,-21,-9,24,86,-34,99}

    Returns: 14.227351800098468

  70. {-54,45,27,-56,-16,-27,45,-84,88,47,-16,53,-55}

    Returns: 21.111042247290023

  71. {-37,98,70,43,-30,1,18,19,32,-98,-38,-5,-41,-100,-79}

    Returns: 39.38425925925926

  72. {-55,-80,-50,-12,-55,-94,-28,79,-96,-39,-77,-66,-41,5,15}

    Returns: 0.0

  73. {79,-54,84,29,83,23,-76,-79,-80,-68,-27,-41,-91,6,94}

    Returns: 16.620864235469163

  74. {-58,-75,-19,-43,32,-46,-38,-79,81,-59,33,100,25,-75,-45}

    Returns: 0.0

  75. {52,77,-92,-34,-55,41,-66,80,-6,-4,-51,-64,-92,-95,16}

    Returns: 0.0

  76. {-86,72,1,-67,-95,-50,-66,-73,-62,92,-53,16,-7,-59,26}

    Returns: 0.0

  77. {-97,-94,21,-95,-96,-87,17,28,-5,5,29,-93,58,7,18}

    Returns: 0.0

  78. {83,-16,-69,84,45,-56,67,-10,-94,9,-67,38,-30,-69,-95}

    Returns: 12.027777777777779

  79. {-20,75,-20,-19,-4,-90,78,-2,-22,93,-63,-37,37,31,-80}

    Returns: 8.589110400683916

  80. {-75,-35,-76,22,-53,-29,-91,1,20,-43,-94,74,68,-2,13}

    Returns: 0.0

  81. {-33,-37,-53,-79,94,-71,-10,-78,-95,78,-26,83,46,-16,-54}

    Returns: 0.0

  82. {42,11,-13,-32,-11,-69,20,-41,-46,-9,-25,-44,-95,-11,-32}

    Returns: 0.0

  83. {-11,28,-90,-5,-17,43,55,88,-42,-71,57,-79,-25,-39,57}

    Returns: 16.907994737395843

  84. {73,28,43,-82,-22,-77,-31,-89,-14,59,-26,13,-87,-33,21}

    Returns: 0.0

  85. {-23,-9,45,-72,79,45,42,-1,93,-8,-69,-38,-98,-95,85}

    Returns: 49.49347256839649

  86. {-42,-98,-88,10,-84,-11,-93,-52,68,58,-52,-24,77,-20,78}

    Returns: 0.0

  87. {-67,61,-63,-65,96,92,-18,-63,3,60,57,-18,-99,-29,1}

    Returns: 31.852820778417883

  88. {-1,43,38,-57,6,-76,89,-1,-50,64,-68,-88,-95,-22,78}

    Returns: 8.175925925925926

  89. {90,-93,72,-69,-91,-97,-58,-52,43,9,29,97,99,-92,95}

    Returns: 0.0

  90. {-83,-10,-94,8,-60,-1,30,-22,29,11,-57,4,-74,66,-70}

    Returns: 0.0

  91. {-1,26,-44,-30,-18,40,-52,-66,-51,-99,-48,-89,41,82,-13}

    Returns: 0.0

  92. {79,-64,39,-100,71,91,-7,-44,-47,-41,47,-43,-34,19,-73}

    Returns: 7.404300353630519

  93. {-83,9,87,-39,-95,52,-83,-97,9,70,-67,51,97,-97,91}

    Returns: 0.0

  94. {-42,-76,-96,93,53,-74,-82,51,-40,11,80,13,-70,-83,33}

    Returns: 0.0

  95. {-1,-21,3,28,77,-44,-90,-35,37,-22,65,-72,-89,12,-6}

    Returns: 0.0

  96. {19,-8,-88,12,-82,-88,-60,44,-32,31,-45,-78,6,-19,92}

    Returns: 0.0

  97. {11,-31,1,-30,34,-38,-26,-24,16,20,85,-75,5,6,25}

    Returns: 0.0

  98. {69,-34,96,14,33,-79,11,82,-99,-52,-100,10,-92,-85,61}

    Returns: 11.194444444444445

  99. {-52,14,5,-47,-76,-34,14,-82,44,0,-71,6,-14,-96,5}

    Returns: 0.0

  100. {-72,-53,43,38,-95,-57,8,-97,-30,-85,-75,-80,50,-6,74}

    Returns: 0.0

  101. {0, -1, -1, -1, -1, -1, -1, -1, 20, 20, 20, 10, -99, -99, -99 }

    Returns: 6.694230109739369

  102. {-36, 95, -77, -95, 49, -52, 42, -34, -1, 98, -20, 96, -96, 23, -52 }

    Returns: 12.395613307567126

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: