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

Tutorial USB_C1 Parte I

Hola a todos,

Llevaba tiempo sin escribir en el blog gracias al comienzo de clases. Hoy quiero escribir un tutorial acerca de los problemas usados en el maratón USB10_C1 (el primer calentamiento para los maratones ACM-ICPC 2010 de la Universidad Simón Bolívar) el cual fué llevado a cabo en SPOJ.

TEST:
Éste fué el problema más sencillo del maratón, fué resuelto por todas las personas que participaron en el concurso.

La solución es muy simple, sólo hay que leer enteros hasta que aparezca el número 42 en la entrada.

Aquí les coloco una solución en C++ del problema:

# include <iostream>
using namespace std;

int main()
{
    int n;

    while(cin >> n && n != 42) {
        cout << n << endl;
    }

    return 0;
}

ADDREV:
Éste es otro problema que fué resuelto por todas las personas que participaron en el maratón. Sin embargo, es un poco más difícil que TEST ya que requiere de más implementación. Aquí les dejo la solución del problema, sin embargo, no colocaré código para que puedan practicar haciéndolo :-).

Leer cada par de enteros.
Revertir cada uno.
Sumarlos usando, por ejemplo, el método de adición que aprendimos en primaria.
Revertir el resultado.
Eliminar los 0s al principio del resultado.

Tenga en mente algunos casos especiales que pueden surgir en los pasos dichos anteriormente, como los siguientes:
1.- Se acabaron los dígitos de un número y hay un acarreo de una operación pasada.

2.- Al eliminar los 0s del resultado tenga en mente que tiene que quedar un dígitos al menos.

Nota: Los ejemplos no son ejemplos de lo que recibirá el programa y lo que debería arrojar, son sólo ejemplos para mostrar algunos casos intermedios.

CISTFILL:
Este problema ya no resulta ser tan fácil como los anteriores. La solución a este problema puede ser obtenida usando Búsqueda, ahora veamos que tipo de búsqueda hay que realizar. Tenemos que buscar una altura a la cual se puedan llenar las cisternas con cierta cantidad de líquido. Lo primero que se nos puede ocurrir es buscar sobre todas las alturas posibles, pero veamos cuantas alturas tenemos que verificar. El punto más alto de una cisterna es su altura base + su propia altura, y si vemos las restricciones tenemos que la altura base puede ser a lo sumo 10^6 y que su propia altura puede ser 40000 (se dice que 1 <= h*w*d <= 40000, si w = d = 1 entonces 1 <= h <= 40000), es decir, que en total la máxima altura que se puede alcanzar es 1040000, pero también tenemos que tener dos dígitos de precisión, por lo que para cada altura tenemos que revisar 100 números más (desde *,00 hasta *,99), lo cual hace un total de 104000000 alturas y eso es aproximadamente 10^8 alturas. Anteriormente hablamos de revisar alturas, ¿a qué me refieron con ello? Me refiero con ello a que tenemos que ver que volumen de líquido hay en las cisternas a cierta altura, es decir, que para cierta altura tenemos que ver cuales cisternas no están por encima de esa altura y calcular el volumen de líquido que hay en cada una de ellas y sumarlas para obtener la cantidad total de líquido en el sistema; a esta última operación la llamaremos f (altura, cisternas). Ahora, por cada altura (aproximadamente 10^8) tenemos que revisar todas las cisternas (1 <= n <= 50000) para ver cuáles no están por encima de dicha altura. Esas son muchísimas operaciones que tenemos que hacer. Por lo tanto, si escogemos realizar búsqueda lineal seguramente obtendremos Time Limit Exceeded.

Hasta ahora nuestros esfuerzos se han vistos frustrados, pero, si observan detalladamente la función f (altura, cisternas) pueden ver que la función es monótona no decreciente, es decir, f (altura1, cisternas) <= f (altura2, cisternas) con altura1 <= altura2. Eso ocurre porque en altura2 tenemos las cisternas de altura1 más las que aparezcan desde altura1 hasta altura2 (que pueden ser ninguna), por lo tanto, tendremos al menos la misma cantidad de volumen de líquido que en altura1. Pero, ¿qué hago con saber que la función es no decreciente? Pues elemental mi querido Watson, usar búsqueda binaria con respecto a la altura.

function f(altura, cisternas)
    Retorna el volumen de agua en las cisternas a esa altura

funcion busquedaBinaria(volumen, cisternas)
    ini <- 0
    fin <- 1040001 # Máximo de alturas que tenemos que revisar + 1

    Mientras ini + 1 != fin # Mientras haya un intervalo [a, b) válido
        med <- (ini + fin) / 2 # Los cálculos se hacen con reales porque la altura tiene que tener dos dígitos decimales.
        si f(med) > volumen # El volumen excede lo que buscamos, tenemos que bajar la altura
            fin <- med
        sino # Tenemos que subir la altura
            ini <- med

    retornar ini

