Vine, Vi, Vencí

En mi opinión, los maratones de programación son experiencias enriquecedoras e incluso divertidas. Sin embargo, cuando empezamos a competir, nos damos cuenta de que la gran mayoría de los problemas propuestos en la competencia necesitan de teoría y herramientas que aún no conocemos o manejamos completamente. Cuando esto pasa, es natural que nos desmotivemos un poco y sintamos que no estamos a la altura de la competencia. Sin embargo, realmente no es momento de desanimarse. Hasta los mejores competidores del mundo alguna vez supieron tanto y hasta menos que nosotros. ¿Y como llegaron a ser los mejores? Con mucha práctica, mucha ayuda pero sobre todo, con continua pasión, dedicación y perseverancia.

Ahora, las primeras preguntas que uno podría hacerse son: ¿Cómo puedo aprender? ¿Qué cosas debo practicar? ¿Quién me puede enseñar? Como en toda competencia orientada al ejercicio intelectual, la participación en los maratones de programación necesitan de un balance entre la teoría y la práctica, así como de la comprensión de la estrecha conexión que ambas partes comparten. La práctica nos dará formas de expresarnos (lenguajes, librerías y hasta patrones eficientes de diseño) y nos dará velocidad a la hora de pensar, comprender, plantear, codificar y finalmente resolver los problemas que nos propongamos. La teoría nos dará visión, nuevas formas de atacar los problemas, maneras eficientes de lograr los resultados, capacidad para reconocer problemas similares y plantear su solución en base a problemas o estrategias que ya conozcamos.

Lo que quisiera mencionarles ahora es algunos sitios en la Web donde pueden adquirir conocimientos y luego ponerlos en práctica resolviendo problemas interesantes. Empiezo con algunos sitios donde es posible ejercitar la parte teórica:

• Los tutoriales de Topcoder: Esta pequeña colección de tutoriales sobre algoritmia son de gran ayuda, tanto para principiantes como para competidores intermedios y avanzados. Plantean de una forma amena, muchas de las estrategias de programación que un competidor debe conocer, así como código que implementa dichas estrategias y ejemplos concretos con problemas en donde las mismas deban aplicarse para lograr resolverlos. Muchos de estos tutoriales incluyen también una lista de problemas relacionados en los que se puede poner en práctica lo aprendido, separados por nivel de dificultad. En lo personal, me fueron de gran ayuda los tutoriales de Geometría y de Maximum Flow (una clase de problemas sobre grafos).



• Wolfram Mathworld: Este sitio está dedicado enteramente a las matemáticas. No provee de tutoriales concretos sobre los maratones de programación, pero si plantea soluciones a problemas matemáticos que pueden encontrarse escondidos en el enunciado de problemas de programación. Para entrenarse en un área particular que está presente en los maratones, conocida como "Teoría de Números", esta es posiblemente la página más adecuada y completa. Además, como parte del proyecto del creador de esta página, se encuentra el motor de conocimiento Wolfram Alpha, el cual permite resolver ecuaciones y dar respuesta a toda clase de preguntas (no solo matemáticas). Es interesante pasarse por ese sitio solo para observar el inmenso potencial que posee para resolver toda clase de dudas.

Existen también muchos libros de texto que pueden ayudar a comprender algunos conceptos teóricos relacionados a los maratones de programación, como el "Introduction to Algorithms" de Thomas Cormen, o el "Fundamentals of Algorithmics" de Gilles Brassard. Sin embargo, por su naturaleza puramente teórica, a veces pueden ser un poco tediosos de leer y dificiles para encontrar su relación con problemas de programación concretos. Otro libro ampliamente utilizado, que es interesante leer, es el "Art Of Programming Contest" de Miguel Revilla y Steven Skiena. Éste plantea una buena relación entre teoría y práctica, con secciones teorícas, ejercicios de ejemplo y otros más de tarea incorporados. La soluciones a los problemas en este libro pueden ser enviadas al sitio "Programming Challenges", para ser juzgadas como correctas o incorrectas.

