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

Una implementación directa y sin optimizaciones ni podas para los casas donde n = 8 hará uso de 1\times2\times3\times4\times5\times6\times7\times8\times7\times6\times5\times4\times3\times2\times1=203212800 operaciones, lo cual no está muy lejos de ser una solución eficiente. Entonces bastan algunas podas para obtener una solución al 100%, podemos por ejemplo podar las ramas de la recursión que consideran combinaciones con una diagonal invertida repetida.

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