Tutorial USB_C1 Parte II

Hola a todos.

Supuestamente iba a terminar de escribir este tutorial la semana pasada, pero la verdad se me acumularon algunas cosas y tuve que postergarlo hasta ahora.

CPRMT:
El problema pide que imprimamos en orden lexicográfico las letras que hay en común entre ambos strings. Una solución sencilla puede ser la siguiente:

• Buscamos la letra 'a' en el primer string y vemos cuantas ocurrencias tiene (llamémosle Aa: ocurrencias de la letra 'a' en el string A) y luego vemos cuantas ocurrencias tiene en el segundo string (Ba).
• Ahora tenemos que imprimir cierta cantidad de aes, pero ¿cuántas aes tenemos que imprimir si tenemos 2 cantidades? Pues la respuesta es el mínimo de ellas, porque el resultado no puede tener mas aes que cualquiera de los strings, si no, la respuesta no sería un substring de los strings originales. Ahora, ¿por qué no imprimimos menos letras que el min(Aa, Ba)? Porque el resultado tiene que tener la máxima longitud posible y para ello tenemos que aprovechar todas las aes que podamos.
• Imprimimos min(Aa, Ba) aes.
• De manera análoga procedemos con las letras desde 'b' hasta la 'z'.

Ahora, ¿cómo se le ocurre calcular cuantas ocurrencias de a hay en uno de los dos strings? Puede hacer una función que recorra el string y calcule cuantas veces aparece un caracter en dicho string. Esa función tiene una complejidad de O(2 * 26 * N) [Para ambos string hay que calcular el número de ocurrencias de cada letra entre 'a' y 'z', donde recorrer el string es N, con N igual a su longitud] = O(N). Sin embargo, ¿puede pensar en una mejor manera de hacerlo, por ejemplo, en O(2 * N + 26) = O(N)?

OFFSIDE:
La solución del problema está dicha por el mismo problema:

An attacking player is offside if he is nearer to his opponent's goal line than the second last opponent

Entonces, lo único que tenemos que hacer es buscar el jugador del primer equipo que está más cerca de la línea de gol y comparar si está más cerca que el penúltimo jugador del segundo equipo.

Nota importante: la frase "penúltimo jugador del segundo equipo" puede resultar un poco confusa. Si ordenamos las posiciones del segundo equipo en orden no decreciente obteniendo un arreglo B[0..n), B[1] representa la posición del penúltimo jugador y no B[n - 2] como podrían pensar otros, ya que para el segundo equipo entre más cerca de la línea de goal se esté, significa que está más atrás con respecto a los demás.

SAMER08F:
Éste fué el tercer problema más resuelto de la competencia. Podemos subdividir el problema de la siguiente manera: si tenemos un cuadrado de N x N, entonces calculemos el número de cuadrados diferentes de tamaño 1 x 1, 2 x 2, 3 x 3, ..., N x N. Entonces, procedamos a calcular el número de cuadrados diferentes para cada tamaño.

• Para cuadrados de tamaño 1 x 1, tenemos que hay N x N cuadrados diferentes. Cada celda del cuadrado de tamaño N x N mide 1 x 1, y hay N x N celdas.
• Para cuadrados de tamaño 2 x 2, tenemos que hay (N - 1) x (N - 1) cuadrados diferentes. No podemos colocar un cuadrado de tamaño 2 x 2 en la última columna del cuadrado, ya que se excedería del tamaño del cuadrado. Igualmente no podemos colocar un cuadrado de tamaño 2 x 2 en la última fila. Entonces, para cada fila (que son N - 1, ya que la última no es válida) tenemos que podemos colocar cuadrados de tamaño 2 x 2 en todas las columnas, excepto la última.
• Para cuadrados de tamaño 3 x 3, tenemos que hay (N - 2) x (N - 2) cuadrados diferentes. Antes no podíamos colocar un cuadrado de tamaño 2 x 2 en la última fila, ahora como es de tamaño 3 x 3, no podemos colocarlo en la penúltima fila. Igualmente, no podemos colocar cuadrados de tamaño 3 x 3 en la penúltima columna.
• Generalizando, para un cuadrado de tamaño i x i, tenemos que hay (N - i + 1) x (N - i + 1) cuadrados diferentes. Por ejemplo para cuadrados de tamaño 2 x 2, tenemos que hay (N - 2 + 1) x (N - 2 + 1) = (N - 1) x (N - 1) cuadrados diferentes, lo cual encaja con nuestro análisis.

