Below you will find pages that utilize the taxonomy term “Alain Acevedo”
Posts
Solución a "Metro"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12 **Autor: **Alain Acevedo Mejía
El problema en cuestión se reduce a encontrar un árbol de expansión mínima. La solución es una aplicación directa de alguno de los algoritmos existentes para ello (bien implementada), por lo que hablaré brevemente sobre una de las posibilidades y daré referencias donde puedan encontrar información más detallada.
Para encontrar el costo mínimo de unir todas las estaciones debemos encontrar el árbol de expansión mínima de la gráfica en cuestión (es decir, una subgráfica conexa que una todos los vértices de la gráfica original y cuyo peso (la suma de los costos de todas sus aristas) sea el mínimo posible (siempre es un árbol)).
Posts
Solución a "Pulseras"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 **Autor: **Alain Acevedo Mejía
Considero este problema como un buen ejemplo para quienes desean comenzar a trabajar con problemas de programación dinámica. Se nos pide calcular la cantidad de pulseras diferentes que se pueden construir bajo ciertas condiciones. Podemos comenzar preguntándonos, ¿qué sucede si la primera cuenta es negra? La siguiente podrá ser sólo blanca. Y si comenzamos con una blanca, la siguiente puede ser negra o blanca.
Posts
Solución a "Los Bloques de Link"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8 **Autor: **Alain Acevedo Mejía
Es claro que no es posible probar todas las sucesiones posibles de movimientos de los bloques para encontrar la solución (a excepción de casos muy simples). El número de tales sucesiones puede ser infinito en caso de que se puedan formar ciclos de movimientos (lo cual sucede en muchos de lo casos de prueba), y aún en casos donde el número sea finito puede suceder que no se tenga tiempo para probarlos todos.