[Solved]: Guessing Number Game

Problem Detail: 

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

Asked By : justice league

Answered By : user2566092

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29018