Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10
Autor: Hugo Dueñas
Primero, dado una secuencia denotaremos por
a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia
debemos de econtrar una subsecuencia
de
tal que
sea la minima posible.
Ahora, como , entonces tenemos que minimizar
que es lo mismo que minimizar
. O sea, debemos de encontrar una subsecuencia
cuya suma esté lo más cercana a la mitad de la suma de
, en particular podemos restringir nuestra búsqueda a las subsecuencias cuya suma sea menor o igual a
.
Se plantea para este problema una solución de tipo Programación Dinámcia que corre sobre los elementos de la secuencia y considera todas las posibles diferentes sumas de subsecuencias cuyos elementos tienen índices menores o iguales al actual y cuya suma no excede
. Se tendrán entonces
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
.
A continación se lista una implementación en C++ de la solución: