GUESSROW - Editorial

PROBLEM LINK:

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

DIFFICULTY:

MEDIUM

DRAFT EXPLANATION:

Note: The editorial is underway. To not keep you waiting however, the draft editorial of the author is attached below.

We ask for a (random, still unknown) cell in the row which has the highest probability of being the one with N/2 ones. Computing the probability of being the row with N/2 ones exactly is unfeasible, so we shall make an approximation. To simplify the computation, instead of the assumption “for each 1\le k \le N there is a row with k ones”, we assume that the row are independent and the number of ones in each row is initially sampled uniformly from 1, 2, \dots, N. Under this assumption, if we have asked a questions on a row and b of those a cells are ones, then the conditional probability that such row has N/2 ones can be computed explicitly).