Hagar
SRM 817 · 2021-10-21 · by misof
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
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.
{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.
{0, 0, 0, 0, 0}
Returns: 0.0
The king has no gold, strategies don't matter.
{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.
{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.
{1, 3, 4, 8}
Returns: 2.823529411764706
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Hagar with a public method double expectedProfit(vector<int> gold) · 122 test cases · 2 s / 256 MB per case