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

Your email address will not be published. Required fields are marked *