Longest Zig Zag Subsequence: Análisis de la solución

Ayer el M.Sc. Jorge Terán, en la materia INF-143 nos planteó este problema… la solución se realizaba mediante dos vectores de tamaño n (donde n es la cantidad de datos). Sin embargo, también se puede solucionar mediante un solo vector de tamaño n, con una complejidad algorítmica de O(n)…

Ahora que tengo tu atención, voy a explicar cómo llegar a esta solución, y luego explicaré cómo es que esta solución funciona XD

Pero primero, sobre lo que encontrarás, y lo que no encontrarás aquí: Si estás esperando encontrar deliciosa copy-pasta del código para terminar tu tarea, te haz equivocado de post! por el contrario, si lo que buscas es entender la solución del problema, este post es para tí!

Statement: (Resúmen)

Para una descripción completa del problema, puedes ver el enunciado que M.Sc. Terán nos pasó en clases

Dada una secuencia de números en determinado orden, esta secuencia se denomina “secuencia zig-zag” si el número que resulta de restar el primer número del segundo, es de un signo distinto que el número que resulta de restar el segundo número del tercero… y este a su vez, es de signo distinto que el resultado de la resta del tercero con el cuarto… y así sucesivamente.

Se asume que el 0 es positivo y negativo ( demostración matemática), por lo que tiene el mismo signo que un número positivo y que un número negativo, y por lo tanto, cualquier secuencia que tenga dos números iguales seguidos, no es una secuencia zigzag.

Por ejemplo:


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1
Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Esta es una secuencia zigzag, porque los signos de sus restas están intercalados.

Dada una secuencia de números, determinar la longitud de la subsequencia zig-zag más grande que se pueda formar con éstos números

una subsecuencia se puede formar eliminando cualquier número de cualquier posición de la secuencia original.

Buscando una solución

cómo sabemos si una secuencia de números es una secuencia zig-zag?

Para determinar esto, necesitamos la resta de los números de la secuencia…


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1

Más concretamente, necesitamos saber la polaridad


Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Eso es! negativo, positivo, negativo, positivo, … eso es lo que buscamos en los números: que:
si hay una resta negativa: después tiene que haber, o bien nada, o bien una resta positiva.

Si hay una resta positiva: después tiene que haber, o bien nada, o bien una resta negativa.

De vuelta al problema… hay que encontrar la subsecuencia zig-zag más larga dentro de una secuencua dada de números. Puedo hacer esto si lo veo como un juego:

¿Cómo convierto una secuencia de números cualquiera, en una secuencia de números zig-zag eliminando la menor cantidad de números posible? Si de convertir se trata, entonces necesitaremos algo más que la polaridad de las restas: también necesitaremos la cantidad de las restas, para saber cuándo un (+) se puede convertir en un (-) luego de eliminar algún número de la secuencia.

Intentemos resolver un problema usando nuestro razonamiento… veamos este caso:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

Comenzando de izquierda a derecha, podemos ver: -, +, -, ¡-! y encontramos la primera incongruencia en el índice 4! ¿Qué hacemos? tenemos dos opciones:
1 STEP-FORWARD: borrar el índice 4
2 STEP-BACKWARD: borrar el índice 3

¿Cuál de estas dos nos conviene más? no lo sabemos: hay que probar ambas, y ver con cuál se realizarían menos eliminaciones… probemos step-forward: eliminaremos el índice 4:

intentando step-forward


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

*luego de eliminar el índice 4*


indice: 0   1   2   3   4   5   6    7   8 
Datos:  1   17  5   10  15  10  5    16  8 
Restas:  -16  12  -5  -5   5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

AAAJÁ!!!!! vieron lo que pasó? lo vieron?! cada vez que eliminas al iésimo número del vector de datos, el iésimo-1 número del vector de restas se suma con el número que tiene a su derecha :D

Ahora, parece obvio que no necesitaremos el vector de datos (de hecho, tampoco necesitaremos un vector de índices ni de signos, pero los dejaremos visibles, ya que ayudan a entender el problema). todo lo que necesitamos es un vector en el que almacenamos las restas de los números!

volvamos a intentar solucionarlo… luego de eliminar el índice 4, se resolvió el problema? parece que no: el problema no se va a solucionar, hasta que el signo del 3er elemento del vector de restas cambie a positivo… así que volvamos a eliminar al índice 4, y hagámoslo hasta que el 3er elemento en el vector de restas se vuelva positivo no olviden que solo hemos eliminado 1 item


