Eu não to afim de fazer a análise desse problema não, até porque pela escovação de bits que precisei fazer pra passar minha solução, devem ter idéias melhores. Então só vou dar uma idéia básica de como eu fiz.
Considere um grafo cujos vértices sejam todas as sequencias de 2 letras minusculas, e há um arco de i para j se houver uma palavra que comece com i e termine com j. O custo desse arco é o comprimento da palavra negativo.
Nessas condições, o que queremos é um circuito com o custo médio mínimo.
O que não é muito difícil de perceber, é podemos esquecer os "circuitos" que repetem vértices, porque nesses casos, a média total é uma média ponderada de cada um de seus "subcircuitos", então se a primeira for mínima, a dos subcircuitos também tem que ser.
Aí usando a observação esperta de que se você soma o custo médio mínimo de um circuito em todos os custos das arestas, então você não tem mais circuitos negativos no seu grafo, então você pode fazer uma busca binária pela sua resposta.
Até aí é só pra dar uma idéia do que eu fiz. Agora as otimizações que eu tive que fazer pra isso passar:
- Não usei a queue da STL, implementei fila na mão.
- Retiro todas os arcos duplos, deixando só os com custo menor (de palavras maiores)
- Retiro todos os arcos que saem e entram no mesmo vértice, e depois eu faço a resposta ser o máximo entre a resposta no caso normal e o tamanho da maior palavra nesses casos.
- Abuso um pouco do fato dele deixar a precisão baixa, e faço a busca binária só enquanto d-e > 1.0e-2