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. Podemos entonces en una matriz de 2xn colocar en cada columna cuántas secuencias distintas hay que en la posición i-ésima terminen en negro y cuántas en blanco de tal modo que no haya dos cuentas negras consecutivas. Simplemente, para obtener los números de la siguiente posición, observamos que el número de las que terminan en blanco es la suma de ambos números de la posición anterior y de las que terminan en negro es el número de secuencias que terminan en blanco de la posición anterior.

Resta solo un detalle más a considerar. Requerimos que la secuencia no inicie y termine en negro, pues los extremos quedarán adyacentes al cerrar la pulsera. Una forma de resolver esto es la siguiente: Contamos, con el método descrito, cuántas secuencias distintas hay que inicien con blanco y que no tengan dos cuentas negras consecutivas. El número que nos pide el problema será entonces la cantidad de pulseras que empiezan con blanco y cumplen con que no haya dos negras consecutivas (independientemente de con qué color terminen) más el número de pulseras que inicien con negro y terminen con blanco (y claro, cumplan con que no haya dos negras consecutivas). ¿Cuántas hay de estas últimas? La misma cantidad que de pulseras que inician con blanco y terminan con negro, pues su simétrica inicia con negro, termina con blanco y claramente sigue cumpliendo el que no posea dos cuentas negras consecutivas. Así que es posible resolver el problema con un código muy breve, como se muestra abajo.

Solo resta mencionar que hay que tener cuidado de aplicar el módulo correctamente. Se pueden evitar errores definiendo el valor del mismo para no tener que escribir el número varias veces.

El siguiente código resuelve el problema:

Solución a “Problema”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10
Autor: Hugo Dueñas

Primero, dado una secuencia A denotaremos por s(A) a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia S debemos de econtrar una subsecuencia A de S tal que s(A) - (s(S) - s(A)) sea la minima posible.

Ahora, como s(A) - (s(S) - s(A)) = 2 \times s(A) - s(S), entonces tenemos que minimizar 2 \times s(A) - s(S) que es lo mismo que minimizar s(A) - s(S)/2. O sea, debemos de encontrar una subsecuencia A cuya suma esté lo más cercana a la mitad de la suma de S, en particular podemos restringir nuestra búsqueda a las subsecuencias cuya suma sea menor o igual a s(S)/2.

Se plantea para este problema una solución de tipo Programación Dinámcia que corre sobre los elementos de la secuencia S y considera todas las posibles diferentes sumas de subsecuencias cuyos elementos tienen índices menores o iguales al actual y cuya suma no excede s(S)/2. Se tendrán entonces n \times s(S)/2 posibles estados y cada uno podrá ser procesado en tiempo constante ya que solo hay dos trancisiones posibles para cada estado: Se toma el elemento actual dentro de la subsecuencia o no. Por lo tanto la solución tendrá una complejidad temporal de O (n \times s(S)).

A continación se lista una implementación en C++ de la solución:

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.

Continue reading