indice: 0   1   2   3   4    5    6    7 
Datos:  1   17  5   10  10   5    16   8 
Restas:  -16  12  -5  0    5   -11   8
Signos:  (-)  (+) (-) (?) (+)  (-)   (+)

nope… hay que volver a eliminar el 4… ya llevamos 2 eliminados


indice: 0   1   2   3   4    5    6  
Datos:  1   17  5   10  5    16   8 
Restas:  -16  12  -5  5   -11   8
Signos:  (-)  (+) (-) (+) (-)  (+)

esto sí soluciona el problema! y hemos eliminado a 3 números

¿Qué habría pasado si hubieramos intentado step-backward?

intentando step-backward…

En este camino, intentamos eliminar al número índice 3…


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

luego de eliminar el índice 3…


indice: 0   1   2   4   4   5   6   7    8  
Datos:  1   17  5   13  15  10  5    16  8 
Restas:  -16  12  -8  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

esto no solucionó el problema… ¿Cuándo se solucionará el problema? cuando el número que está a la derecha del índice 3 del vector de las restas cambie de signo! así que vamos a repetir éste proceso, hasta que el 4to índice del vector de restas se vuelva positivo…

 

¿Qué problemas podrían surgir aquí? podría suceder que… de pronto, en una de las eliminaciones, el número del vector de restas que estamos analizando (el que está en negrillas en el código de arriba), cambie de signo, porque entonces, ya no sería congruente con el número anterior, y tendríamos que volver a analizar tooodo el vector. Pero esto no va a pasar porque, para que esto pase, es necesario que el número que está a la derecha de él tenga un signo diferente al número que estamos analizando, y cuando esto suceda, el problema se habrá solucionado, por lo que no sería necesario eliminarlo!

hasta ahora hemos eliminado 1 número

eliminamos el 4to…


indice: 0   1   2   4   4   5   6   7  
Datos:  1   17  5   15  10  5    16  8 
Restas:  -16  12  -10  5   5   -11   8
Signos:  (-)  (+) (-)  (+) (+) (-)  (+)

Esto soluciona el problema! hemos eliminado 2 números

Así que comparemos: qué solución es mejor en este caso?
STEP-BACKWARD: elimina 2 números.
STEP-FORWARD: elimina 3 números.

Creo que es mejor quedarnos con STEP-BACKWARD, ya que solo elimina 2 números.

Más adelante, nos queda un problema por resolver: dos signos + repetidos! creo que la lógica se ha entendido, así que, no lo resolveré paso por paso.

La Secuencia Zig-Zag más larga que se puede formar, es esta:


indice: 0   1   2    4   4   5    6  
Datos:  1   17  5    15  10  16   8 
Restas:  -16  12  -10  5   -6   8
Signos:  (-)  (+) (-)  (+) (-) (+)

y se forma luego de realizar 3 eliminaciones… su longitud es 7=10-3;

La Solución

“Pero dijiste que era una solución que funcionaba en O(n)!! yo solo veo una gran y obvia recurrencia…”

Con este razonamiento, se puede lograr una solución que funciona en O(n)… en serio! no es tan complicado como parece…

Ya que nos convencimos de que no necesitaremos el vector de los datos, transformaremos esto:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

en esto


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8

Como solo vamos a recorrer el vector una vez, imagina que este eres tú: ·u· y que estás en el primer elemento del vector:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·

Así que vas a recorrer el vector hasta que encuentres la primera incoherencia, así:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:           ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·

¡haz encontrado tu primera incoherencia! tienes dos opciones: step-forward o step-backward… así que te declaras dos variables: fw=0 (para step-forward) y bw=0 (para step-backward), también te creas otra variable llamada j… y las inicializas así:


bw+=restas[j-1]; fw+=restas[j]
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j

mientras vas incrementando j… ¿Hasta cuándo hay que repetirlo? hasta que j se salga del vector, o mientras bw tenga el mismo símbolo que restas[j+1] o mientras fw tenga el mismo símbolo que restas[·u·]

¿Por qué? porque bw indica cómo quedaría el número con índice 2 si decides tomar la solución step-backward, así que, en cuanto el número de la derecha (luego de sumarle ‘j’ números) cambie de signo, entonces el problema se habrá solucionado, y se asumirá que se han hecho ‘j – ·u·’ eliminaciones.

Mientras que fw indica cómo quedaría el número con índice 3 si decides tomar la solución step-forward… es casi la misma lógica…

