Esse é um desafio que originalmente era uma tarefa do alemão Bundeswettbewerb Informatik (concurso federal de ciência da computação [?]), Um concurso para estudantes do ensino médio. Ao contrário da pergunta original, onde você precisa encontrar uma boa solução e escrever alguma documentação, eu quero que você jogue isso. Eu tento replicar a pergunta da melhor maneira possível:
Desafio
Muitas cidades da Europa têm as chamadas cidades gêmeas . Este ano, há um Jubileu especial em que cada par de cidades gêmeas na UE organiza um festival para celebrar sua parceria. Para garantir que nenhuma cidade precise organizar muitos festivais, cada cidade tem um limite de festivais que pode organizar. É possível distribuir os festivais entre as cidades gêmeas de uma maneira que cada par de cidades gêmeas organize um festival em uma das duas cidades e nenhuma cidade organize mais festivais do que é permitido? Se sim, explique como.
Este é um mapa de algumas cidades, suas parcerias e seus limites de festivais.
parcerias http://dl.dropbox.com/u/1869832/partnerships.png
Exigências
- Seu programa deve encerrar o problema em um minuto cada para os dois casos de teste. (Ver abaixo)
- Consulte as caixas de teste para o formato de entrada.
A saída deve estar vazia se não houver solução e deve ter o seguinte formato: Caso contrário, uma linha para cada par de cidades gêmeas,
a
secity1
organizar o festivalb
.<city1>, <city2>, <a/b>
A solução com o menor número de caracteres que satisfaz os requisitos vence. Em caso de empate, o programa enviado primeiro vence.
- Aplicam-se regras usuais de código-golfe.
Casos de teste
A tarefa original tinha dois casos de teste. Eu os carreguei no github .
fonte
n
nós, onden
é o limite de orçamento da cidade).Respostas:
Python, 380 caracteres
Esse código usa um algoritmo de fluxo máximo no estilo push-re-label .
N[x]
é o número de participantes permitido emx
,X[x]
é a lista de cidades parceiras atualmente programadas para hospedar emx
(que pode ser maior queN[x]
durante o algoritmo) eH[x]
é a altura rotulada dex
. Para qualquer cidade com excesso de assinaturas, enviamos uma das partes programadas para uma cidade parceira mais baixa ou aumentamos sua altura.fonte
C #,
1016992916caracteresLeva 4 segundos para mim no grande conjunto de testes; o desempenho pode ser facilmente aprimorado muito fazendo
X
umHashSet<s>
ao invés de umList<s>
.Isso usa a redução ao fluxo máximo, como sugeri anteriormente nos comentários. Os vértices são
S
e coletor recém-geradosT
.As arestas são
O algoritmo é Ford-Fulkerson com DFS. É óbvio a priori que cada caminho aumentado aumentará o fluxo em 1; portanto, a otimização do golfe de remover o cálculo do fluxo do caminho não tem efeito negativo no desempenho.
Existem outras otimizações possíveis, fazendo suposições como "Os nomes dos arquivos de entrada nunca serão os mesmos das cidades", mas isso é um pouco confuso para IMO.
fonte