Solução Informática – Nível Avançado – Semana 38

Solução escrita por Henrique Vianna

Conhecimento prévio necessário:

• Range-DP
• Somas Parciais

Uma ideia inicial é pré-calcular os intervalos que formam palíndromos para que, de alguma forma, seja possível responder queries de forma rápida (perceba que Q pode chegar a $10^6$). Para isso, podemos usar uma DP de intervalo. Define-se então:

$dp[l][r] =\begin{cases} 1, & \text{se $[l, r]$ for palindromo}.\\ 0, & \text{caso contrario}. \end{cases}$

É fácil ver que o caso base ocorre quando $l == r$, uma vez que toda palavra de uma unica letra forma um palíndromo. Logo:

$dp[l][r]$ = $1$, se $(l == r)$

A recorrência também é simples:

$dp[l][r]$ = ($dp[l + 1][r - 1]$  &&  $s[l] == s[r]$)

Uma vez que se $[l, r]$ é palíndromo, então seus extremos devem ter o mesmo carácter e a palavra formada pelo restante deve ser também um palíndromo. Sendo assim, sabemos para todos os intervalos se ele é palíndromo ou não, calculando isso com uma complexidade de $\mathcal{O}(n^2)$. Alem disso, podemos já responder cada pergunta em $\mathcal{O}(n^2)$, computando, para cada uma, o valor:

$\sum_{i=l}^{r}\sum_{j=l}^{r}dp[i][j]$

Isso, porém, faz com que a complexidade de nosso algoritmo seja $\mathcal{O}(n^2 * q)$, o que é lento demais para os limites do problema. 

Entretanto, percebe-se que essa expressão corresponde ao somatório dos valores de um quadrado da matriz da nossa DP.  Podemos, então, calcular somas parciais 2D da DP e utilizá-las para rapidamente calcular a soma e responder a cada pergunta em $\mathcal{O}(1)$. Assim, o problema está resolvido em  $\mathcal{O}(n^2 + q)$, o que passa no limite de tempo.

Em caso de dúvidas, veja o código comentado a seguir:   https://codeforces.com/contest/245/submission/212298002