AliceAndFriends
SRM 623 · 2013-12-22 · by standy
Problem Statement
The second phase of the game follows. At the beginning of this phase, everyone gets a blank blue card. Then, Alice writes down an integer onto her blue card and reveals it to all other players. Finally, her friends write down integers onto their respective blue cards. For each player (including Alice) we have the following constraint: the number on their blue card must be between 0 and the number on the red card they received, inclusive. Thus, for example, if in the first part Alice's friend Bob received a red card with the number 47, in the second phase he can only write an integer between 0 and 47 onto his blue card.
The game then enters its last, third phase. In this phase each player flips a coin. Let R be the number on the player's red card and B be the number on the player's blue card. If the coin flip results in a head, the player's final score is R + B. If the coin comes up tails, the final score is R - B.
After the game, each of Alice's N-1 friends compares their score to Alice's score. The one whose score is higher gets a dollar from the other. (Nothing happens in case of a tie. The players other than Alice don't compare scores with each other.)
Assume that everyone tries to maximize their expected profit at the end of the game. That is, in the second phase of the game, when they have to write a number onto their blue card, the players (including Alice) choose their numbers with this goal in mind.
You are given a
Notes
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- cards will contain between 2 and 1000 elements, inclusive.
- Elements in cards will be between 1 and 1,000,000,000, inclusive.
{10, 1}
Returns: 0.0
Alice's first card will be either 10 or 1 with equal probability. If Alice gets the 10, she can write down 0 on her new card and she is guaranteed to win a dollar from her friend. If Alice gets the 1, her friend will write down 0 and win the dollar. As both cases are equally likely, Alice's expected profit is 0.5*1 + 0.5*(-1) = 0 dollars.
{10, 9}
Returns: -0.25
Alice's first card will be either 10 or 9 with equal probability. If she gets the 10, one optimal strategy for her is to write 0 onto her blue card. That way she can be sure that her final score is 10. Her friend will then write down at least 2, which means that each of them wins with probability 50%. If Alice gets the 9, one optimal strategy for her is to write 9 onto her blue card. After her friend's optimal response and the coin flips, Alice will win a dollar with probability 25% and lose a dollar with probability 75%. Thus, in the first case Alice's expected profit is 0 dollars and in the second case it is -0.5 dollars. Overall, the expected profit is the average of those: -0.25 dollars.
{1, 3}
Returns: 0.0
Alice's first card will be either 1 or 3 with equal probability. If Alice gets the 1, she will surely lose a dollar. If Alice gets the 3, she can write down 0 onto her blue card and surely win a dollar. Thus, her expected profit is 0 dollars.
{1000000000, 1000000000}
Returns: 0.0
{42, 468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996,
943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539,
870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674, 665, 142, 712, 254, 869}
Returns: -9.095
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AliceAndFriends with a public method double getMoney(vector<int> cards) · 42 test cases · 2 s / 256 MB per case