¿Alguien tendrá el código de este problema?: es la B del CIIC 2016
https://omegaup.com/arena/CIIC-2016#problems/Calendario-Azteca
creo que sale con flujos, esta feo :'v.
2 Me gusta
¡Hola!
Adjunto el pdf de esa CIIC para referencia. Si nadie respondió, cuando tenga tiempo me pongo a mirarlo 
ExamenFinalCIIC2016.pdf (567,3 KB)
1 me gusta
Primero que nada, comentar que para obtener 100 puntos este es un problema bastante difícil.
Modelando con grafos, el problema se puede reenunciar como calcular el número cromático de un grafo intersección de arcos de circunferencia.
Determinar si un grafo arco-circular es K-coloreable es NP-completo en general. En este problema se pide calcular el K mínimo, pero nos garantizan que es pequeño (K \leq 7 según las cotas), así que por lo tanto allí está la clave: el algoritmo que hay que hacer seguramente sea exponencial en K, y aprovechará que K es pequeño, pues si no lo hacemos así, tendríamos que encontrar un algoritmo polinomial para un problema NP-hard, y se cree muy fuertemente que no existe tal cosa.
Gracias a la garantía K \leq 7, podemos de hecho probar hasta 6, y si con 6 colores no alcanzó, es que K=7.
Para verificar si es posible con K colores, se puede utilizar programación dinámica, recorriendo los N días del círculo a partir de algún 0 prefijado arbitrariamente. Cada vez que se abre un período nuevo, debemos asignarle un color que no esté actualmente ocupado. Por eso, en el estado de programación dinámica se debe guardar por qué número de día vamos, y también la asignación de colores a intervalos aún abiertos, ya que esa asignación determina qué opciones de asignación tenemos disponibles cuando abre un nuevo intervalo. Al final de todo se cierra el círculo, y para que la solución sea válida tenemos que llegar al estado final con una asignación de colores que no entre en conflicto con los colores que usamos para los primeros intervalos que abrían en el punto que tomamos como “0” (que podemos inicialmente pintar arbitrariamente con los colores 1,2,3,4, etc en orden a los intervalos que pasen por allí).
La información de “cómo están asignados los intervalos abiertos en este puntos a colores” es claramente exponencial en K, en particular la codificación más simple y directa podría necesitar almacenar K^K opciones diferentes (puede haber hasta K intervalos abiertos a la vez, si no ya se sabe que es directamente imposible colorear con K colores. Y por cada uno de los K, hay que guardar cuál de los K colores de referencia se usa).
Aún así, esta cota de 6^6 \cdot 1000 para los estados totales recorridos en peor caso no es tan grande, y allí está la clave de la solución.
2 Me gusta