Ahora, por la parte práctica, existen muchísimos jueces online que permiten que uno resuelva un problema, se los envíe y se juzgue automáticamente de forma que sepamos si nuestra solución era correcta o no. A continuación les menciono algunos de los que más he usado:

• SPOJ (SPhere Online Judge): Por mucho el juez online en el que más he practicado. La interfaz y la navegabilidad del sitio hacen sencillo mandar problemas y esperar el veredicto del juez virtual. Otorga la posibilidad de resolver los problemas en una amplia variedad de lenguajes, con una gran base de problemas disponibles para escoger. La puntuación de cada problema depende de la cantidad de personas que lo ha resuelto, por lo que los problemas difíciles posiblemente valdrán más que los problemas fáciles. Ahora, si lo queremos para practicar para los maratones ACM-ICPC, debemos concentrarnos en practicar exclusivamente en C/C++ o Java. Una gran desventaja de SPOJ es que a veces los tiempos límites para los problemas suelen estar muy apretados, ocasionando que la misma solución sea incorrecta (demasiado lenta) en Java y aceptada en C/C++. Esto lo hace injusto con aquellas personas que quieran practicar en Java, afortunadamente es una dificultad que solo ocurre con algunos de los problemas.



• TopCoder: Más que un juez virtual, es un portal completo dedicado al desarrollo de aplicaciones y la comunicación entre programadores del mundo. Tiene muchos tipos de competencia distintas, en donde los mejores programadores de distintas áreas de la programación, el diseño gráfico y la ingeniería de software pueden competir entre sí y medirse ante el resto del mundo (posiblemente incluyendo premios monetarios). La competencia más relacionada a los maratones de programación es la que ellos llaman "Algorithm Competition" (Los "Marathon Match" son otro tipo de competencias, interesantes, pero completamente distintas). Lo mejor de este portal es que toda la codificación puede hacerse desde un applet que ellos llaman "Arena" que incluye los compiladores para los lenguajes que ellos soportan y facilidades para probar el código de forma sencilla. El formato de los problemas es bastante distinto ya que no se debe leer ni escribir nada, ni a un archivo, ni a la entrada/salida estándar. Más bien lo que se pide es que se implemente únicamente una función que, dado ciertos argumentos, devuelva la solución al problema planteado. TopCoder organiza competencias aproximadamente cada dos semanas, sin embargo todas las competencias pasadas pueden ser vistas y resueltas en los salones de práctica.



• UVA (Universidad de VAlladolid): Es un juez virtual, parecido a SPOJ. Sin embargo es en realidad uno de los primeros y con mayor cantidad de problemas disponibles. Muchos de los mejores competidores del mundo han practicado con este juez virtual que incluye problemas de todas las categorías. Su más grande desventaja sin embargo es la navegabilidad, lo que la hace muy difícil de usar. Además de esto, lenguajes como Java cuentan con compiladores que no están lo suficientemente actualizados (situación que han enmendado mucho últimamente). Una ventaja, por otra parte, es que los tiempos límites están mucho mejor planteados que en SPOJ, resultando en un juicio justo sin importar el lenguaje escogido.

Existen muchos otros jueces online como USACO, Codeforces, etc. Sin embargo, no he tenido el suficiente contacto con ellos como para mencionarles de que se trata cada uno. Queda de su parte investigarlos y aprovecharlos de ser de su agrado.

Ya entonces solo queda practicar y aprender bastante, dedicarse a ser cada vez mejor, participar de la mejor forma en las competencias, pero sobre todo disfrutar cada momento. ¡Muchas gracias por leer! Cualquier comentario o sugerencia es más que bienvenido. En un futuro post hablaré de las competencias en las que se puede participar, más allá de los ACM-ICPC. Hasta una próxima vez.

¡Escoge bien tu arma!

