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). La descripción del problema muestra las restricciones, que no superan los 100, 000 elementos, por lo que es posible hacer un arreglo estático de caracteres de ese tamaño.

En el caso de mi solución, para que sea más clara la inserción, también utilizo memoria auxiliar para guardar las palabras que se van a insertar en la estructura de datos.

En el código que se muestra abajo se describe la forma en la que se implementa y opera la estructura mencionada anteriormente:

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). Podemos pensar lo mismo de los rectángulos adhesivos.

Si pensamos el problema sin rectángulos adhesivos, podríamos resolverlo teniendo en un arreglo matricial el color que se encuentra hasta arriba de cada rectángulo de 1 x 1 que tiene la cartulina.

Si tomamos la misma idea pero ahora teniendo en cuenta que existen rectángulos adhesivos, nos encontramos con el problema de que si rasgamos un cuadro necesitamos recordar el color la capa de papel que se encontraba debajo de la capa “visible”, y además podemos rasgar tantas veces como capas de papel hemos puesto. Con esto tenemos que necesitamos guardar un número de valores igual al número de capas que hemos puesto. Además tenemos que tener en cuenta el orden en el que fuimos poniendo las capas; esto es la última capa que pusimos debe de recordarse primero que la primera que pusimos, o en otras palabras: El primero que entras es el último que sale, así como el el último que entra es el primero que sale. Ese comportamiento lo encontramos en la estructura de datos Pila (Si no conoces la estructura de datos, puedes consultarla acá).

A continuación se encuentra la implementación de una estrúctura Pila que nos serviría para este problema:

struct Pila{
		char arreglo[2002];
		short int posActual;
		
		//Devuelve si la pila esta vacia
		bool estaVacia(){
				return posActual == 0;
		}
		
		//inserta un elemento en cima de la pila
		void push(char valor){
				posActual++;
				arreglo[posActual] = valor; 
		}

		//quita el elemento de la cima de la pila y lo devuelve
		char pop(){
				char valor = 0;
				if(!estaVacia()){
						valor = arreglo[posActual];
						posActual--;
				}
				return valor;
		}

		//devuelve el valor del elemento de la cima de la pila
		char top(){
				return arreglo[posActual];
		}
};



Es importante notar que esta es una implementación estática de una Pila (Siempre ocupa el mismo espacio en memoria sin importar el número de elementos, además de que el número de elementos máximo ya está definido). Como se ve, se han utilizado char para guardar los valores, ya que el valor de los colores llega hasta 100, por lo que un char es más que suficiente.

Entonces teniendo pilas para recordar todas nuestras capas de papel en orden, lo que podemos hacer es hacer un arreglo matricial de pilas para resolver nuestro problema.

Básicamente, cada que agreguemos un rectágulo de papel a nuestra cartulina lo que tenemos que hacer es, para cada rectángulo de 1 x 1 que abarca, agregar el color a la pila en su posición en la matriz. Si se trata de un rectángulo adhesivo, hacemos justo lo contrario, sacamos un valor de la pilas correspondientes.

Sólo nos queda resolver el problema del grosor de la cartulina. Debido a que necesitamos desgarrala G veces con un rectángulo adhesivo, podemos pensar que se tratan de G capas de papel del color de la cartulina. Entonces, se reduce a inicializar nuestro arreglo pilas agregando G capas del color de la cartulina.

La complejidad de agregar una capa de papel a la cartulina es de O(M x N) (ya que una sola capa puede abarcar toda la cartulina), la misma aplica para usar un rectángulo adhesivo. Entonces la complejidad de agregar todas las capas quedaría O(M x N x K) donde K es el número de rectángulos por pegar. Inicializar la cartulina tendría una complejidad O(M x N x G) donde G es el grosor. Dejándonos con una complejidad final de O(M x N x (K + G)) que es suficientemente buena como para funcionar con los límites de tiempo establecidos.

La complejidad en memoria es igual de O(M x N x (K + G)), ya que se tienen que guardar las (K + G) capas de papel en la matriz de M x N.

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. Para saber cuando vuelve a su estado inicial hay que notar ciertas cosas, una de ellas es que en cuanto el diente 1 vuelve a tocar al valle 1 hemos vuelto al estado inicial, no hay forma de que el diente 0 toque al valle 0 sin haber vuelto al estado inicial, entonces hay que buscar ese instante.

Consideremos ra y rb como el número de vueltas que ha dado el engrane a y el engrane b respectivamente en un momento dado después de x pasos, hay que notar que si ra y rb son enteros significa que hemos vuelto al estado inicial o estamos en el estado inicial (ra igual a cero y rb igual a cero).

