Solução Informática – Nível Intermediário – Semana 30

Escrito por Estela Baron

Conhecimento prévio necessário:

• Congruências
• Princípio da casa dos pombos
• Somas de prefixo

Nesse problema, queremos descobrir se existe alguma maneira de escolhermos vizinhos tal que a soma de seus brigadeiros tenha resto $0$ na divisão por $c$. Para isso, vamos construir um vetor $pref$ que guarde o resto da soma de $a_1, ... a_i$ por $c$ em $pref[i]$ (semelhante a uma soma de prefixos normal, mas com restos).

• se $pref[i] \equiv 0 \;(mod \; c)$, então achamos uma solução – escolher os vizinhos de $1$ até $i$.
• se $pref[i] \equiv pref[j]\;(mod \;c)$ , com $i\neq j$, então $pref[i] - pref[j]\equiv 0 \;(mod \; c)$. Ou seja, se $i < j$, então $\sum a_1, ... a_j - \sum a_1, ... a_i \equiv 0\;(mod \: c)$ e, portanto, temos a solução de escolher os vizinhos de $i+1$ até $j$.

Logo, como visto anteriormente, quando há um resto igual a $0$ ou dois restos iguais, temos uma solução.

Uma observação extremamente importante de se fazer é que $c \leq n$, pois isso nos garante que sempre haverá uma quantidade maior ou igual a $c$ de restos em $pref$.

Portanto, como há pelo menos $c$ restos, pelo Princípio da Casa dos Pombos, ou haverá um resto zero, ou haverá pelo menos um resto repetido (sem o zero, sobram $c-1$ restos diferentes para pelo menos $c$ posições). Como consequência, sempre haverá uma solução.

A complexidade da solução é $O(n)$ para cada caso teste.

Recomendamos que você tente implementar o problema antes de ver o código.Veja a implementação nesse link.