Por Freddy
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: