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 hijos, para cada hijo
sea
el subárbol de
,
el número de hojas de
, y
el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a
. Si todas las
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
continúe estando balanceado. La única manera que le podemos restar peso a
sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada
sólo podemos restarle peso en múltiplos de
. Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande
tal que a todos los
les podamos restar un múltiplo de su respectivo
para obtener
. Notemos también que
es un múltiplo de
porque los nodos internos del árbol no tienen peso. Si
es el mínimo común múltiplo de todos los
, entonces
también es un múltiplo de
. Entonces, el máximo
posible es igual al múltiplo de
más grande que sea menor o igual a todos los
. Por lo tanto, el valor máximo obtenible del árbol completo es igual a
. 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
, y si seguimos restando
continuará balanceado.
De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, es la cantidad de hijos de la raíz,
el subárbol del
ésimo hijo, y
el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a
(o el del anterior si
tiene 2 niveles). Ahora
es igual a lo mínimo que le podemos restar a
y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de
y
.
El código siguiente implementa esta solución: