Escrito por Lúcio Figueiredo
Conhecimento prévio necessário:
Note que se o valor de $$k$$ fosse “pequeno” (por exemplo, menor ou igual a $$300$$) poderíamos precalcular a resposta de todas as queries usando programação dinâmica, da seguinte forma:
Defina $$dp[i][j] (i, j \leq n)$$ como a resposta de um query se $$p = i$$ e $$k = j$$. Assim, podemos calcular $$dp$$ dividindo o problema em dois casos:
- Caso 1: $$i + A[i] + j > n$$. Neste caso, $$dp[i][j] = 1$$, já que na próxima operação o valor $$p$$ se tornaria maior que $$n$$.
- Caso 2: $$i + A[i] + j \leq n$$. Neste caso, $$dp[i][j] = 1 + dp[i + A[i] + j][j]$$, já que realizamos uma operação com $$p = i$$ e na próxima operação $$p = i + A[i] + j \leq n$$.
Assim, conseguimos calcular $$dp$$ com complexidade $$O(n^2)$$, já que a DP possui $$n^2$$ estados e conseguimos realizar a transição em $$O(1)$$. No entanto, como o valor de $$k$$ pode ser “grande” (até $$10^5$$), isso não é suficiente para resolver o problema.
Perceba, porém, que se o valor $$k$$ de uma query for “grande” (maior que $$300$$), o número máximo de operações realizadas em tal query é menor ou igual a $$n/300 \leq 334$$, já que em cada operação o valor de $$p$$ é somado em, pelo menos, $$k$$.
Usando este fato, conseguimos chegar em uma solução. Defina $$B$$ como um valor próximo de $$\sqrt{n}$$. Para este problema, faça $$B = 320$$. Calcule $$dp[i][j]$$ utilizando o método citado acima para todo par $$(i, j)$$ onde $$i \leq n$$ e $$j \leq min(n, B)$$. Assim, conseguimos responder as queries quando o valor $$k$$ é menor ou igual a $$B$$. Para queries em que $$k > B$$, podemos simplesmente “simular” todas as operações (ou seja, fazer $$p = p + A[p] + j$$) até que o valor $$p$$ da query se torne maior que $$n$$, já que no máximo $$n/B \leq 313$$ operações serão realizadas.
Assim, se $$B$$ for um valor próximo de $$\sqrt{n}$$ (por exemplo, $$320$$), conseguimos resolver o problema com complexidade $$O((n+q) \cdot \sqrt{n})$$. Confira o código abaixo para melhor compreensão: