Below you will find pages that utilize the taxonomy term “Hugo Dueñas”
Posts
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$.
Posts
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 $latex 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).