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.