si j se sale del rango, es porque hay que eliminar a todos los que están a partir de tu posición.


bw+=-5; fw+=-3;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j


bw+=-8; fw+=-5;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                        j

¡aquí se cumple una condición de salida!
bw es de diferente signo que restas[j+1], por lo tanto, la mejor solución, es backward, en la que se realizan 2 eliminaciones.

Añades las 2 eliminaciones al contador de eliminaciones, saltas hasta j, y continúas tu camino hasta volver a encontrar una incoherencia… si vuelves a encontrar una incoherencia, repites el proceso…


contador de eliminaciones: 2;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:                       ·u·

¡Eso es todo! ahora… a codificar! :D

Si se fijan con atención, con este algoritmo, únicamente es necesario recorrer una vez el vector de restas (que tiene una longitud de n-1), lo cual nos da una complejidad algoritmica de O(n-1) = O(n). Además, si al momento de la lectura de los datos, en vez de almacenarlos en un vector, se restan y estas restas se almacenan directamente en un vector, este algoritmo ocuparía un espacio de O(n).

Advertisements

Competitive Programming

“Given well-known Computer Science (CS) problems, solve them as quickliy as possible!”

Durante todo el 1er semestre (y de hecho, incluso ahora) estuve obsesionada con encontrar mi propia solución a muchos problemas de algoritmia, nunca busqué en internet la solución a ningún problema de programación (a excepción del problema de pasar de notación INFIX  a POSTFIX). Pero en estos últimos días me di cuenta de algo: no tiene sentido continuar así · n ·

Pero, antes de que muchos de mis amigos que aún persisten en la insesante lucha de encontrar sus propias soluciones saquen sus antorchas y quieran quemarme en una hoguera por hereje (Gustavo Callejas :D), permítanme explicar el fundamento de tan herética proposición:

Como desarrolladores, tenemos que ser rápidos, tenemos que encontrar la solución más apropiada para los problemas, pero, si cada vez que nos topamos con algún problema, pretendemos querer solucionarlo desde 0, no solo tardaremos mucho, sino que también, nuestra solución podría no ser la más adecuada.

Podremos ver nuevos horizontes, si y solo si, nos paramos sobre los hombros de los gigantes.

Hay que aceptar que, gran parte de los problemas de algoritmia, ya fueron solucionados por otros programadores brillantes, quienes a su vez, también utilizaron, entendieron y adaptaron, las soluciones de otros programadores brillantes.

¡Ya habrá tiempo para solucionar problemas de algoritmia sin solución! por ahora, es mejor entender todas las soluciones que ya han sido planteadas para poder proponer las nuestras en un futuro (espero, no muy lejano), y que estas soluciones que nosotros contribuyamos (en el futuro), ayuden a otros programadores novatos a solucionar problemas “solucionables” en los contests.

¿Pero… si esto fuera cierto, entonces la ACM-ICPC (y todos los contests de competitive programming) se reducen a copiar, pegar y ver quién typea más rápido? ¡no del todo!

Como desarrolladores, en los contests, tenemos que llevar a los límites nuestro conocimiento de algoritmos, identificando problemas, encajándolos en algoritmos conocidos… está de más decir que, para hacer esto, es necesario conocer muy bien las limitaciones y ventajas de cada uno de los algoritmos, así como su funcionamiento ~_^

Así que, con este post, quiero despedirme de mi orgullo (infundado)… de ahora en adelante, bucaré soluciones parciales!

(Migración de Tumblr a WordPress, fecha original: 2013-10-04)

Programación Dinámica (DP: Dynamic Programming)

La programación dinámica es un tanto confusa, y lo sé! en las últimas semanas, estuve interrogando a muchas personas: “Qué es la programación dinámica?” muchas de ellas respondían conceptos muy confusos, por lo que llegué a concluír (erróneamente) que la programación dinámica era una especie de magia mediante la cual los algoritmos se hacen mucho más eficaces y rápidos, y que todo mago capaz de invocar el conjuro de la programación dinámica de forma exitosa, sería capaz de resolver todos los problemas de algoritmia del mundo…. no… DEL UNIVERSO!

Pero luego de un tiempo, y luego de que Jhtan me explicara varias veces el concepto (btw, gracias ^_^) por fin entendí qué es la programación dinámica:

NO ES MAGIA de hecho, nada es magia… todo tiene su explicación ;)

