GreaterGame
SRM 637 · 2014-08-25 · by snuke
Problem Statement
Cat Snuke and wolf Sothe are playing the Greater Game. The game is played with cards. Each card has a number written on it. There are 2N cards. The numbers on the cards are the integers between 1 and 2N, inclusive.
At the beginning of the game, each player gets N of the cards and chooses the order in which he wants to play them. The game then consists of N turns. In each turn, both players play one of their cards simultaneously. The player who revealed the card with the larger number gets a point.
You are given a
Obviously, Snuke can determine the numbers on Sothe's cards, but he does not necessarily know the order in which Sothe is going to play his cards.
You are given the information Snuke has about Sothe in a
Snuke wants to play according to a strategy that maximizes the expected number of points he'll get. Find that strategy and return the corresponding expected number of Snuke's points at the end of the game.
As shown in Example 0, the optimal strategy for Snuke may involve some random decisions. However, note that before the game starts Snuke must choose the order in which he is going to play all his cards. He is not allowed to change their order after he sees some of the cards played by Sothe.
Constraints
- N will be between 1 and 50, inclusive.
- hand and sothe will contain exactly N elements each.
- Each element of hand will be an integer between 1 and 2N, inclusive.
- Each element of sothe will be either -1, or an integer between 1 and 2N, inclusive.
- The positive integers in hand and sothe will be distinct.
{4,2}
{-1,-1}
Returns: 1.5
Sothe will play the cards 1 and 3 in some unknown order. The best strategy for Snuke is to flip a coin and to play his cards either in the order {2,4} or in the order {4,2} with equal probability. This leads to two equally likely results of the game: Snuke plays his 2 against Sothe's 1, and his 4 against Sothe's 3. In this case, Snuke wins both turns and thus scores 2 points. Snuke plays his 2 against Sothe's 3, and his 4 against Sothe's 1. In this case, Snuke scores 1 point. Therefore, the expected number of Snuke's points is 1.5.
{4,2}
{1,3}
Returns: 2.0
If Snuke plays card 2 first and card 4 next, he is guaranteed to score 2 points.
{2}
{-1}
Returns: 1.0
Sothe's only card has to be 1, and thus Snuke is guaranteed to win the only turn of this game.
{1,3,5,7}
{8,-1,4,-1}
Returns: 2.5
{1}
{2}
Returns: 0.0
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GreaterGame with a public method double calc(vector<int> hand, vector<int> sothe) · 82 test cases · 2 s / 256 MB per case