11651. Banda

Olá meus amigos nerds, esquentem seus motores, pois hoje começa o code jam 2015 e é claro que vocês não vão querer perder essa.  E para começar bem o dia, nada melhor do que resolvermos um probleminha, não é mesmo?

Hoje vamos ajudar o Jimmy a montar sua banda, já que é isso que o problema 11651. Banda nos pede para fazer. Mais expecificamente, dada uma lista de músicos e suas respectivas afinidades e deseja-se escolher três dentre esses músicos de modo a maximizar a afinidade deles.

Solução

O problema é bem simples. Podemos modelar os músicos como sendo vértices de um grafo, desse modo as arestas do grafo representariam a afinidade entre o par de músicos representados pelos vértices. Agora basta percorrermos esse grafo e encontrarmos a trinca de músicos com a maior soma das afinidades. O seguinte algoritmo faz isso:

maxScore = -1

for i in vertices_grafo

    for j in vertices_adjacentes[i]

        for k in vertices_adjacentes[j]

            score = afinidade[i][j] + afinidade[i][k] + afinidade[j][k]

            if score > maxScore

                maxScore = score

                trio = (i, j, k)

O algoritmo acima é O(n^3), onde n é o número de vértices, mas como a entrada é pequena esse algoritmo é suficiente para resolver o problema e passar no tempo.

Implementação