Solução Informática - Nivel Avançado - Semana 13

Escrito por Lúcio Figueiredo

Conhecimento prévio necessário:

• Programação Dinâmica

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: