Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Khayyam Fuente: Khayyam La primera observación que hay que hacer es que si todas las carreteras son bidireccionales y entre cada par de ciudades existe exactamente un camino que las conecta (usando una o mas carreteras) entonces la representación gráfica del problema es un árbol: los nodos representan las ciudades y las aristas representan las carreteras. La siguiente figura, muestra el árbol que representa el caso de prueba dado como ejemplo.

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1 Autor: Freddy Román Cepeda Fuente: Freddy Este problema es bastante sencillo de entender, la dificultad radica en que exponenciar un número de la manera obvia no es lo suficientemente rápido para obtener todos los puntos disponibles. Subtarea 1 Para obtener el primer grupo de puntos, sólo basta calcular $latex N^M$ multiplicando a $latex N$ por sí mismo $latex M$ veces, teniendo cuidado de que no haya overflow.

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1 Autor: Joemmanuel Ponce Galindo Fuente: Topcoder Básicamente lo que nos pide el problema es encontrar el número de cartas que son distintas entre la configuración que es dada como entrada y una configuración donde las cartas estén alternadas. Cómo se explica en el problema, sólo hay 2 estados posibles en los que una carta puede estar: negro (B) y blanco (W).

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 4 Autor: Ethan Jiménez Vargas Después de comprender el problema podemos deducir dos cosas: Los N puntos de la cueva modelan un árbol, esto debido a la propiedad de que existirán N-1 aristas y siempre hay un camino entre cualquier par de nodos. Podemos traducir la tarea principal del problema a lo siguiente “Para cada una de las Q preguntas, ¿el nodo A es un ancestro del nodo B?

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12 Autor: Ethan Jiménez Vargas La clave para resolver este problema es interpretar las palabras como nodos y los cambios entre palabras como aristas, de manera que podamos verlo todo como un grafo no dirigido. Asignamos a cada palabra un nodo y creamos las aristas entre nodos verificando alguna de las condiciones que se proponen en el enunciado del problema: si una palabra A es un prefijo o sufijo de la palabra B o la palabra A difiere con la palabra B por un solo caracter, establecemos una arista entre los nodos A y B.

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 7 **Autor: **Enrique Lira Vargas Lo importante de este problema es notar como se puede usar un backtracking para contar cosas. En este caso lo que se debía contar era la cantidad de formas de llegar a una cantidad sumando una o más veces una serie de cantidades dadas. Solución de 30, 50 puntos Generar todas las combinaciones que sumen la cantidad C pedida.

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 5 **Autor: **Enrique Lira Vargas Este problema no requiere ninguna observación específica y realmente lo único que hay que hacer es una búsqueda. Para los primeros 50 puntos Este primer sub set de casos se puede resolver implementando una búsqueda en amplitud que nos dé el camino más corto entre dos puntos en un mapa con paredes. Para los 75 puntos Para este punto se me ocurrió una solución factible para aquellos que no saben construir una cola de prioridad, correr una búsqueda en amplitud con dos colas cuidando elegir siempre la siguiente posición con una menor cantidad de movimientos de las dos colas.

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 5 **Autor: **Saul de Nova Caballero En pocas palabras el problema es, dado un árbol que se puede colorear, encuentra la menor solución satisfaciendo las restricciones dadas sobre los colores. Este problema es un caso particular de Graph Coloring(en español coloración de grafos), en donde el grafo es un árbol. Subcaso 1(10 puntos) Para el primer subcaso era posible hacer una búsqueda en profunidad sobre todos los nodos, encontrando la menor solución.

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)).