Ahora este algoritmo tiene complejidad O(N * lg (104000001)) con N el número de cisternas, el cual es suficiente para obtener un accepted en el problema. Ah ya se me olvidaba, para revisar si hay un overflow, solo calculen la cantidad total de líquido que pueden contener todas las cisternas y revisen si es mayor a la cantidad dada.

ACT:
Este problema me trajo sorpresas en el maratón, pues pensé que más gente lo resolvería. Algunas personas intentaron simular el problema, lo cual no está mal, pero toma un poco de tiempo. Sin embargo, hay observaciones muy interesantes acerca de este problema:

• La secuencia de caracteres representa un juego válido, es decir, un juego completo con un ganador o dicho de otra manera, lo contrario a un juego que no ha terminado o un juego que fué continuado a pesar de tener un ganador.
• Un jugador que anota un punto puede ganar un game, un set o un match, de acuerdo a sus cantidades de games y sets acumulados, es decir, que cada vez que un jugador anota un punto hay que verificar si ganó un game, set o match.

De acuerdo a los puntos anteriormente mencionados, ¿tenemos que simular el juego? La respuesta es no, cuando una persona anota un punto quiere decir que es candidato para ganar un match (punto 2) y si no hay más puntos a continuación quiere decir que esa persona efectivamente ganó un match y por lo tanto es la ganadora del juego (punto 1).

# include <iostream>
# include <string>
using namespace std;

int main()
{
    int t, n;
    string juego;

    cin >> t;
    while(t--) {
        cin >> n >> juego;
        cout << *(juego.end() - 1) << endl; // o juego[juego.size() - 1], como les parezca mejor.
    }

    return 0;
}

Recuerde que juegos.end() devuelve un apuntador al final de la cadena (a la derecha del último caracter). Al escribir juegos.end() - 1, obtenemos un apuntador al último caracter de la cadena, y usando *(juegos.end() - 1) podemos leer el caracter al cual se estaba apuntando.

TOANDFRO:
Éste fué otro problema fácil del maratón, pues había que hacer exactamente lo que se decía en el enunciado. Se recibía una cadena y el número de columnas que se iban a utilizar. Se comienza a transcribir la cadena en una matriz de c columnas (con c dado en la entrada). Se comienza en la fila 0 de la matriz y se procede de la siguiente manera hasta que no hayan mas caracteres por analizar: si la fila es par se copian los siguientes c caracteres de la cadena de izquierda a derecha, si la fila es impar se copian de derecha a izquierda, luego vamos a la siguiente fila.

Aquí coloco el enlace a la siguiente parte del tutorial: Tutorial USB_C1 Parte II

Saludos a todos.

Selecciona tu armamento