Para que tanto ra y rb sean enteros, es necesario que x sea divisible tanto por N como por M y hay que encontrar el numero más pequeño distinto de cero (cero es el momento inicial) en el que esto pasa. Para nuestra fortuna esto es fácilmente calculable y es algo que nos enseñan en la escuela, se llama mínimo común múltiplo.

mcm(N,M) = \frac{N * M}{MCD(N, M)}

Ya que sabemos después de cuantos pasos se repite (llamémoslos K), debemos notar que en esos K pasos ningún par (diente, valle) se va a repetir, dado que si se repite significaría que K no es el primer momento en el que se vuelve al estado inicial.

Sabiendo esto podemos saber cuantos dientes distintos pasan por cada valle, siendo K la cantidad de parejas (diente, valle) distintas que existen (no sé pueden generar más), se puede deducir que K / M es la cantidad de dientes distintos que pasan por cada valle, simplificando nos queda:

\frac{N}{MCD(N, M)}

Ahora hay que buscar una forma de saber el primer diente que pasa por un valle x, con un poco de observación podemos saber que el numero del primer diente en tocar al valle x esta dado por el residuo de la división x sobre N ( x mod N ).

Ya que sabemos cual es el primer diente en tocar al valle x, debemos buscar la forma de calcular los otros dientes, con algunos ejemplos podemos notar que el numero del siguiente diente es M mod N veces mayor que el actual.

En el peor de los casos, los N dientes pasan por todos los valles, resultando nuestra solución actual con una complejidad de O(LN) y funciona bastante bien para los 80 puntos del problema.

Para llegar a la solución de 100 puntos hay que notar que después de que un diente y se junta en un valle x, el siguiente diente en juntarse con el valle x no depende del valle sino solo del diente, es por esto que si el diente y pasa por un conjunto de valles y uno de ellos no es estable, ninguno de los otros lo será y viceversa si el diente y pasa por un valle x que es estable, todos los demás valles por los que pase serán estables. Sabiendo esto podemos guardarlo en un arreglo que nos diga por cada diente si pasa por valles estables o no, reduciendo la complejidad a O(N).

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.

La pregunta clave para este problema es, ¿realmente hay diferencia entre tomar una ficha de un montón y tomar una ficha de otro montón? Aumentemos la cantidad de montones en el juego, digamos que ahora tenemos dos montones de fichas, ambos montones tienen una sola ficha, el jugador con el primer turno ganará, detente por un momento a experimentar qué sucede si aumentamos la cantidad de fichas en un montón, en el otro y en ambos montones, teniendo en mente la pregunta anterior.

Después de probar con diferentes configuraciones de juego podemos decir que la respuesta a la pregunta es no, tomar primero una ficha de un montón no es diferente a haberla tomado de cualquier otro montón, con lo que podemos concluir que, si tenemos dos montones, el primero con a1 fichas y el segundo con a2 fichas, este juego es equivalente a tener un solo montón con a1+a2 fichas, una vez establecido podemos volver a nuestro análisis inicial y calcular quién ganará.

De manera análoga deducimos que si tenemos N montones de fichas y elegimos K de ellos, podemos reducir la configuración herpes transmission de esta partida a un juego con solo un montón de k1+k2+…+kN fichas, donde ki es el número de fichas en el montón elegido i. Una vez que sabemos lo anterior debemos darnos cuenta que para ganar tenemos que elegir K de los N montones cuya suma total sea un número impar.

Para asegurarnos que un conjunto de montones tiene un número impar de fichas debemos considerar lo siguiente, un número impar más un par da un número impar, un número impar sumado a un impar da un número par y un número par más un par da otro número par. Dado lo anterior podemos definir una regla para tener una suma total impar, debe existir una cantidad impar de montones con un número de fichas impar, si le agregamos cualquier cantidad montones con número de fichas par no se modifica la condición de tener un total impar.

En conclusión, es posible ganar el juego cuando existe más de un montón con número impar de fichas, si hay una cantidad impar de montones impares ya se cumple la condición deseada, pero si hay una cantidad par de montones impares debemos quitar uno para cumplirla, para obtener el juego con la mayor cantidad de fichas el montón que quitemos debe ser el que tenga menos fichas, nota que, como mencioné antes, agregar montones pares no afecta la condición de victoria, por lo que para aumentar la cantidad de fichas en el juego se deben agregar todos ellos.