Below you will find pages that utilize the taxonomy term “Examen 17”
Posts
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.
Posts
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.