Por último, sumemos la cantidad de cuadrados diferentes que hay de tamaño i x i, con 1 <= i <= N.

Esta solución es de orden O(N), ya que para cada 1 <= i <= N, hay que hacer un pequeño cálculo (de orden constante). Ahora, ¿puede hacerlo mejor, tal vez en orden O(1)?

BYTESM2:
Un ejercicio sencillo que puede ser resuelto usando Programación Dinámica. Algunos indicativos de que el problema puede ser resuelto usando programación dinámica son: un problema se puede expresar en subproblemas que son del mismo tipo del problema; el subproblema no depende del problema padre, y hay casos que se repiten. Vamos a analizar esos indicativos uno por uno:

• El problema se puede expresar en subproblemas que son del mismo tipo del problema: supongamos que estamos en un punto de la primera fila y nos movemos a la segunda fila. Al movernos a otra fila no podemos regresar a la anterior, por lo tanto lo que era antes la segunda fila se vuelve técnicamente en nuestra nueva primera fila y tenemos el mismo problema que el anterior, encontrar el máximo desde esa primera fila hasta el final y sumarle el beneficio de la vieja primera fila.
• El subproblema no depende del problema padre: cuando llegamos a una posición determinada mediante una secuencia de movimientos, no nos importa como llegamos allí, ní lo que hay antes de nosotros, pues el subproblema tiene que calcular el mejor resultado desde su posición en adelante (gracias al punto anterior).
• Hay casos repetidos: digamos que AB = moverse hacia abajo, AD = moverse hacia abajo y después 1 paso a la derecha y AI = moverse hacia abajo y después 1 paso a la izquierda. Si estamos en la posición (1, 3) (1era fila y 3era columna) y tomamos la secuencia de pasos AB-AB llegaremos a la posición (3, 3). También podemos llegar a esa misma posición desde la posición (1, 3) usando las secuencias de paso AI-AD y AD-AI. Entonces estamos haciendo el cálculo desde la posición (3, 3) al menos 3 veces, en donde todos los resultados serán iguales, porque las celdas de la matriz se mantienen constantes.

Un pseudocódigo que resuelva el problema puede ser el siguiente:

# n = número de filas
# m = número de columnas
function dp(pos: posicion, tab: tablero, n, m: enteros) # dp = dynamic programming
    si (pos.fila > n) # n es el número de filas
        retornar 0 # Ya terminamos

    si (la posicion ha sido calculada anteriormente)
        retornar el valor correspondiente a esa posicion
    sino # Procedemos a calcular
        Calcular cuales de los movimientos (AI, AB, AD) son válidos
        De los movimientos válidos tomar el que provea mayor beneficio usando la función dp desde la nueva posición indicada por el movimiento
        retornar el mayor beneficio calculado en el paso anterior + el valor del tablero en la posición dada.

Para la función principal tenemos que calcular dp en todas las columnas de la primera fila e imprimir el mayor de todos los valores obtenidos

CANDN:
Éste fué el problema más difícil de la competencia. Hay 3 puntos de interés para el problema: el bar, la casa de Charly y la casa de Nito. Tenemos que obtener la distancia mínima que hay entre el bar y la casa de Charly, y la distancia mínima que hay entre el bar y la casa de Nito, pues ellos no están dispuestos a caminar más de esa distancia. Para obtener esa mínima distancia, podemos usar el Algoritmo de Dijkstra. Ahora, procedemos a resolver el problema de la siguiente manera:

