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
and the conditional probability that the row has N/2 ones is
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 .