Below you will find pages that utilize the taxonomy term “Soluciones Preselectivo 2013”
Posts
Solución a "Químicos"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 6 Autor: Luis Héctor Chávez (lhchavez) Fuente: Ethan Jiménez Vargas
Éste es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.
El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible.
Posts
Solución a "Crucero"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4 Autor: Saúl Germán Gutiérrez Calderón Fuente: USACO Enero 2009 Gold
Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.
Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.
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 alternativa a "Decepción"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Freddy Román Cepeda Fuente: Ethan Jiménez Vargas
Esta es una solución alternativa al problema. La solución pensada originalmente consiste en una búsqueda podada. Sin embargo, esta solución corre en tiempo y memoria $latex O(N^2)$, mucho mejor de lo necesario para obtener todos los puntos.
Podemos dividir el problema a la mitad con una observación simple: la torre más alta debe verse desde ambos lados.
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.
Posts
Solución a "Mapas de bits"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12 Autor: Jorge Alberto González Martínez Fuente: Jorge Alberto González Martínez
En el problema se describen dos formas de representar un mapa de bits.
La forma bidimensional es simplemente utilizar una matriz para representar los bits. La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.
Posts
Solución a "Pista"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14 Autor: Miguel Covarrubias Fuente: Codeforces
Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.
Para $latex N \le 10$ se pueden checar todas las $latex 2^N$ configuraciones de pistas. Para $latex N \le 1000$ funciona una dinámica $latex O(N^2)$, donde los estados son (posición, altura/profundidad que se lleva hasta el momento).
Posts
Solución a "Cueva"
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?
Posts
Solución a "Chilly Rapero"
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.
Posts
Solución a "Cambio"
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.
Posts
Solución a "Minecraft"
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.
Posts
Solución a "K-Arbol"
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.
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.
Posts
Solución a "Problema"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 **Autor: **Hugo Dueñas
Primero, dado una secuencia $latex A$ denotaremos por $latex s(A)$ a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia $latex S$ debemos de econtrar una subsecuencia $latex A$ de $latex S$ tal que $latex s(A) - (s(S) - s(A))$ sea la minima posible.
Ahora, como $latex s(A) - (s(S) - s(A)) = 2 \times s(A) - s(S)$, entonces tenemos que minimizar $latex 2 \times s(A) - s(S)$ que es lo mismo que minimizar $latex s(A) - s(S)/2$.
Posts
Solución a "Alfiles"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 7 **Autor: **Hugo Dueñas
Lo primero que se debe de notar es que en cada una de las $latex 2n-1$ diagonales principales, las cuales mostradas en la imagen de abajo, habrá máximo 1 alfil. Lo mismo se cumple para las diagonales invertidas, mostradas también en una imagen abajo.
Ahora, cada diagonal principal se cruza con ciertas diagonales invertidas. Entonces se plantea una solución de tipo Backtracking que corre sobre las diagonales principales marcando diagonales invertidas a cada paso (representando que se ha colocado un alfil en el cruce de esas dos diagonales).
Posts
Solución a "Mario Reloaded"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8 **Autor: **Pavel Herrera Dominguez)
Observaciones Lo primero es ver como se modelan los estados del problema sin pensar en que Mario puede tomar los atajos, únicamente pensar en las llaves, claramente existen $latex n\times2^m$ estados, pues no importa el orden en que se toman las llaves solo las llaves que se tienen al llegar a cada puerta. A partir de aquí nos referiremos como estado a la puerta y las llaves que trae Mario.
Posts
Solución a "El collar de perlas"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10** Autor: **Félix Rafael Horta Cuadrilla
En una bosque habitan dos clanes de enanos: los enanos rojos y los enanos verdes. Durante sus expediciones en las cuevas cercanas, un grupo de enanos rojos y verdes encontraron un collar formado por perlas blancas y negras que no tienen ningun valor, pero al final del collar hay un valioso diamante. Los dos clanes de enanos quieren apoderarse del diamante.
Para resolver el problema de manera pacifica deciden jugar el siguiente juego: a cada uno de los N enanos se le asigna un numero del 1 al N (un numero diferente para cada enano) y dos listas de numeros, una negra y una blanca (las listas pueden ser diferentes entre si). Cada lista contiene una cantidad diferente de numeros, cada numero i en cualquier lista representa al enano i.
Durante el juego, el collar se pasa de un enano a otro de acuerdo con las siguientes reglas: cuando un enano recibe el collar, el quita la primer perla en el collar y si la perla es blanca, entonces pasa lo que quedo del collar a cualquier enano que este en su lista blanca (al que el quiera), pero si la piedra es negra, entonces pasa lo que quedo del collar a algun enano de su lista negra. Para empezar el juego, el collar se le da a un enano aleatoriamente.
En algun momento el collar solamente va a tener el diamante, el enano que recibe el collar en este estado gana el diamante para su clan y el juego termina.
Posts
Solución a "Teclado Roto"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 2** Autor: **Jorge Alberto González Martínez
Los temas para el examen donde apareció este problema eran pilas, colas y búsqueda binaria. Después de haber estudiado los temas, es buena idea combinar la teoría aprendida.
El problema del teclado roto describe una serie de operaciones en las que es necesaria una estructura en la que sea posible agregar elementos por ambos lados (izquierda y derecha).
Posts
Solución a "El Artista Lento"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 2** Autor: **Christian Hernández
Lo primero de lo que debemos darnos cuenta es de que como los pedazos son de dimensiones enteras y se colocan en dimensiones enteras, podemos “pensar” el problema de manera que en lugar de pegar rectángulos de Mi x Ni, estamos pegando Mi x Ni de 1 x 1 (Ejemplo: Si tuvieramos que pegar un rectángulo de 4 x 3, podemos pensarlo como pegar 12 rectangulos de 1 x 1).
Posts
Solución a "Engranes"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 1** Autor: **Omar Ocegueda (Khayyam) **Solución por: **Enrique Lira
Para poder resolver este problema hay que ver ciertas propiedades a las cuales podemos llegar fácilmente a partir de ejemplos. Una primera duda que nos surge es: ¿Vuelve al estado inicial?, si hacemos un par de ejemplos podemos ver que si, otra duda que nos surge es: ¿Cuándo vuelve al estado inicial?, y aquí comienza lo complicado.
Posts
Solución a "Juego Lento"
Concurso:Preselectivo para la IOI 2013, Etapa 1, Examen 1
Autor: Ethan Jimenez
Empecemos analizando el caso en que solo jugamos con un montón de fichas, dada la restricción de tomar únicamente una sola ficha el juego se vuelve predecible ya que no hay más opción que tomar una ficha de ese montón. Si el montón tiene una sola ficha el jugador con el primer turno pierde, si hay dos fichas el jugador con el primer turno gana, si hay tres fichas el jugador con el primer turno pierde, y así alternadamente, podemos entonces deducir que si hay un número impar de fichas en el montón, el jugador con el primer turno perderá, por el otro lado, si el montón tiene un número par de fichas ganará la partida.