Guess the number is a very simple game. Given is a positive integer n. The first player picks a number x from the set {0,1,…,n - 1}, writes it on a card and places the card into an envelope. The second player then makes guesses. Each guess has the form of an integer g. The first player answers “too low” if g < x, “too high” if g > x, or “correct” if g = x. For each guess the first player gets a candy from the second player. The game ends when the second player gets the answer “correct”.
Hannah discovered this game when she was eight and she started playing it with her younger brother Gunnar. Hannah always picked the number and Gunnar was always guessing.
When they were young, Hannah had it easy. Gunnar only knew a few deterministic guessing strategies, such as “binary search”. In each game he would use one of the strategies he knew, picked uniformly at random. Hannah knew all Gunnar’s strategies, and she always picked a number that maximized the expected number of candies she would get.
As Gunnar grew up, the games became much more involved. Eventually, both he and Hannah became perfect in playing the game.
Problem specification
In the easy input each test case contains n and a list of Gunnar’s strategies. Find the expected number of candies Hannah will get per game if she plays optimally. Also, find one optimal strategy for Hannah.
In the hard input each test case contains n. Find the expected number of candies Hannah will get per game if both players play optimally (i.e., try to maximize/minimize the expected number of candies paid per game). Also, find one optimal strategy for Hannah and one optimal strategy for Gunnar.
Strategy format specification
We will only consider strategies where Gunnar never makes a guess that reveals no new information. (All strategies in the input for the easy data set will be such, and all strategies you will provide in the output for the hard data set must be such.)
Each such strategy can be encoded into a sequence of integers: First, you write down the first query he will make. Then you recursively write the strategy used if the guess was too large, and finally the strategy if the guess was too small. (I.e., the encoding is the pre-order traversal of the decision tree.)
For example, for n = 6 the strategy (2,0,1,4,3,5) means that in the first round Gunnar will guess 2. If the correct number is smaller, he will then guess 0 (and afterwards 1 if necessary), otherwise he will guess 4 (and then possibly 3 or 5).
Input specification – easy subproblem
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of several lines. The first line contains the integer n (up to 16) and an integer s (up to 100) giving the number of strategies Gunnar knows. Each of the next s lines describes one strategy in the format specified above.
Output specification – easy subproblem
For each test case, output two lines. The first line must contain a fraction p∕q giving the exact expected number of candies per game Hannah will gain by playing optimally. This fraction must be reduced (i.e., p and q must be coprime).
The second line must contain one optimal strategy for Hannah – a sequence of integers h0,…,hn-1 giving the relative probabilities of Hannah’s choices. That is, Hannah should choose the number i with probability hi∕(∑ hi). The numbers hi must not exceed 109.
Example – easy subproblem
Gunnar picks one of three strategies: the first is a linear search, the second is a binary search, and the third is ad-hoc. One optimal strategy for Hannah is to pick the number 4 in 1/3 of all games and the number 6 in the remaining 2/3 of all games. This strategy guarantees her to get 13/3 of a candy per game, and there is no better strategy.
Input specification – hard subproblem
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of a single line with the integer n.
Output specification – hard subproblem
For each test case, output several lines. The first line must contain a fraction p∕q giving the exact expected number of candies per game Hannah will gain if both players play optimally. This fraction must be reduced (i.e., p and q must be coprime).
The second line must contain one optimal strategy for Hannah – a sequence of integers h0,…,hn-1 giving the relative probabilities of Hannah’s choices. That is, Hannah should choose the number i with probability hi∕(∑ hi). The numbers hi must not exceed 109.
The third line must contain a positive integer s not exceeding 1000 – the number of deterministic strategies Gunnar will be using with a non-zero probability.
Each of the remaining s lines should contain n + 2 space-separated tokens: the encoding of a strategy, a colon, and a positive integer gi. The numbers gi are relative probabilities of Gunnar’s choices; they must not exceed 109.
Example – hard subproblem
The optimal strategies are “pick 0 or 1 with equal probability” and “start by guessing 0 or 1 with equal probability”. In 50 in the other 50
Clearly, Hannah’s strategy guarantees she can expect to gain at least 3/2 candies per game, and Gunnar’s strategy guarantees she can expect at most 3/2. Hence both strategies are optimal.