Para cada nodo del grafo:
    Si la distancia que Charly y Nito han recorrido desde el bar hasta dicho nodo + la distancia que le falta a cada uno por correr sigue siendo aceptable para cada uno (recuerde que ellos están dispuestos a recorrer la distancia mínima del bar a su casa) "tomamos en cuenta" ese nodo.
De todos los nodos que "tomamos en cuenta" tomamos aquel donde Charly y Nito han recorrido la mayor distancia juntos.

Al ver la información anterior, nos damos cuenta que aún nos faltan datos adicionales, que son: la distancia da la casa de Nito a cada uno de los nodos y la distancia de la casa de Charly a cada uno de los nodos. Para cada nodo tenemos que saber cuanto le falta a Charly y a Nito por recorrer para llegar a sus respectivos hogares desde ese punto (podemos calcular las distancias desde la casa de cada uno a todos los nodos, y dado que el grafo es no dirigido, podemos decir que la distancia de la casa de X a un nodo Y es igual a la distancia del nodo Y a la casa de X). En resumen, tenemos que hacer uso del algoritmo de Dijkstra sólo 3 veces: para calcular la distancia del bar a todos los nodos, para calcular la distancia de la casa de Charly a cada uno de los nodos y para calcular la distancia de la casa de Nito a cada uno de los nodos. Y por último, usar el procedimiento dicho anteriormente, para resolver el problema.

Con esto termina el tutorial del primer calentamiento para el maratón local de la USB. Espero les haya gustado :-).

Saludos

Bienvenidos a mi Blog

Hola a todos,

Bienvenidos a mi Blog. Esta primera entrada es para introducirme ante ustedes y para hablar algunos aspectos de mi Blog.

Antes que todo, soy David Gómez estudiante del 5to año de Ingeniería de la Computación en la Universidad Simón Bolívar. Antes de entrar a la universidad no estaba completamente seguro de que carrera iba a estudiar. Había obtenido el cupo en Ingeniería Mecánica en la UCV y el cupo en Ingeniería de la Computación en la USB y comencé a ver ventajas y desventajas de cada una hasta que me decidí por Ingeniería en Computación en la USB. Pude haber hecho admisión para Licenciatura en Computación en la UCV, pero prefería obtener el título de Ingeniero, supongo que porque suena mejor a mi parecer jejejeje. Y en el 2006 comenzaron mis estudios en la USB, primero tuve que hacer 1 año de ciclo básico antes de comenzar a saber de que se trataba mi carrera (así es, cuando ingresé no tenía ni idea de que era Ingeniería de la Computación). En septiembre del 2007 comenzó mi primer año de carrera, estaba viendo materias como Lógica Simbólica y Algoritmos y Estructuras I y su respectivo Laboratorio y tengo que admitir que esas materias me gustaron bastante. En diciembre del mismo año una amiga me dijo que el próximo trimestre iba a ver Computación I que se dicta en lenguaje C así que decidí aprender C. Comencé a hacer algunos ejercicios viejos que tenía de Algoritmos y Estructuras I en C y así fuí aprendiendo un poco más. Recuerdo que a veces le pedía ayuda a Saúl Hidalgo o le pedía que me corrigiera algunos programas. Creo que se cansó de hacer eso (xD) y me recomendó un sitio llamado UVa. Comencé a hacer algunos problemas allí y fué desde ese momento que comenzó mi pasión por la programación. Claro, los ejercicios que hacía eran extremadamente fáciles, pues a esa altura sólo tenía idea de un for, un if y lo más avanzado que sabía era backtracking porque Carlos Colmenares me lo explicó en una de las primeras clases de Algoritmos y Estructuras II.

