Solución a "Problema"

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

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

Ahora, como $latex s(A) - (s(S) - s(A)) = 2 \times s(A) - s(S)$, entonces tenemos que minimizar $latex 2 \times s(A) - s(S)$ que es lo mismo que minimizar $latex s(A) - s(S)/2$. O sea, debemos de encontrar una subsecuencia $latex A$ cuya suma esté lo más cercana a la mitad de la suma de $latex S$, en particular podemos restringir nuestra búsqueda a las subsecuencias cuya suma sea menor o igual a $latex 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 $latex S$ y considera todas las posibles diferentes sumas de subsecuencias cuyos elementos tienen índices menores o iguales al actual y cuya suma no excede $latex s(S)/2$. Se tendrán entonces $latex 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 $latex O (n \times s(S))$.

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

• Etapa 1
• Examen 10
• Hugo Dueñas
• preselectivo
• solución
• Soluciones Preselectivo 2013