Jogo de números de adivinhação

Eu estava resolvendo essa pergunta. É como segue

Joe escolhe um número inteiro a partir da lista de com uma probabilidade de colheita para todos . Ele então tenta Jason adivinhar seu número. Em cada palpite, Joe dirá a Jason se seu número é maior ou menor que o palpite de Jason. Se Jason adivinha o número de Joe corretamente em qualquer um dos , o jogo termina e Jason vence. Jason perde o contrário. Se Jason conhece todos os e joga da melhor maneira, qual é a probabilidade de ganhar? $1,2,\cdots,N$$p_i$$i$$1\leq i \leq N$$K$$K$$p_i's$
$1\leq N\leq 200000$
$1\leq K\leq 20$

Eu tentei esse problema por programação dinâmica. Permita que armazene a probabilidade de ganho, de modo que o número esteja entre e inclusivo e restem apenas chances. Então Mas desde o intervalo de N é muito alto, essa solução não é viável. Então, enquanto eu procurava uma solução \ mathcal {O} (n) , me deparei com a seguinte solução (na internet, que foi aceita)$DP[i][j][k]$$i$$j$$k$

$$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}$$ $N$$\mathcal{O}(n)$

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

Se executarmos a solução na entrada , obteremos a mesma resposta. Portanto, minha pergunta é como o algoritmo acima está funcionando e podemos chegar à mesma conclusão começando com a minha formulação dp {se estiver correta}.$N=5,K=2, p=[0.2, 0.3, 0.4, 0.1, 0.0]$

A razão pela qual a solução de classificação funciona é que, se você receber palpites, com qualquer estratégia determinística, você poderá adivinhar no máximo valores. Isso pode ser provado por indução, observando primeiro o caso base e, em seguida, para , observe que depois de adivinhar o primeiro valor, você terá palpites restantes e adivinhar à esquerda ou à direita do seu palpite original, dependendo no resultado da suposição original, por indução que fornece valores, você pode adivinhar após o primeiro; portanto, se você adicionar a suposição original, obterá .$K$$2^K - 1$$K = 1$$K + 1$$K$$2(2^K - 1)$$2^{K+1} - 1$

Além disso, se algum desses valores for o valor correto, ele será adivinhado e você vencerá. Nenhum dos outros valores será adivinhado. Portanto, a probabilidade de ganhar é a soma das probabilidades dos valores que sua estratégia determinística pode adivinhar. Obviamente, a solução ideal é obter as probabilidades .$2^K - 1$$N - 2^K + 1$$2^K - 1$$2^K - 1$

Depois de alguns meses, minha cabeça ficou mais clara e parece fácil ver como isso funciona.

Se você tem um palpite, escolhe aquele com maior probabilidade.

Se você tem 2 palpites, escolhe os 3 com maior probabilidade. O primeiro palpite, você escolhe o segundo entre os três. A segunda escolha, você é direcionado para um dos dois lados da primeira escolha. Cada lado leva ao caso de um palpite e, em cada lado, você já tem os 2 principais prob localizados em cada um. Isso é ótimo. Prob de ganhar é a soma dos 3 prob.

..

Portanto, o padrão claro é que, quando você tem suposições, você escolhe os superiores com as maiores probabilidades. A primeira escolha está no meio dos . Depois disso, você recuará dos dois lados do meio. Em ambos os lados, você tem as probabilidades localizadas lá porque a maneira como você escolhe o pivô do meio e faz as top .$k$$2^k - 1$$2^k - 1$$\frac{(2^k - 1) -1}{2} = 2^{k-1} - 1$$2^k - 1$

Isso fornece a probabilidade de vitória como a soma das probabilidades .$2^k - 1$