Solución a “Mocha Hojas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Freddy Román Cepeda
Fuente: Alberto José Ramírez Valadez

Para simplificar el análisis, podemos notar que la respuesta que nos piden es igual al total de los pesos de las hojas del árbol menos el total de los pesos de las hojas del árbol ya balanceado. De ahora en adelante, trataremos el problema como si tuviéramos que conseguir este segundo valor, en vez del número de operaciones. Entonces queremos maximizar el peso total del árbol balanceado, para minimizar la cantidad de operaciones.

Consideremos el caso de un árbol con un solo nivel. Ya que sólo podemos restarle a los pesos de las hojas, evidentemente el peso máximo del árbol se alcanza cuando se emparejan todas las hojas al peso de la hoja con peso mínimo.

Ahora, consideremos un árbol con dos niveles. Si la raíz tiene $latex k$ hijos, para cada hijo $latex i$ sea $latex h_i$ el subárbol de $latex i$, $latex b_i$ el número de hojas de $latex h_i$, y $latex c_i$ el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a $latex h_i$. Si todas las $latex c_i$ son iguales, entonces nuestro árbol está balanceado. De lo contrario, debemos restar aún más para poder balancearlo. Sin embargo, también necesitamos que cada $latex h_i$ continúe estando balanceado. La única manera que le podemos restar peso a $latex h_i$ sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada $latex h_i$ sólo podemos restarle peso en múltiplos de $latex b_i$. Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande $latex x$ tal que a todos los $latex c_i$ les podamos restar un múltiplo de su respectivo $latex b_i$ para obtener $latex x$. Notemos también que $latex c_i$ es un múltiplo de $latex b_i$ porque los nodos internos del árbol no tienen peso. Si $latex m$ es el mínimo común múltiplo de todos los $latex b_i$, entonces $latex x$ también es un múltiplo de $latex m$. Entonces, el máximo $latex x$ posible es igual al múltiplo de $latex m$ más grande que sea menor o igual a todos los $latex c_i$. Por lo tanto, el valor máximo obtenible del árbol completo es igual a $latex kx$. Por último, si tuviéramos que restarle más peso a este árbol pero mantenerlo balanceado, es evidente que lo menos que podemos restar para mantenerlo balanceado es $latex km$, y si seguimos restando $latex km$ continuará balanceado.

De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, $latex k$ es la cantidad de hijos de la raíz, $latex h_i$ el subárbol del $latex i$ésimo hijo, y $latex c_i$ el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a $latex h_i$ (o el del anterior si $latex h_i$ tiene 2 niveles). Ahora $latex b_i$ es igual a lo mínimo que le podemos restar a $latex h_i$ y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de $latex b_i$ y $latex c_i$.

El código siguiente implementa esta solución:

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 $latex s_1$ y para cada $latex 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.

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

$latex h$ es un hijo de $latex r$. La arista extra $latex (u,v)$ en el ciclo $latex c$ permite usar otros caminos a lo largo de $latex c$. Tales caminos deben conectar todos los nodos en $latex c$ que tengan nodos interesantes en su árbol después de quitar las aristas del ciclo $latex E-c$. Etiquetemos tales nodos con un uno y los demás nodos del $latex c$ con un cero. Para $latex 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 $latex (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.