La programación dinámica tampoco es una forma de solucionar todos los problemas del universo y traer la felicidad y la paz mundial, de hecho, la programación dinámica también tiene sus limitaciones (como cualquier otro paradigma de algoritmia) y no funciona para cualquier problema… como ven, nada es mágico, y, en todo el conocimiento que he coleccionado a lo largo de mi vida, podría asegurarles casi con certeza: nada es mágico, no hay una receta mágica que funcione para todo y garantice perfección, si hacer algoritmos fuera algo automatizable, entonces habrían algoritmos para hacer algoritmos, y por lo tanto, programas que programen programas.
(Pero eso ya es un tema diferente…)

Si la programación dinámica no es magia, y si tampoco es una receta mágica, entonces… ¿Qué es exactamente la programación dinámica? y ¿por qué debería un informático entenderla? Vamos por pasos…

¿Qué es?

La programación dinámica es un paradigma (entre muchos) para resolver problemas. Este paradigma consiste en: utilizar resultados parciales (que el programa ha calculado y guardado en algún lugar) para dar con el resultado requerido. Un ejemplo! (bastante escueto e inútil, pero que ayudará a entender el paradigma): imagina que aún estás en colegio, y tu profesora quiere jugar un juego: ella te dirá una palabra que empieza con “a” y tú tienes que buscarla en el diccionario y leerle su significado… si tus compañeros encuentran la palabra antes que tú, ella te castigará sin recreo (digamos que está loca, y la lleva contra tí, o algo así), por suerte, tú eres más avispado que tus compañeros, y, como sabes que la profesora preguntará una palabra que comience con la letra “a”, separas la sección del diccionario que contiene todas las palabras con la letra “a” y eso te da cierta ventaja.

En el ejemplo, la porción del diccionario que haz separado, constituye un conjunto de resultados parciales, y para encontrar el resultado, buscas entre los resultados parciales el resultado correcto. La programación dinámica se trata, básicamente, de eso: calcular resultados parciales, guardarlos, y luego usarlos (ya sea buscando entre ellos o realizando operaciones con ellos) para obtener el resultado deseado.

Viéndolo así, Gauss utilizó este paradigma para resolver el problema de 1 + 2 + 3 + … + n y simplificarlo en su, tan conocida fórmula n(n+1)/2 cuando aún era niño.

Cuenta la anécdota que, el maestro de aritmética de Gauss le planteó al salón el problema de sumar los primeros 100 números de forma consecutiva (1 + 2 + 3 + … + 100), pero Gauss se dio cuenta que  1+99 = 100 y que  2 + 98 = 100 y que r + ( 100 – r ) = 100 y por lo tanto r + (n – r) = n… y allí está de nuevo resultados parciales, Gauss encontró todos los resultados parciales, los guardó, y se dio cuenta que formaban un rectángulo, luego, se dio cuenta que el resultado deseado era uno de los triángulos contenido en el conjunto de resultados parciales, así que procesó todos estos resultados parciales para obtener el resultado deseado, y de allí viene su fórmula n(n+1)/2.

Ahora vamos a la siguiente pregunta…

¿por qué es importante?

Aunque la programación dinámica no es una receta mágica, es una de las muchas armas que todo informático debería saber empuñar. Hay una gran variedad de problemas que se pueden resolver con programación dinámica, uno de ellos es el de Longest Common Subsequence.

Y bueno, recién estoy entendiendo la programación dinámica y no tengo mucha experiencia en esto del competitive programming y por eso aún no entiendo del todo sus implicaciones…

Pero lo que sí puedo afirmarles con certeza es que, entender (al menos en parte) cómo funciona la programación dinámica, y ser capaz de identificar problemas que requieren de programación dinámica para su solución, me ha dado cierto aire de confianza, la sensación de que, todos los problemas a los que no les encuentro solución, TIENEN una solución, pero primero, necesito aprender una nueva forma de encararlos: de entenderlos.

Y por último, un consejo para entender la programación dinámica: el problema Maximum Sum, el sitio uHunt lo clasifica como un problema de nivel de dificultad 1 (bastante fácil) que se resuelve mediante programación dinámica. Es altamente recomendable resolverlo sin buscar ayuda, por eso, es mejor entenderlo resolviendo este algoritmo… será difícil al principio, pero a mí me funcionó. Solo intenten resolverlo mientras piensan una y otra vez “por qué necesito resultados parciales?” “cómo voy a usar resultados parciales para resolver este problema?”… esto me funcionó a mí… espero que también te funcione a tí ^ w ^

(Migración de Tumblr a WordPress, fecha original: 2013-08-01)