¡Bienvenidos programadores! A mi me sucedió, y posiblemente a muchos otros también, que cuando comencé a interesarme en los maratones de programación lo único que quería era continuar resolviendo más y más problemas. En busca de seguir mejorando, investigamos nuevos y mejores algoritmos, nuevas y mejores estructuras de datos. Sin embargo, a veces estamos seguros de la solución de un problema, pero no tenemos idea de como implementarla en nuestro lenguaje de programación favorito. Incluso, a veces lo logramos pero nos damos cuenta de que tardamos demasiado en terminarlo y realmente no aprendimos demasiado al hacerlo. Puede incluso ocurrir también que el programa que resultó no sea lo suficientemente rápido para ejecutarse bajo el tiempo límite del problema.

Sucede que el primer paso y uno de los más importantes a la hora de empezar a programar soluciones a estos problemas, es el de escoger el lenguaje con el cual se piensa implementarlo. Y no solo para los maratones de programación, sino para cualquier aplicación que se desee realizar. Lo primero que se debe hacer es planificar que lenguajes de programación y herramientas conviene utilizar. Esto, ya sea para que sea más fácil de implementar, se ejecute velozmente, sea portable, mantenible o cualquier otra característica que se considere importante.

Muchas personas que tienen un tiempo compitiendo en los maratones de programación recomendarían que uno escogiera el lenguaje con el que uno se siente más cómodo (algunos incluso parecerán decirte, que si no escoges C++ no estás en nada, jajaja). Aprender todos los detalles de ese lenguaje, sus librerías, la manera rápida de manejar la entrada/salida, etc. Yo sin embargo, creo que es más importante estudiar TODOS los lenguajes disponibles y analizar cuales son sus fortalezas y debilidades. Así, podré decidir cual lenguaje me conviene más utilizar dado un problema específico.

Ahora, no digo que uno no tenga un lenguaje insignia, aquel que nos se más cómodo. Es importante conocer al detalle este lenguaje y hacer especial énfasis en estudiarlo. Sin embargo, se debería dedicar también un poco de estudios a los demás lenguajes de programación disponibles, pudiendo decidir entonces cuando nuestro lenguaje insignia es idóneo y cuando es vulnerable. Los maratones de programación por lo general son en equipos de 2 a 3 personas, por lo que una buena estrategia es intentar lograr que los lenguajes de programación insignia de cada integrante sean distintos. Así, cada uno conoce un poco más de su propio lenguaje, sin embargo con la visión de poder decidir que un problema es más adecuado para que lo resuelva su compañero. Este tipo de estrategias lleva mucho entrenamiento, quizá incluso más que la resolución misma de los problemas por uno mismo.

Hay muchos lenguajes de programación disponibles, diseñados bajo distintos conceptos e ideales en diferentes áreas. Sin embargo, hablaré un poco sobre los lenguajes de programación ofrecidos en los maratones de programación ACM-ICPC. Estos son: C/C++ y Java. Siendo C un subconjunto de C++, es claro que la elección real es entre C++ y Java. Si bien ambos lenguajes tienen muchas similitudes, diseñados bajo el mismo esquema de orientación a objetos, la verdad es que tienen diferencias notables que pueden ser aprovechadas a la hora de programar la solución a un problema.



Comienzo por mi propio lenguaje insignia para los maratones: Java. Este lenguaje es poderoso y a la vez elegante. Es verdad que pide que se escriba más, pero a cambio es consistente en la mayoría de sus definiciones. ¿Su gran desventaja? Es muy lento y consume mucha memoria. Por lo tanto, para problemas que requieren mucha manipulación de datos y un bajo nivel de abstracción de los mismos (Como los problemas de programación dinámica, de los cuales se hablará un post futuro), Java no es la mejor elección. La memoria y el espacio de pila se ven seriamente afectados por el hecho de ejecutarse bajo una máquina virtual. ¿Y entonces para que problemas es ideal? Principalmente para aquellos en los que la abstracción de los datos sea vital (Como algunos problemas de grafos) o los problemas geométricos.

