Problema Intermediário - Problemas da Semana 42 - Solução

Escrito por Caique Paiva

Conhecimentos Prévios Necessários

• Somas de Prefixos

Suponha que a nossa sequência de bombons $[a_1, a_2, \cdots, a_n]$ tem uma divisão boa $(l_1, r_1), (l_2, r_2), \cdots, (l_k, r_k)$, com $k > 2$, então, veja que $(l_1, r_2), (l_3, r_3), \cdots, (l_k, r_k)$ também é uma solução válida, pois, como o MEX de $(l_1, r_1)$ é igual o de $(l_2, r_2)$, então $(l_1, r_2)$, também terá o mesmo MEX, pois esse intervalo vai conter todos os números de $0$ até $MEX-1$ e não vai conter $MEX$. Portanto, provamos que, caso tenhamos uma divisão boa de tamanho $k$, também temos uma divisão boa de tamanho $k-1$. Em particular, fazendo essa operação de juntar várias vezes, conseguimos chegar em somente $2$ intervalos.

Agora, só precisamos ir atrás de $2$ intervalos $(1, i), (i+1, n)$ tal que o MEX deles dois sejam o mesmo. Então, chame de $pref[N]$ um vetor de $N$ elementos, onde $pref[i] = MEX$ de $a_1$ até $a_i$. Vamos ver como calcular ele.

Primeiro, seja $mark[N]$ um vetor que vai guardar quais elementos estão na nossa sequência (Ou seja, $mark[i] = 1$ caso $i$ esteja na sequência, e $0$ caso contrário). Inicialize $pref[0] = 0$ e $mark[i] = 0$ para todo i. Então, façamos um for com $i = 1$ indo até $n$, e no passo $i$, vamos calcular $pref[i]$:

• Primeiro, veja que $pref[i-1] = MEX$ de $a_1$ até $a_{i-1}$, então, para calcularmos $pref[i]$, basta adicionarmos $a_i$ ao $MEX$ de i-1. Então, faça $mark[a[i]] = 1$, e veja os seguintes casos:
  • Se $mark[pref[i-1]] = 0$, significa que $pref[i-1]$ não foi adicionado ao vetor, então o mex de $a_1$ até $a_i$ continua sendo $pref[i-1]$, logo, $pref[i] = pref[i-1]$
  • Caso contrário, então todos os elementos de $0$ até $pref[i-1]$ estão em $a_1$ até $a_i$, faça $pref[i] = pref[i-1]$, e faça o seguinte while:
    • while(v[pref[i]] > 0) pref[i]++;
  • Ou seja, enquanto $pref[i]$ pertencer a $a_1$ até $a_i$, aumente $pref[i]$. Isso vai achar qual é o mex de $a_1$ até $a_i$.

Portanto, conseguimos calcular $pref[i]$ para todo $i$ em $O(N)$! Para finalizar, chame de $suf[N]$  um vetor de $N$ elementos onde $suf[i] = MEX$ de $a_i$ até $a_n$ (Ele vai ser calculado quase da mesma maneira que pref). Então basta procurar algum $i$ tal que $pref[i] = suf[i+1]$. Caso ele exista, imprima os inervalos $[1, i]$ e $[i+1, n]$ como resposta. Caso não exista, imprima -1. Complexidade final: $O(N)$.

Clique aqui para ver o código