Statistics

Problem Statement for "Hagar"

Problem Statement

Hagar the Horrible is going to raid one of the king's castles.

Castle i contains gold[i] tons of gold.

The king currently has only one battalion of soldiers. He can secretly station it at any one of the castles.

If Hagar attacks an unprotected castle, his band of vikings will loot all the gold from that castle. If Hagar attacks the protected castle, the king's soldiers will chase off the vikings and Hagar will go home empty-handed.


All of the above information is public (i.e., both Hagar and the king know it). The king must choose which castle to protect without knowing where Hagar plans to attack, and Hagar must choose where to attack without knowing which castle the king will protect.

You are given the int[] gold describing the king's castles. Return the expected number of tons of gold looted by Hagar, assuming both parties make their decision optimally.

Definition

Class:
Hagar
Method:
expectedProfit
Parameters:
int[]
Returns:
double
Method signature:
double expectedProfit(int[] gold)
(be sure your method is public)

Notes

  • The return value must have an absolute or a relative error at most 1e-9.
  • Optimal play can formally be defined as follows: the value X you should return is the only real number such that Hagar can make sure that his expected profit is at least X regardless of the king's strategy, and the king can make sure that Hagar's expected profit is at most X regardless of Hagar's strategy.

Constraints

  • gold will contain between 1 and 30 elements, inclusive.
  • Each element of gold will be between 0 and 40, inclusive.

Examples

  1. {37, 37, 37}

    Returns: 24.666666666666664

    With three identical castles the best strategy for both the king and Hagar is to pick the castle uniformly at random. In two out of three cases Hagar will loot the chosen castle, in one of three cases he'll be unlucky and choose the castle the king defended.

  2. {0, 0, 0, 0, 0}

    Returns: 0.0

    The king has no gold, strategies don't matter.

  3. {0, 0, 0, 27, 0}

    Returns: 0.0

    All the king's gold is in one of the castles. The king can just protect the gold and Hagar cannot loot anything.

  4. {1, 37, 37}

    Returns: 18.5

    Both parties ignore the poor castle and flip a fair coin to choose one of the two rich castles.

  5. {1, 3, 4, 8}

    Returns: 2.823529411764706

  6. {1, 0, 3, 0, 4, 0, 8}

    Returns: 2.823529411764706

  7. {3, 4, 8, 3}

    Returns: 2.8800000000000003

  8. {31, 32, 40, 33, 34, 35, 36, 37, 38, 39}

    Returns: 31.834733989687372

  9. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    Returns: 6.263463131731567

  10. {0, 1, 2, 4, 8, 16, 32}

    Returns: 10.666666666666666

  11. {1, 1, 2, 3, 5, 8, 13, 21, 34}

    Returns: 12.990902729181245

  12. {0}

    Returns: 0.0

  13. {27}

    Returns: 0.0

  14. {10, 11}

    Returns: 5.238095238095238

  15. {10, 10}

    Returns: 5.0

  16. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 0.0

  17. {29, 6, 24, 1, 12, 6}

    Returns: 13.132075471698112

  18. {19, 13, 1, 1, 1, 40, 5, 14, 12}

    Returns: 13.417402269861288

  19. {8}

    Returns: 0.0

  20. {21, 1, 3, 4, 15, 2, 32}

    Returns: 13.74233128834356

  21. {17, 6, 1, 6, 6, 28, 24}

    Returns: 14.683804627249355

  22. {3, 17, 24, 5, 3, 1, 5, 1}

    Returns: 9.951219512195122

  23. {1, 17, 1, 2}

    Returns: 1.7894736842105263

  24. {10}

    Returns: 0.0

  25. {15, 1, 2, 31, 14, 23, 6, 26, 19}

    Returns: 17.98243733088273

  26. {1, 36, 22, 3, 1}

    Returns: 13.655172413793103

  27. {5, 8, 3, 2, 2, 3, 3, 24, 7}

    Returns: 6.461538461538462

  28. {31, 11, 7, 18, 5, 2}

    Returns: 11.387755102040817

  29. {4, 3, 2, 5, 1, 1, 3, 7, 6}

    Returns: 3.949843260188088

  30. {6, 6, 13, 8}

    Returns: 5.604790419161676

  31. {1, 2, 1}

    Returns: 0.8

  32. {8}

    Returns: 0.0

  33. {29, 1, 8, 23, 1, 1, 23, 14, 9}

    Returns: 16.469135802469136

  34. {9, 13, 2, 1, 2}

    Returns: 5.318181818181818

  35. {1, 13, 6, 12, 7, 1, 4, 38, 3}

    Returns: 10.719710669077758

  36. {1, 23, 1, 2, 12, 35, 2, 2, 8, 30}

    Returns: 18.978388998035367

  37. {2, 7, 24, 11, 3, 29}

    Returns: 13.132075471698112

  38. {14, 31, 3, 1, 9, 34, 17, 27, 11, 17}

    Returns: 20.26201495194019

  39. {1, 21, 15, 3, 16}

    Returns: 11.313131313131315

  40. {2, 24, 3, 6}

    Returns: 4.800000000000001

  41. {14, 7, 1}

    Returns: 4.666666666666667

  42. {15, 6, 17, 3}

    Returns: 7.96875

  43. {2}

    Returns: 0.0

  44. {13, 2, 1, 1, 11, 13, 6, 7, 9}

    Returns: 8.430131004366812

  45. {1, 28, 6, 4}

    Returns: 4.9411764705882355

  46. {2, 1, 1}

    Returns: 0.8

  47. {4, 25}

    Returns: 3.4482758620689657

  48. {1, 7, 25, 1, 5, 9}

    Returns: 6.803455723542117

  49. {20, 1, 16, 5, 26, 1, 2, 3}

    Returns: 13.2484076433121

  50. {17, 18, 1, 9, 3}

    Returns: 8.869565217391305

  51. {17, 16, 17}

    Returns: 11.10204081632653

  52. {26, 34}

    Returns: 14.73333333333333

  53. {6, 13, 33, 31, 28, 40, 7, 29, 13}

    Returns: 25.355268650144723

  54. {1, 38, 3, 39, 37, 4, 10}

    Returns: 25.321634726391135

  55. {36, 20, 9, 22, 23, 13, 20, 14, 24}

    Returns: 19.351548888794458

  56. {26, 35, 4, 33, 1, 32}

    Returns: 23.330689671916222

  57. {6, 21, 2, 15, 39, 9, 34, 37}

    Returns: 24.36652594983859

  58. {31, 24, 23, 3, 19, 20, 30, 36, 24}

    Returns: 22.70861348998514

  59. {22, 14, 26, 1, 21, 15, 22, 31, 1, 39}

    Returns: 21.359566352138124

  60. {3, 10, 38, 27, 21, 37, 34, 29}

    Returns: 25.927831188181568

  61. {34, 2, 33, 8, 21, 30, 6, 18, 32, 34}

    Returns: 26.023048488801912

  62. {14, 40, 0}

    Returns: 10.370370370370372

  63. {2, 22, 5, 28, 26, 28, 10, 19, 25, 9}

    Returns: 20.476628822747266

  64. {26, 7, 8, 13, 6, 24, 35, 3, 16, 7}

    Returns: 18.39932603201348

  65. {0, 24, 4, 35, 11, 9, 18, 38, 29}

    Returns: 22.89435934640307

  66. {14, 39, 5}

    Returns: 10.301886792452832

  67. {39, 24, 18, 13, 19, 11, 10}

    Returns: 17.094520986863188

  68. {4, 29, 40, 11, 1, 31, 17, 8, 35, 24}

    Returns: 24.935116394254585

  69. {0}

    Returns: 0.0

  70. {21, 16, 0, 25}

    Returns: 13.32275971451229

  71. {23}

    Returns: 0.0

  72. {17, 21, 36, 33, 16, 3, 4, 5, 4, 13}

    Returns: 18.92150170648464

  73. {28, 35, 6, 37, 30, 28, 17, 37}

    Returns: 26.682692307692307

  74. {24, 17, 15, 2, 13, 5, 14, 9}

    Returns: 12.677946423998222

  75. {29, 33, 1, 35, 2, 40, 26, 15, 0}

    Returns: 25.50715299070981

  76. {32, 35, 24, 28, 5, 25, 23, 8, 13, 5}

    Returns: 22.657175358562696

  77. {14, 0, 35, 10, 8}

    Returns: 10.0

  78. {28, 38, 34, 10, 21}

    Returns: 21.871825876662637

  79. {4, 31, 33, 4, 33, 35}

    Returns: 24.70446182152714

  80. {15, 1, 39, 0, 30, 2, 0, 31, 21}

    Returns: 21.92203082502267

  81. {34, 9, 2, 17, 14}

    Returns: 12.526315789473685

  82. {12, 19, 7, 28, 9, 10, 28, 7}

    Returns: 16.12121212121212

  83. {15, 12, 39, 40, 35, 22, 9, 34}

    Returns: 27.618150260352095

  84. {4, 37, 35, 9, 25, 24, 11}

    Returns: 21.855515447002013

  85. {39, 8, 9, 21, 26, 20, 1, 34, 13, 21}

    Returns: 21.387096774193548

  86. {24, 13, 19, 32}

    Returns: 15.930131004366814

  87. {29, 6, 24, 1, 12, 6, 19, 13, 1, 1, 1, 40, 5, 14, 12, 4, 8, 21, 1, 3, 4, 15, 2, 32, 17, 6}

    Returns: 22.658708627238198

  88. {1, 6, 6, 28, 24, 3, 17, 24, 5, 3, 1, 5, 1, 1, 17, 1, 2, 14, 10, 1, 2, 31, 14}

    Returns: 19.82741116751269

  89. {23, 6, 26, 19, 1, 36, 22, 3, 1, 5, 8, 3, 2, 2, 3, 3, 24, 7, 31, 11, 7, 18, 5}

    Returns: 21.824830495222113

  90. {2, 4, 3, 2, 5, 1, 1, 3, 7, 6, 3, 6, 13, 8, 1, 2, 1, 2, 8, 29, 1, 8, 23, 1}

    Returns: 12.91288160833954

  91. {23, 14, 9, 9, 13, 2, 1, 2, 1, 13, 6, 12, 7, 1, 4, 38, 3, 1, 23, 1, 2}

    Returns: 17.656565656565657

  92. {12, 35, 2, 2, 8, 30, 2, 7, 24, 11, 3, 29, 14, 31, 3, 1, 9, 34, 17, 27, 11, 17, 1, 21, 15, 3, 16}

    Returns: 25.62862049702623

  93. {2, 24, 3, 6, 14, 7, 1, 1, 2, 15, 6, 17, 3, 2, 13, 2, 1, 1, 11, 13, 6, 7, 9, 28}

    Returns: 14.787711425612702

  94. {6, 4, 16, 1, 19, 4, 25, 1, 7, 25, 1, 5, 9, 20, 1, 16, 5, 26, 1, 2, 3, 17, 18}

    Returns: 18.091924555942136

  95. {1, 9, 3, 17, 16, 17, 29, 12, 3, 21, 2, 9, 36, 4, 20, 2, 1, 12, 1, 40, 16, 13, 34, 25, 3}

    Returns: 25.713043898198677

  96. {14, 7, 2, 2, 15, 1, 8, 13, 16, 6, 30, 13, 10, 5, 9, 1, 1, 12, 16, 1, 17, 22, 8, 3}

    Returns: 15.231630748345493

  97. {6, 32, 1, 2, 3, 13, 1, 3, 5, 3, 1, 29, 5, 28, 1, 1, 2, 3, 6, 3, 6, 7, 11, 32}

    Returns: 22.60788863109049

  98. {4, 3, 32, 7, 2, 18, 7, 31, 18, 10, 2, 7, 23, 29, 23, 2, 6, 14, 4, 13, 33, 2, 21, 1, 23, 5}

    Returns: 23.38381706966624

  99. {13, 2, 29, 24, 1, 12, 23, 1, 8, 19, 11, 20, 28, 6, 15, 9, 1, 12, 9, 29, 13, 20, 1, 3, 4, 5, 30, 2}

    Returns: 22.40564340043669

  100. {6, 1, 1, 9, 1, 24, 5, 38, 12, 3, 24, 7, 1, 3, 11, 10, 7, 7, 20, 18, 1, 14, 3, 6, 1, 2, 5, 6}

    Returns: 18.791208791208792

  101. {1, 12, 12, 35, 2, 15, 13, 4, 6, 5, 16, 2, 3, 16, 23, 2, 10, 2, 2, 14, 40, 3, 13, 3, 3, 4, 9}

    Returns: 20.608

  102. {35, 14, 9, 20, 3, 34, 17, 13, 36, 37, 40, 9, 6, 35, 37, 24, 37, 10, 5, 35, 11, 36, 31, 18, 35, 36, 15, 23, 38}

    Returns: 33.38641003903014

  103. {20, 9, 7, 13, 26, 27, 5, 37, 12, 9, 20, 1, 4, 14, 22, 0, 5, 17, 38, 12, 2, 1, 28, 26, 14, 27, 6, 19, 24}

    Returns: 24.994349900968015

  104. {1, 21, 39, 6, 37, 21, 11, 18, 10, 1, 35, 5, 28, 14, 18, 38, 13, 36, 26, 9, 19, 26, 20, 22, 24}

    Returns: 29.556712455699163

  105. {14, 4, 39, 23, 7, 1, 5, 8, 7, 28, 30, 32, 12, 21, 19, 19, 4, 15, 10, 1, 5}

    Returns: 23.821123432103256

  106. {39, 17, 10, 20, 1, 17, 15, 37, 18, 18, 25, 14, 40, 29, 14, 24, 5, 8, 30, 13, 34, 31, 37, 31, 4, 28, 2}

    Returns: 30.207985996228608

  107. {21, 34, 29, 17, 33, 35, 28, 4, 21, 38, 29, 12, 22, 6, 14, 4, 15, 23, 24, 12, 9, 5, 32, 38, 27}

    Returns: 29.0414347316495

  108. {6, 25, 10, 4, 38, 10, 16, 19, 0, 9, 10, 2, 25, 8, 0, 26, 27, 0, 3, 0, 20, 33, 2, 23, 37, 36}

    Returns: 26.943164312963244

  109. {17, 30, 7, 29, 23, 31, 1, 13, 19, 3, 0, 25, 37, 21, 17, 31, 40, 38, 24, 14, 36}

    Returns: 29.416082432480568

  110. {16, 22, 33, 16, 17, 6, 1, 22, 39, 38, 4, 10, 34, 39, 33, 36, 9, 9, 25, 31, 33, 18, 28, 19, 34, 2, 13, 19, 14}

    Returns: 31.3592380862575

  111. {40, 33, 40, 35, 5, 30, 23, 34, 34, 15, 38, 5, 33, 33, 0, 39, 24, 18, 21, 29, 3, 27, 40, 15, 39, 28, 34, 12, 33, 35}

    Returns: 33.55975067768211

  112. {12, 8, 3, 19, 16, 27, 8, 35, 5, 29, 21, 26, 0, 32, 36, 34, 4, 4, 23, 24, 9, 5, 21, 10}

    Returns: 26.52087023873608

  113. {31, 37, 34, 13, 23, 23, 10, 39, 39, 33, 33, 29, 22, 39, 15, 12, 13, 34, 6, 16, 17, 29, 19, 35, 17, 6, 34, 15, 39}

    Returns: 32.572874742820126

  114. {20, 7, 4, 9, 37, 31, 34, 17, 29, 13, 11, 13, 24, 28, 30, 19, 18, 22, 7, 32, 39, 35}

    Returns: 28.92856021778499

  115. {26, 36, 21, 8, 13, 17, 15, 39, 36, 37, 16, 12, 14, 16, 12, 0, 20, 3, 5, 18, 5, 15, 20}

    Returns: 27.720384204909287

  116. {13, 0, 3, 31, 40, 33, 24, 39, 3, 27, 26, 25, 24, 3, 7, 21, 13, 26, 23, 8, 0, 25, 39, 25, 23, 3, 34, 38, 40}

    Returns: 32.03200881513831

  117. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}

    Returns: 23.015346417522796

  118. {40, 40, 39, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 33, 33, 32, 32, 31, 31, 30, 30, 29, 29, 28, 28, 27, 27, 25, 21}

    Returns: 34.30359524605858

  119. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    Returns: 23.015346417522796

  120. {1, 13, 7, 24, 10, 18, 30, 2, 0, 11, 35, 4, 20, 25, 22, 5, 18, 2, 22, 28, 13, 15, 35, 29, 40, 32, 4, 0, 22, 35 }

    Returns: 28.601340443226842

  121. {2, 33, 20, 36, 21, 32, 17, 0, 12, 11, 13, 31, 31, 10, 32, 4, 20, 9, 24, 2, 15, 28, 3, 32, 31, 23, 22, 0, 28, 26 }

    Returns: 28.15711652672537

  122. {0, 0, 8, 9 }

    Returns: 4.235294117647059

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: