Escrito por Estela Baron
Conhecimento prévio necessário:
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.