Mi primer post no introductorio iba a ser acerca de la última competencia online de Codeforces (Codeforces Beta Round #27). Tenía pensado hacer un tutorial de los problemas ya que algunos de estos tenían cosas interesantes que quería resaltarles. Iba a dar una introducción a Codeforces y me dí cuenta de que iba a tener que hacer una introducción a cada online judge a medida que los vaya nombrando en el Blog. Entonces decidí usar esta entrada para mencionar varios online judges de interés y para darle puntos de inicio a la gente que se quiera introducir en el mundo de los maratones de programación.

Primer equipamiento: El lenguaje de programación. Entre más conocimiento se tenga de un lenguaje mejor y entre más lenguajes se conozcan mucho mejor. No recomiendo comenzar a aprender muchos lenguajes al mismo tiempo, ya que la salud mental de cualquiera se puede volver muy frágil con el exceso de información. Entonces escoja un lenguaje y comience a aprender del mismo, cuando ya se pueda desenvolver con él puede decidir entre aprender otro lenguaje o seguir aprendiendo del mismo lenguaje. Los primeros lenguajes que recomiendo aprender son C++ o Java. Nombro estos dos porque para las competencias de la ACM-ICPC generalmente se usan C/C++/Java; no menciono C porque C++ es C pero con más herramientas. También puede escoger otros lenguajes como Python, Perl, Ruby, Haskell, Prolog, Pascal, etc. Donde cada uno tiene sus ventajas y sus desventajas. A lo largo de su aprendizaje podrá ir determinando cuál lenguaje le conviene más para resolver un problema.

Para aprender C++ (mi lenguaje por default) recomiendo esta página, que a mí me ha servido de mucho:
http://www.cplusplus.com/reference/

Después de que escoja su lenguaje, comience a aprender y a practicar. Recomiendo aprender un nuevo tema y practicarlo hasta que sienta que tiene dominio sobre el mismo. Para aprender recomiendo las siguientes referencias:

• El famoso Cormen: Introduction to Algorithms. Es un excelente libro con gran variedad de temas para aprender.
• Art of Programming Contests. Otro buen libro para comenzar a aprender.
• TopCoder Tutorials. Éstos tutoriales me han parecido excelentes para aprender muchos temas que tal vez no encuentre en las lecturas mencionadas anteriormente.
• Manuscritos de Edsger W. Dijkstra. Algunos problemas puntuales resueltos por Dijkstra. Realmente no he leído muchos, pero los que leí me encantaron. Una buena práctica podría ser leer un problema, tratar de encontrar una solución y luego leer (y muy importante: entender) la solución propuesta por Dijkstra. Los artículos que leí contienen una muy buena explicación acerca de la solución del problema y una demostración formal de la solución, así que son buenos para expandir la mente.
• Algorithm problems for dummies: Petr Mitrichev's blog. El Blog de uno de los mejores programadores de todo el mundo: Petr Mitrichev. Precaución: el Blog es un tanto profundo jejeje.
• Mi Blog. Espero que algún día sirva de referencia para varios programadores alrededor del mundo. Por supuesto, tendria que empezar a traducirlo a inglés al menos =P.

 Para practicar recomiendo las siguientes páginas:

• SPOJ. Mi online judge preferido =P. Me gusta mucho por la gran variedad de lenguajes, los problemas tienen diferente dificultad por lo tanto diferente valor, algo llamado "Ignore extra whitespaces" (los que sufran de varios Wrong Answer o Presentation Errors en páginas como UVa a causa de cosas como un espacio en blanco de más o la última línea no termina en '\n' sabrán que ésto es la gloria =P). Además soy problemsetter acá, así que espero que vean algunos problemas que he publicado o publicaré allá =D.
• UVa. Detesto la navegabilidad de esta página -.-', esa es una de las razones por las que he dejado de programar allí. Pero bueno aquí les dejo unos truquitos para esta página: traten de acceder a ella usando Google Chrome; cuando vayan a las últimas 50 submissions y le den click a un problema o usuario le aparecerá un mensaje diciendo algo tipo "You are not authorised to view this resource." borren el "com_" que se encuentra luego de la variable option del url y podrán acceder al recurso sin problemas =P.
• SPOJ Brasil. Otra "sucursal" de SPOJ con diferentes problemas y además en portugués.
• CodeChef. Online judge de la gente de India.
• TopCoder. Un judge un tanto diferente ya que tiene que bajar una arena en Java y resolver los problemas en el applet. Luego me tomaré la libertad de hablar de TopCoder ya que a mi parecer requiere una entrada completa =P.
• Codeforces. Judge de la gente de Rusia (creo que de la gente de Saratov).
• USACO. Un buen lugar para comenzar porque vas resolviendo problemas a medida que te encuentras con puntos teóricos.
• Facebook's puzzles. Unos problemitas de Facebook =P. El método de sumisión es un tanto diferente ya que tiene que mandar el programa por email a una dirección, con un archivo en cierto formato, etc. No me parece muy interesante, pero si algo que vale la pena mencionar.
• 2000's ACM-ICPC Live. Ésta generalmente la uso para hacer los problemas de suramericanos pasados.
• Project Euler. Un sitio con unos cuantos problemas interesantes para poner a trabajar la mente ;-).

Recomiendo por comenzar en USACO y SPOJ (haciendo algo de publicidad ;-) ) y leyendo material como el Cormen y Art of Programming Contests.

Después de aprender un lenguaje y haber practicado un poco puede seguir practicando en maratones de programación =P. Algunos de ellos son:

• ACM-ICPC. Se dividen en maratones locales por universidad, luego en maratones regionales (como el suramericano) y luego en maratones mundiales (ACM-ICPC World Finals).
• Google Code Jam. Una competencia organizada por Google donde compiten miles de personas.
• TopCoder Open. Competencia organizada por TopCoder donde al igual que el Google Code Jam, compite muchísima gente.
• IOI. Una competencia para gente de colegios o estudiantes de los primeros años de la universidad. La verdad, no tengo muy claro como es esta competencia, pero se las dejo aquí por si quieren investigar un poco.
• Connect de Smartmatic. Son competencias realizadas por la compañía Smartmatic aquí en Venezuela. Muy buenas competencias, a lo mejor porque tienen recompensa monetaria (aunque no mal interpreten, no compito en maratones por premios en físico, aunque son un incentivo xD) o porque son onsite y puedes conocer a más gente de Venezuela metida en el mundo de los maratones. Además de que tienen promotoras muy bonitas allí xD.

Para los eventos mencionados anteriormente, trataré de mantenerlos al tanto de las fechas y de información relevante acerca de los mismos.

Ya el próximo post comenzaré con materia de los maratones =P. Recuerden que su opinión es bienvenida acá y si quieren proponer temas de interés pues vengan.

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.