Solução Informática - Nível Avançado - Semana 36

Solução escrita por Arthur Lobo

Conhecimento prévio necessário:

• MST

Primeiro vamos reduzir o problema para um grafo: cada bola será representada por um vértice, e vamos criar uma aresta entre todo par de vértices $(i,j)$ com peso sendo a pontuação recebida quando as duas bolas são escolhidas para uma operação, ou seja, $({A_i}^{A_j} + {A_j}^{A_i}) mod M$.

Agora vamos imaginar um conjunto válido de $N-1$ pares de bolas escolhidas e destacar as arestas correspondentes a essas escolhas no nosso grafo. Quando um conjunto de escolhas é válido, ou seja, quando é possível que realizar uma sequência válida de escolhas que resulte nesse conjunto?

As arestas escolhidas não podem formar nenhum ciclo! Essa é a única restrição que o conjunto precisa ter. Observe que, caso tenha algum ciclo, alguma bola terá que ser removida duas vezes. E sempre que não existe um ciclo, podemos fazer uma espécie de ordenação topológica para montar a sequência válida de remoções.

Agora nosso problema é: Dado um grafo completo, escolha um conjunto de $N-1$ arestas de modo que a soma dos pesos delas seja máximo e não exista nenhum ciclo.

$N-1$ arestas e nenhum ciclo, isso te lembra alguma coisa?  É uma árvore! Queremos encontrar a maior árvore contida nesse grafo completo, ou seja, a Árvore Geradora Máxima (Maximum Spanning Tree). Podemos encontrar a MaximumST da mesma forma que fazemos com a MinimumST, mas ordenando da maior aresta para a menor.

A complexidade fica $O(N^2*logN)$, porque temos $N^2$ arestas e ordenamos elas em $N^2logN$.

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