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