Por ejemplo, en el paquete "java.awt" pueden encontrarse muchísimas clases útiles que resuelven problemas geométricos típicos de los maratones. Por ejemplo, en la clase "java.awt.Polygon" hay funciones para determinar si un punto dado está dentro de un polígono o incluso un rectángulo completo, puede calcular el "bounding box" para el polígono y hasta saber si el polígono intersecta con un rectángulo dado. Si bien es posible y quizá no tan difícil implementar estas funciones, es en verdad muy útil no tener que hacerlo durante una competencia. Siendo parte del API se puede asegurar que estas funciones están correctas e implementadas eficientemente.



Ahora, el otro lenguaje disponible para resolver los problemas: C++. Es el lenguaje insignia para la mayoría de los programadores al resolver problemas. ¿Cual es la razón? Es extremadamente eficiente y rápido para codificar. A cambio de perder cierta consistencia en sus definiciones, C++ permite programar de forma muy eficiente, incluso aplicaciones que usen abstracción de datos. En la mayoría de los casos, se utiliza el Standard Template Library (STL). Al ser compilado directamente a la máquina puede hacer un mejor manejo de la memoria y los demás recursos disponibles. ¿Para que tipo de problemas no sirve entonces? Por ejemplo, para aquellos en los que se deba hacer manipulación fuerte de cadenas de caracteres (cosa que se puede mejorar un poco usando stringstreams) o problemas donde hace falta precisión arbitraria de números. A diferencia de Java, que provee las clases "java.math.BigInteger" y "java.math.BigDecimal", en C++ se deben implementar estas funcionalidades manualmente cada vez que desee hacerse este tipo de cálculos. ¿Y para que problemas si es ideal? Principalemente para aquellos en donde contar con la mayor cantidad de memoria posible y una rápida ejecución es vital, como la programación dinámica. Así también para los programas cortos que no necesitan de muchas estructuras de datos, pues es mucho más rápido de codificar.

En conclusión C++ y Java, lenguajes muy similares en su origen, se ven distinguidos por decisiones de diseño que tomaron cada uno de sus implementadores. C++ es un lenguaje diseñado para ser expresivo, eficiente y compacto en su escritura. Mientras que Java es diseñado con el objetivo de ser consistente, fácil de entender y con una gran cantidad de librarías para ahorrar trabajo al programador. Cada quien debe encontrar cual de estos será su lenguaje insignia, recordando que hay que conocer también al otro, pues puede salvar un problema en medio de una competencia. Mi consejo es que intenten resolver sus primeros problemas en ambos lenguajes y decidir con cual se sienten más cómodos, nunca dejando que otras personas con aparentemente más experiencia les obliguen a entrenar en el lenguaje que ellos prefieran, pues entonces el entrenamiento será en vano.

Ambos lenguajes tienen una gran cantidad de editores inteligentes que pueden ser utilizados para implementar el código con mayor rapidez. Hacerse familiar con estas herramientas también es una parte importante del entrenamiento, pues ahorrará tiempo a la hora de codificar los problemas. Sin embargo, es importante no hacerse dependiente de dichos editores, pues algunas competencias no los ofrecen y se pierden algunas de las ventajas de correr los programas directamente sobre la máquina (en especial para C++). El IDE (Inteligent Development Environment) posiblemente más utilizado, ideado originalmente para Java pero que ahora comprende una amplia variedad de lenguajes, es Eclipse.

Por último, espero que este post les haya gustado y haya servido para empezar a decidir que lenguajes utilizar al atacar un problema. Cualquier comentario o sugerencia es más que bienvenido. ¡Muchísimas gracias por leer!

The Contest Has Begun!

Hola a todos, bienvenidos a este nuevo blog: "Throwing Codes" (Echando Código). La intención de este blog es la de ser una referencia con algoritmos, librerías, estilos y otros consejos dirigidos principalmente a los participantes de los maratones de programación ACM-ICPC. Sin embargo, alguna vez también conseguirán articulos relacionados con otros temas, como lenguajes de programación, matemática y otros más que pueden ser vistos como tangentes a estas competencias.

Y ahora solo queda decirles: Happy Coding!!!