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

Solução escrita por Henrique Vianna

Conhecimento prévio necessário:

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.

Spoiler

Seja soma[l][r] igual a soma dos valores do retângulo com vértices em [1][1] e [l][r]. Podemos calcular esses valores com a seguinte recorrência

soma[l][r] = soma[l - 1][r] + soma[l][r - 1] - soma[l - 1][r - 1] + dp[l][r]

Além disso, a soma dos valores no quadrado com vértices [l, l] e [r, r] é:

soma[r][r] - soma[l - 1][r] - soma[r][l - 1] + soma[l - 1][l - 1]

[collapse]

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