Solução Informática - Nível Intermediário - Semana 4

Solução por Thiago Mota

Conhecimento prévio necessário:

• Mapa
• Vetores

Nós temos um vetor $a_i$ e temos que fazer todos os números deles virarem $0$ com o menor número de operações. A soma do vetor $a_i$ é $0$.

Nós podemos dividir o vetor em partes consecutivas de elementos com soma zero. Se a parte tem tamanho $l$ nós podemos usar todos os pares de vizinhos e transformar tudo em zero com $l - 1$ operações.

Então, a soma do número de operações em cada uma dessas partes gera uma resposta $ans = n - k$ onde $k$ é o número de partes. Então para minimizar a resposta temos que maximizar o número de partes.

Vamos calcular a soma de prefixos. Como as partes que nós procuramos tem soma zero, o prefixo no início e no final de cada uma será igual, logo podemos calcular a maior frequência entre todos os prefixos, a maior frequência será o número de partes que iremos dividir, logo a resposta é $n - f$ sendo $f$ a maior frequência. Segue o código: