# 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 .