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:

Leave a Reply Cancel reply