Solução Informática - Intermediário - Semana 38

Solução escrita por Caique Paiva

Conhecimentos Prévios Necessários:

• Programação Dinâmica

Primeiro, veja que maximizar a quantidade de bolas retiradas é a mesma coisa que minimizar a quantidade de bolas que sobram. Então, seja $[a, c], [b, d]$ dois intervalos em que fizemos as operações, então, $a < b < c < d$ é falso, pois, suponha sem perda de generalidade que fazemos a operação em $[a, c]$ primeiro, então, não podemos fazer a operação $[b, d]$, pois $a_b$ já não está no vetor mais. Além disso, se $[b, d]$ estiver contido em $[a, c]$, então, só precisamos fazer a operação $[a, c]$. Portanto, podemos supor que qualquer sequência de operações tem intervalos disjuntos.

Defina $dp_i$ para ser a quantidade mínima de bolas que conseguimos deixar quando olhamos somente para o subarray $a_1, a_2, \cdots a_i$, em particular, $dp_0 = 0$. Vamos calcular $dp_{i+1}$ em função das dp's menores.

Primeiro, olhando para o subarray $a_1, a_2, \cdots , a_{i+1}$, se não removemos a bola $i+1$, então a menor quantidade de bolas que conseguimos ter é $dp_i +1$, pois não removemos a bola $i+1$, então nós só olhamos para o array $a_1, \cdots a_i$ para fazer as operações, que nós sabemos que conseguimos deixar no mínimo $dp_i$ bolas nele.

Agora, se nós removermos a bola $i+1$ com a bola $j$, então removemos todas as bolas no intervalo $[j, i+1]$, ou seja, sobrou o array $a_1, a_2, \cdots a_{j-1}$, que conseguimos deixar no mínimo $dp_{j-1}$ bolas.

Então, veja que esses dois casos abrange todos os casos possíveis, logo

$dp_{i+1} = min(dp_{i}+1, min \{ dp_j | a_{j+1} = a_{i+1}, j+1 < i \} )$

Perfeito, sabemos calcular a $dp_n$ e nossa resposta vai ser $n - dp_n$. Só temos um problema, para calcular essa dp, quando estamos no estado $i$, nós percorremos por $dp_1, dp_2, \cdots , dp_{i-1}$ no pior dos casos, ou seja, a transição da i-ésima posição da dp é $O(i)$. Como temos $n$ valores para calcular, a complexidade total é $O(1+2+\cdots + n) = O(n^2)$, que não passa com as constantes do problema :(.

Como podemos corrigir isso? Veja que $1 \le a_i \le n$, então, vamos criar outro vetor chamado $m[n+1]$, inicializado com $m_i = inf$ para todo $i$, e vamos calcular a dp de forma iterativa. Então, quando estamos calculando $dp_{i+1}$, o vetor $m$ guarda, para todo $a_x$, com $x \le i$, qual é o $j$ onde $dp_j$ é minimizado e $a_{j+1} = a_x$, então

$dp_{i+1} = min(dp_i +1, m[a_{i+1}])$

E, para atualizar $m$ depois de cada operação, basta fazer $m[a_{i+1}] = min(m[a_{i+1}], dp_i)$. Com essa otimização, a transição da $dp$ está sendo realizada em $O(1)$, logo calculamos a $dp$ toda em $O(n)$, que passa nas constantes do problema.

Clique aqui para ver o código