Guessing Number Game

Question

I was solving this question. It is as follows

Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts to guess his number. On each guess, Joe will tell Jason if his number is higher or lower than Jason's guess. If Jason guesses Joe's number correctly on any of the $K$ guesses, the game terminates and Jason wins. Jason loses otherwise. If Jason knows all $p_i's$ and plays optimally, what is the probability he wins?
$1\leq N\leq 200000$
$1\leq K\leq 20$

I tried this problem by dynamic programming. Let $DP[i][j][k]$ stores the winning probability such that the number is between $i$ and $j$ inclusive and only $k$ chances are left. So
$$DP[i][j][k] = \max_{i\leq l\leq j} \{p_l + DP[i][l-1][k-1] + DP[l+1][j][k-1]\}\\DP[i][j][1] = \max_{i\leq l\leq j}p_l\ \quad \quad \text{Base Case}$$ But since the range of $N$ is very high this solution is not feasible. So while I was seeking an $\mathcal{O}(n)$ solution I came across the following solution(on the internet which got accepted)

• Sort($p[]$)
• $\sum_{i=0}^{\min(n,2^k-1)}p_i$

If we run both the solution on input $N=5,K=2, p=[0.2, 0.3, 0.4, 0.1, 0.0]$ we get the same answer. So, my question is how is the above algorithm working and can we get to the same conclusion starting form my dp formulation{if it is correct}.

Answer 1

The reason why the sorting solution works is that if you are given $K$ guesses, then with any deterministic strategy you can only guess at most $2^K - 1$ values. This can be proved by induction, first noting the base case $K = 1$ and then for $K + 1$, note that after you guess the first value then you have $K$ guesses left and you guess either on the left or right of your original guess depending on the outcome of the original guess, so by induction that gives $2(2^K - 1)$ values you can guess after the first, so if you add the original guess then you get $2^{K+1} - 1$.

Furthermore, if any of these $2^K - 1$ values is the correct value, it will be guessed and you will win. None of the other $N - 2^K + 1$ values will ever be guessed. So the probability that you win is the sum of the probabilities for the $2^K - 1$ values your deterministic strategy can guess. Obviously the optimal solution is to take the top $2^K - 1$ probabilities.

Answer 2

After a few months, my head has become clearer and it seems quite easy to see how this works.

If you have 1 guess, you pick the one with highest probability.

If you have 2 guesses, you pick the 3 with highest probability. The first guess, you pick the second one among the three. The second pick, you are directed to either of two sides of the first pick. Each side leads to the case of 1 guess, and on each side you already have the top 2 prob located in each. This is optimal. Prob of winning is the sum of the 3 prob.

..

So the clear pattern is that when you have $k$ guesses, you pick the top $2^k - 1$ with highest probabilities. The first pick is on the middle of the top $2^k - 1$. After that you recurse on either side of the middle one. On either side, you have the top $\frac{(2^k - 1) -1}{2} = 2^{k-1} - 1$ probabilities located there because the way you pick the middle pivot and that you take the top $2^k - 1$.

This gives the probability for winning as the sum of the top $2^k - 1$ probabilities.