BWInf 2011, pregunta 5: Ciudades gemelas

Este es un desafío que originalmente fue un gusto para el Bundeswettbewerb Informatik alemán (competencia federal de informática [?]), Una competencia para estudiantes de secundaria. A diferencia de la pregunta original, donde tienes que encontrar una buena solución y escribir alguna documentación, quiero que juegues al golf. Intento replicar la pregunta lo mejor posible:

Desafío

Muchas ciudades en Europa tienen las llamadas ciudades gemelas . Este año, hay un Jubileo especial donde cada par de ciudades gemelas en la UE organiza un festival para celebrar su asociación. Para garantizar que ninguna ciudad tenga que organizar demasiados festivales, cada ciudad tiene un límite de festivales que puede organizar. ¿Es posible distribuir los festivales entre las ciudades gemelas de tal manera que cada par de ciudades gemelas organice un festival en una de las dos ciudades y ninguna ciudad organice más festivales de los que está permitido? En caso afirmativo, explique cómo.

Este es un mapa de algunas ciudades, sus asociaciones y sus límites de festivales.

asociaciones http://dl.dropbox.com/u/1869832/partnerships.png

Requisitos

• Su programa debe resolver el problema en un minuto cada uno para ambos casos de prueba. (Vea abajo)
• Consulte los casos de prueba para el formato de entrada.

• El resultado debe estar vacío si no existe una solución y, de lo contrario, debe tener el siguiente formato: una línea para cada par de ciudades gemelas, asi city1organiza el festival, de lo bcontrario.

  <city1>, <city2>, <a/b>
  

• La solución con el menor número de caracteres que satisfaga los requisitos gana. En caso de empate, el programa que se presentó primero gana.

• Se aplican las reglas habituales de código de golf.

Casos de prueba

La tarea original tenía dos casos de prueba. Los he subido a github .

Python, 380 caracteres

import sys
N={};H={};X={}
for L in open(sys.argv[1]):n,x,y=L.split('"');N[x]=int(n);H[x]=0;X[x]=[]
for L in open(sys.argv[2]):s,t=eval(L);X[s]+=[t]
p=1
while p:
 p=0
 for x in N:
  if len(X[x])>N[x]:
   p=1;S=[y for y in X[x]if H[y]<H[x]]
   if S:X[x].remove(S[0]);X[S[0]]+=[x]
   else:H[x]+=1
   if H[x]>2*len(N):sys.exit(0)
for x in N:
 for y in X[x]:print'"%s", "%s", a'%(x,y)

Este código utiliza un algoritmo de flujo máximo de estilo push-relabel . N[x]es la cantidad de partes permitidas en x, X[x]es la lista de ciudades asociadas actualmente programadas para hospedar en x(que puede ser más larga que N[x]durante el algoritmo), y H[x]es la altura etiquetada de x. Para cualquier ciudad con exceso de suscripción, empujamos una de sus fiestas programadas a una ciudad asociada más baja o aumentamos su altura.

C #, 1016992916 caracteres

Me toma 4 segundos en el conjunto de prueba grande; el rendimiento se puede mejorar fácilmente haciendo Xun en HashSet<s>lugar de un List<s>.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D<T>:Dictionary<s,T>{}class E:D<int>{static void Main(s[]x){s
S="",T=">",l;s[]b;D<E>R=new D<E>(),P=new D<E>();R[S]=new E();R[T]=new E();foreach(s L in
File.ReadAllLines(x[0])){b=L.Split('"');s f=b[1];R[T][f]=0;R[f]=new E();P[f]=new
E();R[f][T]=int.Parse(b[0].Trim());}foreach(s L in File.ReadAllLines(x[1])){b=L.Split('"');s
f=b[1],t=b[3],v=f+t;R[v]=new
E();R[v][S]=R[f][v]=R[t][v]=0;P[f][t]=R[S][v]=R[v][f]=R[v][t]=1;}for(;;){List<s>X=new
s[]{S}.ToList(),A=X.ToList();w:while((l=A.Last())!=T){foreach(s t in
R[l].Keys){if(!X.Contains(t)&R[l][t]>0){X.Add(t);A.Add(t);goto
w;}}A.RemoveAt(A.Count-1);if(!A.Any())goto q;}l=S;foreach(s n in
A.Skip(1)){R[l][n]--;R[n][l]++;l=n;}}q:if(R[S].Values.Contains(1))return;foreach(s
f in P.Keys)foreach(s t in P[f].Keys)Console.WriteLine(f+", "+t+", "+"ba"[R[f][f+t]]);}}

Esto utiliza la reducción al flujo máximo que indiqué anteriormente en los comentarios. Los vértices son

1. Una fuente Sy un sumidero recién generados T.
2. Las alianzas.
3. Las ciudades.

Los bordes son

1. Desde la fuente hasta cada asociación con capacidad de flujo 1.
2. De cada asociación a cada ciudad en la asociación con capacidad de flujo 1.
3. De cada ciudad al sumidero con una capacidad de flujo igual al presupuesto de esa ciudad.

El algoritmo es Ford-Fulkerson con DFS. Es obvio a priori que cada ruta de aumento aumentará el flujo en 1, por lo que la optimización de golf para eliminar el cálculo del flujo de la ruta no tiene ningún efecto negativo en el rendimiento.

Hay otras posibles optimizaciones haciendo suposiciones como "Los nombres de los archivos de entrada nunca serán los mismos que los nombres de las ciudades", pero eso es un poco dudoso en mi opinión.