Solución a “Panoramas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Miguel Ángel Covarrubias
Fuente: Miguel Ángel Covarrubias

El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a s_1 y para cada s_i marcar los nodos en su camino hacia la raíz. Se puede usar DP o recursión para calcular el mínimo numero de vertices que conectan todos los nodos interesantes y pasan por la raíz para cada subárbol.

\mathrm{dp}_r=\mathrm{interesante}(r)\  \mathrm{si}\ \Sigma_h\mathrm{dp}_h=0
\mathrm{dp}_r = \Sigma_h\mathrm{dp}_h+1\  \mathrm{si}\ \Sigma_c\mathrm{dp}_h>0

h es un hijo de r. La arista extra (u,v) en el ciclo c permite usar otros caminos a lo largo de c. Tales caminos deben conectar todos los nodos en c que tengan nodos interesantes en su árbol después de quitar las aristas del ciclo E-c. Etiquetemos tales nodos con un uno y los demás nodos del c con un cero. Para E-(u,v) el ciclo sólo no cubre los últimos ceros. Para encontrar la solución sólo basta encontrar la secuencia de ceros más grande.
En el siguiente diagrama, la arista que falta es (u,v). La DP sólo no usa el último cero, pero es mejor no usar los dos ceros que están adyacentes.

  0 1
 /   \
1     0
 \   /
  1-0

Este código implementa la solución.

Solución a “Pista”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14
Autor: Miguel Covarrubias
Fuente: Codeforces

Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.

Para N \le 10 se pueden checar todas las 2^N configuraciones de pistas. Para N \le 1000 funciona una dinámica O(N^2), donde los estados son (posición, altura/profundidad que se lleva hasta el momento).

Les dejo la implementación de DiegoRoque como un muy buen ejemplo de una solución a este problema.

Solución a “Ubongo 3D”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: Miguel Covarrubias
Fuente: Miguel Covarrubias

La solución pone piezas de manera recursiva mientras quepan en el tablero y no se empalmen.

resuelve(pieza)
    si pieza > P
        regresa “Si”
    para cada rotación de la pieza
        para cada casilla g del tablero
            para cada cubo c de la pieza
                si al poner c sobre g, la pieza queda dentro de los primeros 2 niveles del tablero y no se empalma con otra pieza ya puesta entonces
                    marca las posiciones de los cubos de la pieza como ocupados
                    resuelve(pieza + 1)
                    desmarca los cubos de la pieza

Para rotar una pieza se puede rotar por 0^o, 90^o, 180^o o 270^o alrededor de cada eje. El número de operaciones es aproximadamente (número de rotaciones * número de casillas del tablero * número de cubos de una pieza)^3 \le (24 * 7 * 5)^3 < 600,000,000. En los casos de prueba y en el juego todas las soluciones tocan la base del tablero, si no fuera así, solo hay que duplicar el 7 a 14. Para checar si una pieza se puede poner en cierta posición se pueden usar mascaras de bits para los niveles del tablero y para las posiciones ocupadas. Para poner la última pieza se puede comparar todas las rotaciones de los cubos no ocupados contra la última pieza y la complejidad cubica de la solución se reduce a cuadrática.