Hooligan

Na final brasileira da maratona de programação de 2009, caiu um problema relacionado a futebol, chamado Hooligan, cujo enunciado pode ser acessado aqui.

Vou tentar resumi-lo. Temos um campeonato onde todos os times se enfrentam exatamente k vezes. Em um campeonato por pontos corridos, como o Brasileirão, temos k=2. Porém, diferentemente de um campeonato normal, vitória vale 2 pontos (e não 3), empate 1 e derrota 0. Imagine agora que estamos a certa altura do campeonato e algumas partidas já foram jogadas. A pergunta é: existe uma combinação dos resultados dos jogos restantes que fará com que o time para o qual estamos torcendo, seja não somente o campeão, mas que também tenha mais pontos que o segundo colocado?

Esse problema pode ser modelado como fluxo em redes e resolvido com um algoritmo de fluxo máximo. No dia da prova pensamos em modelá-lo dessa forma, mas não conseguimos chegar a um modelo correto.

Fluxo em redes

A primeira coisa a se fazer, é processar as partidas já realizadas, computando os pontos de cada time de acordo com a regra. Depois, observamos que, sem perda de generalidade, podemos fazer o nosso time predileto ganhar todas as partidas que lhe restam.

Seja o número total de pontos que nosso time tem após todas essas considerações. Observe que é a melhor pontuação que o nosso time pode obter. Porém, para que ele ganhe o campeonato, dependemos da pontuação dos outros times. Queremos uma combinação de jogos em que nenhum dos times restantes tenha mais do que pontos.

Se, mesmo antes de considerar os jogos não realizados, já houver time com ou mais pontos, não há o que fazer. Consideremos então que todos os times têm no máximo pontos. Seja o número de pontos do time i. Queremos que um time i ganhe no máximo pontos com as próximas partidas.

Vamos definir nosso grafo. Crie um nó para cada partida restante e um nó para cada time, além dos vértices fonte e destino, s e t, respectivamente. Para cada partida p, crie uma aresta (s, p) com capacidade 2, que representa o total de pontos que aquela partida vale. Além do mais, sejam u e v os times envolvidos na partida p. Crie uma aresta (p,u) e (p,v), ambas com capacidade 2. Finalmente, para cada time i, crie uma aresta (i, t) com capacidade .

Modelagem de uma partida entre os times u e v.

Afirmamos que existe uma combinação de resultados tal que nosso time de escolha fique em primeiro lugar isolado, se e somente se, o fluxo máximo na grafo definido acima for exatamente igual a 2*npr onde npr é o número de partidas restantes.

Prova: Observe que se o fluxo máximo for 2*npr, todas as arestas que saem de s estarão saturadas, ou seja, estará passando 2 unidades de fluxo. Temos duas arestas saindo de cada partida p. Sejam fu e fv a quantidade de fluxo nessas arestas respectivamente. Dadas as 2 unidades de fluxo chegando em p, as possíveis saídas (fu, fv) são (2, 0), (1, 1) ou (0, 2), sendo que cada uma dessas possibilidades representa um possível resultado de jogo. Já para cada time i, a quantidade de fluxo que chega no seu vértice correspondente a partir de uma dada partida p, é a quantidade de pontos que ganhou com aquela partida. Por conseguinte, a quantidade de fluxo que sai dele é o total de pontos conquistados. Note que, devido à capacidade da aresta, estamos limitando a quantidade de pontos que um dado time pode ganhar. Assim, se o fluxo é 2*npr, significa que conseguimos distribuir os pontos das partidas restantes entre os times, de forma que nenhum deles alcance nosso time predileto.

Além disso, dada uma combinação de resultados das partidas, é fácil construir um fluxo máximo de tamanho 2*npr.

Modelagem de um time.

Uma otimização para que o grafo não fique muito grande é: se existem k’ partidas restantes entre os times u e v, ao invés de criar k’ nós, criamos apenas um, mas multiplicamos as capacidades das arestas de entrada e saída por k’.

Observe que o sistema de pontuação foi modificado para que essa modelagem fosse possível. Se a vitória valesse 3, não conseguiríamos modelar as pontuações (3, 0), (1, 1) e (0, 3).

Algoritmo Guloso

Alguns maratonistas implementaram uma solução gulosa, que foi aceita no site nuevo portal.

A ideia é a seguinte. Computamos os pontos dos jogos já ocorridos e também assumimos que o time escolhido ganha o restante de seus jogos. Além disso, assumimos, a princípio, que todos os outros times empatam seus jogos.

O passo guloso é assim: Verificamos se o nosso time está na liderança isolada. Se sim, então temos uma combinação de resultados válida. Caso contrário, selecionamos o primeiro colocado x (ou algum que esteja dividindo a liderança com nosso time) e o time pior classificado y que tinha inicialmente um jogo não jogado com x. Desfazemos o empate entre x e y e fazemos x perder pra y. Reordenamos os times com essa nova pontuação e repetimos o passo. Se não houver tal y, declaramos que não existe nenhuma configuração de jogos que leve à situação desejada.

Pensei em um contra-exemplo que pode estragar essa estratégia se nenhum cuidado adicional for tomado. Considere 7 times, A, B, C, D, E, F e G, sendo que estamos torcendo pelo time A. Suponha que k=1, e já tiveram vários jogos de forma que só restam as partidas: (B,E), (B,F), (C,E) e (D,E) e que A, B, C, D têm 7 pontos, F e G têm 5 e E tem 4 (depois de considerados os empates dos jogos restantes).

Imagine que o algoritmo selecione B para perder de E (que é o pior classificado), ficando B com 6 pontos e E com 5. Agora suponha que ele selecione C, que necessariamente tem que perder para E (é a única partida que lhe resta). C tem 6 e E tem 6. O único time que está empatado com A é o D, que só pode perder para E, fazendo com que D tenha 6 e E tenha 7. Agora E passa a ficar empatado com A, mas como E não tem mais jogos, o algoritmo vai acusar que não há solução.

Tabelas de classificação ao longo da execução do algoritmo guloso.

Porém, se B perder para F ao invés de E e tanto C quanto D perderem para E, todos esses times ficam com 6 pontos e A ficará na liderança isolada.

Tabelas de classificação ao longo da estratégia ótima.

Uma pergunta é: o resultado que eu usei como contra-exemplo pode ser obtido com alguma combinação de jogos? Eu fiz na mão e aparentemente dá sim. Tive inclusive que adicionar o vértice G para a conta bater :P (note que ele não é usado no contra-exemplo).

Porém, essa é uma pergunta que pode ser respondida com uma modelagem por fluxo em rede e uma consequente redução ao problema do fluxo máximo, usando as ideias do modelo apresentado anteriormente.

Os comentários estão fechados.

%d bloggers like this: