GUESSROW - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

PREREQUISITES:

Probability, Binomial coefficients

EXPLANATION:

This problem is about having the right intuition for a good strategy in the game.

The strategy we will employ is the following one.

Strategy: Always ask the value of a random cell in the row that, given the current information, is the most likely to be the one with exactly N/2 ones.

It remains to decide how shall we select the row that has the largest probability of having exactly N/2 ones. Computing such probability exactly is unfeasible (since the condition that the rows have distinct number of ones makes the rows not independent). We compute a different probability, which shall be very close to the desired one:

  • For each row, we assume that its number of ones was, at the beginning of the interaction, randomly sampled from \{1, 2, \dots, N\} and we compute the conditional probability (given the current information) that such row has N/2 ones.

Let us see how to compute such conditional probability.
For a certain row, the information we have is that we asked a cells and exactly b of them are ones. If the row had k ones, the probability of this event is

P_k(a, b) := \frac{\binom{k}{b}\binom{N-k}{a-b}}{\binom{N}{a}}.

and the conditional probability that the row has N/2 ones is

P(a, b) := \frac{P_{N/2}(a, b)}{\sum_{k=1}^N P_k(a, b)}.

With this formula for the probability in our hand (one should precompute the values of P(a, b) for all 0\le b\le a \le N), we are able to efficiently select the “best” row (i.e., the one which maximizes this probability) and ask the value of a random cell on such row.

This strategy performs, on average, \approx 585 queries.

Open question: Is it true that the strategy “ask a cell in the row that has the largest probability of having N/2 ones” is the optimal strategy against a random input.

SOLUTION

The author’s solution can be found here .