No pasó mucho tiempo sin que me enterara de la existencia de algo llamado Maratones de Programación. Carlos Colmenares me había motivado a ir a un maratón de programación que se iba a celebrar pronto (en Febrero del 2008) llamado Connect II de Smartmatic. Después de discutir con él y decirle que "iba a llevar yuca" decidí ir a competir. Primero iba a competir con Saúl Hidalgo, pero no recuerdo claramente que fué lo que pasó y me cambiaron de compañero (creo que se llamaba Sergio). Y así comenzó mi primer maratón de programación... efectivamente "llevamos yuca" (xD), sólo logramos hacer 1 ejercicio y obtuvimos la posición 32 de 60 (esos números pueden variar de acuerdo a mi memoria). Un completo desastre. Sin embargo, decidí que iba a comenzar a practicar más, a mejorar mis habilidades y a competir en eventos siguientes. Desde ese entonces compito en diversos maratones de la ACM-ICPC, de Smarmatic, maratones online de TopCoder, Codeforces, Google, etc. Irónicamente no programé mas en UVa (creo que su nivel ha decaído un poco), pero me trasladé a otra página llamada SPOJ (puede ver mi username aquí: http://www.spoj.pl/users/david70/).

Ahora voy a otro punto de la entrada: aspectos del Blog.

• El origen del nombre pepedebugging. ¿Por qué ese nombre? Bueno, una de mis prácticas de programación cuando no uso un debugger y quiero ver el flujo del programa es comenzar a escribir líneas de código al estilo puts("pepe"), puts("por aqui pase"), printf("pepe%\n", variable_pepe). Y ése es todo el origen del nombre.
• El actual título del Blog "Porque programar no es sólo presionar teclas". Porque creo que hay muchos factores que se ven envueltos a la hora de crear un programa o la solución a un problema. A veces somos ambiciosos y no nos conformamos con una solución, sino que buscamos de mejorarla (en diferentes aspectos que mencionaré luego).
• Fuese bien sencillo si el resultado de los problemas de programación que se nos presentan en la vida consistiesen de colocar unos if por acá, un for por allá, una funcioncita por allá o escribir la solución más obvia posible. Hay muchos factores que se ven envueltos en obtener un "buen resultado". Entre ellos se encuentran: la complejidad en tiempo, la complejidad en memoria, la legibilidad del código, su mantenibilidad, su portabilidad, escoger el lenguaje que más se adapte al problema, etc. Por ejemplo: imagine que buscar una palabra de 10 caracteres en un libro de 10^8 caracteres tome 10 segundos en vez de 1 segundo porque decidió implementar una búsqueda en O(N * M) en vez de implementar KMP o BM; sería bastante tedioso esperar 10 segundos por cada búsqueda cuando se sabe que se podría obtener en menos. Es por eso que trataré de hablar de aspectos como esos.
• Estaré mencionando algunas herramientas de interés que puedan facilitar o hacer el trabajo de programar. Por ejemplo: CakePHP, el cual me parece un muy buen framework de desarrollo en PHP.
• Tengo que admitir que no soy muy amante de las "nuevas tecnologías". No creo que vean en el Blog cosas como "Google se une con Aguas Minalba, ahora podrá adquirir agua potable en cualquier parte del mundo gratis al usar la característica Google Water que fué incorporada a GMail". Pero uno nunca sabe.
• Hablaré de algunos temas que me son de curiosidad (no necesariamente de computación).
• Acerca de los comentarios: siéntase libre de comentar cualquier error (así sea ortográfico) o hacer cualquier sugerencia en el Blog siempre y cuando no sea ofensiva, incoherente o contenga cosas como "io kReOzzz ke..." (simplemente odio comentarios con presencia de "io", exceso de "z" o intercambios sin sentido entre minúsculas o mayúsculas).

Y bueno, eso es todo para mi primera entrada en el Blog. Entonces, Bienvenidos a mi Blog.