¡Divide y Vencerás la Programación Dinámica!

Cuando se empieza a competir en los maratones de programación, los que tienen más experiencia pueden llegar a intimidarnos un poco cuando discuten la solución de un problema. Mencionan algoritmos, técnicas y librerías de las que no tenemos ni idea y a veces se no hace difícil seguir la conversación. Personalmente, me intrigaba mucho cuando decían que tal o cual problema era una Programación Dinámica. En aquel momento, decidí investigar un poco por mi cuenta e intenté resolver algunos problemas relacionados (principalmente en SPOJ). Una de las referencias que más me ayudó fue el tutorial que tiene Topcoder sobre el tema. Sin embargo, más que ofrecerles otro tutorial completo, lo que quisiera a continuación es nada más que mencionarles, a grandes rasgos, de que se trata la programación dinámica y como podemos reconocer un problema de ese estilo.

Sin embargo, antes de empezar a discutir el tema, quisiera hablarles un poco sobre una técnica de resolución de problemas conocida como Divide y Vencerás. Esta técnica se basa en tomar un problema, dividirlo en varios problemas más pequeños (similares al original), resolver cada uno de esos subproblemas y luego unirlos de cierta forma tal que resuelva el problema original. Por ejemplo, veamos el algoritmo Mergesort. La intención es ordenar un arreglo y Mergesort logra este objetivo partiendo el arreglo a la mitad, ordenando cada una de estas mitades y luego uniendo las mitades ya ordenadas nuevamente en un solo arreglo (tal que este último continúe ordenado). Así para ordenar un arreglo, Mergesort solo necesita saber como ordenar arreglos que son de la mitad del tamaño del original. (Que es un problema similar, pero más pequeño) y luego saber como unirlos haciendo que el arreglo final resulte de igual forma ordenado.


Ahora, si esos subproblemas que acabamos de construir los mandamos a ordenar con el mismo Mergesort, tendremos un algoritmo recursivo. Éste partirá siempre el arreglo que debe ordenar a la mitad, luego ordenará cada mitad por separado y por último volverá a unir ambas partes. Sin embargo, como cada subproblema que generamos es más pequeño que el original, si continuamos haciendo esto, eventualmente llegaremos a llamar a Mergesort con un arreglo que tiene un solo elemento. Es imposible partir este arreglo de un solo elemento por la mitad. ¿Entonces que hacemos? ... La respuesta es simplemente devolver el mismo arreglo, ya que un arreglo de un solo elemento está inmediatamente ordenado. A este tipo de casos excepcionales se les conoce como caso base de la recursión y son necesarios siempre que se esté implementando un algoritmo recursivo.

Como pudimos ver, Mergesort es un ejemplo importante de la técnica de Divide y Vencerás, sin embargo no es el único. Hay muchos problemas que se pueden plantear de esta forma, dividiendo el problema original uno o más subproblemas y tratando luego cada uno de ellos por separado. Un momento... ¿Uno o más? ¿Puede dividirse en un solo subproblema? ... ¡La respuesta es que si! Y como ejemplo podríamos analizar el algoritmo de Búsqueda Binaria. Esto queda de ejercicio para el lector.

Pero este es un blog sobre maratones de programación, así que intentemos resolver un problema real de competencia. En esta ocasión, intentaremos resolver el problema PIGBANK de SPOJ.


Analicemos lo que nos están pidiendo. Nos dan un conjunto posible de monedas que tienen su propio peso y valor. Nos dan también un peso total que debemos cubrir exactamente con cualquier cantidad de las monedas disponibles (Este peso es la resta del peso de la alcancía llena y la alcancía vacía, F - E). Ahora bien, lo que queremos es minimizar el valor total posible. Crearemos entonces una función valmin (Valor mínimo), tal que:

valmin(W): El valor mínimo que se puede lograr, ocupando exactamente W de peso, utilizando cualquier cantidad de monedas posible.

Ahora, veamos que pasa si asumimos que una moneda m se encuentra dentro de la alcancía. Esto aseguraría que el valor mínimo que buscamos es por lo menos el valor de m. A este valor deberíamos sumarle luego el nuevo valor mínimo que es posible con el peso original menos el peso de la moneda m. Entonces, nuevamente estando seguros de que la moneda m se encuentra en la alcancía, tendríamos que se cumple la siguiente ecuación:

valmin(W) = costo de m + valmin(W - peso de m)

Sin embargo, no sabemos realmente que monedas se encuentran en la alcancía. Lo que podemos entonces es intentar tomar la moneda que mas nos convenga. ¿Y cual sería tal moneda? Dado que queremos minimizar, la mejor moneda es la que haga que la suma en la ecuación anterior sea la más pequeña posible.

valmin(W) = min i : 0 <= i < numero de monedas : costo de i + valmin(W - peso de i)

Conseguimos entonces una función recursiva para calcular el valor mínimo que necesitamos, sin embargo falta aún algo. ¿Que pasa cuando W es cero? ¿Cual es entonces el valor mínimo posible? La respuesta es también cero, pues la única forma de llenar un peso nulo es sin utilizar monedas.

valmin(0) = 0

Ahora tenemos también un caso base para la recursión, sin embargo aún no hemos terminado de formular la solución. ¿Que pasaría si para un cierto peso W, no existiese ninguna moneda que tenga peso menor a W? Si esto sucediera, no habría forma de incluir una moneda en la solución y por lo tanto debe reportarse que alcanzar tal peso con las monedas disponibles es en realidad imposible. Pero valmin es una función. ¿Que valores le asignamos a estos casos imposibles? Debe ser un valor que sea automáticamente peor que todos los demás valores posibles. Solamente existe un psuedonúmero con esa propiedad: El infinito. Nótese que para hacer el código más fácil podemos permitir que los casos imposibles hagan su llamada recursiva valmin(W - peso de i), que estaría llamando a valmin entonces con un valor negativo.

valmin(W) = Infinito, para todo W < 0


Pero el infinito no existe realmente en la computadora, lo que debemos es escoger un valor que sea lo suficientemente grande como para que se comporte de la misma forma. El primer valor que uno podría pensar es el máximo entero (2^31 - 1). Sin embargo, este valor tiene un problema. Si en una llamada recursiva valmin(W - peso de i) el resultado es (2^31 - 1), al sumarle el costo de i estaríamos incurriendo en un overflow, posiblemente resultando la suma en algún número negativo que haría que nuestro programa no se comporte como esperamos. Detalles como éste muchas veces hacen fallar a un programa que estaría correcto de haber escogido el infinito con más cuidado. Debemos buscar entonces un infinito que nos asegure que no haya overflow. Para eso analicemos el enunciado. Debemos asegurar que: costo de i + valmin(W - peso de i) no de overflow.

costo de i + valmin(W - peso de i) <= 2^31 - 1

El mayor valor posible para costo de i es 50000, por lo que tenemos lo siguiente:

50000 + valmin(W - peso de i) <= 2^31 - 1

Esto quiere decir que cualquier valor de infinito que sea menor que (2^31-1 - 50000) es un valor aceptable. Particularmente el valor 10^9 cumple con esa característica. ¿Será 10^9 lo suficientemente grande como para ser infinito? Veamos el caso extremo, que solo tengamos monedas de valor 50000 y peso 1, y además además queramos llenar una alcancía de peso 9999 (que es la máxima resta posible entre F y E). El menor y único valor posible en este caso sería 50000 * 9999 = 499950000 que es menor que 10^9.

Muy bien, ya tenemos todo lo que nos hace falta, solamente queda transcribir lo que hemos pensado a algún lenguaje de programación y enviarlo a SPOJ para que sea juzgado. Les recomiendo a los lectores que intenten hacer su propia implementación, sin embargo les dejó este enlace con una implementación propia de todo lo que se ha discutido hasta ahora.

Una vez enviemos el problema a SPOJ, nos daremos cuenta de que nuestro algoritmo es demasiado lento y el juez nos reportará un Time Limit Exceeded. ¿Por que está ocurriendo esto? Supongamos que hay dos monedas m1 y m2 que con seguridad están en la alcancía. Como estamos minimizando, la función valmin debe recorrer todas las monedas posibles para decidir cual es la mejor. Por lo tanto, valmin(W) llamará tanto a valmin(W - peso de m1) como a valmin(W - peso de m2). Ahora, dentro de la primera llamada recursiva, se intentará también en algún momento descontar la moneda m2, lo que resultaría en una llamada a valmin((W - peso de m1) - peso de m2). Por su parte, la segunda llamada recursiva eventualmente intentará descontar la moneda m1, lo que resultaría en una llamada a valmin((W - peso de m2) - peso de m1). Notemos que estas llamadas del segundo nivel de la recursión son en realidad la misma. ¡Y la estamos calculando dos veces! Imaginen entonces como sería con tres monedas, cuatro monedas, etc. Estamos recalculando muchas veces, muchas llamadas distintas a valmin. Esto hace que nuestro programa corra demasiado lento (de hecho, tomará un tiempo de ejecución exponencial con respecto al peso original de la alcancía y a la cantidad de monedas disponibles. De la razón de esto hablaré en alguna otra ocasión).


¿Como podemos evitarlo? Bueno, podríamos tener un arreglo que esté afuera de la función y que nos sirva para recordar que llamadas se han hecho hasta el momento. Esto es, cada vez que hagamos una llamada a valmin(W) guardaremos en ese arreglo que hemos ya calculado valmin para W y el valor que nos haya resultado. Como en ese arreglo deben caber todos los W posibles, debe tener al menos tamaño 10000 que es la cota superior para el mayor peso posible. Ahora, solo guardaremos este valor para el caso recursivo, no hace falta memorizarlo para el caso baso o el caso imposible, ya que estos son muy rápidos de calcular.

¿Como saber si ya hemos calculado valmin para algún W particular? Podríamos colocarle a la posición W del arreglo un valor imposible (como -1). Entonces, al inicio del calculo todas las posiciones del arreglo tendrían -1 y al transcurrir la ejecución, solo las que aún tengan -1 serán las que necesitaremos calcular. Realicemos entonces ese cambio a nuestro programa. (Nuevamente les aconsejo que implementen su propia solución, sin embargo pueden encontrar una implementación propia en este enlace. Si bien pudiera implementarse esta misma solución en Java, la razón por la que he escogido C++ pueden entontrarla aquí.)

Lo volvemos a mandar al juez de SPOJ y si hicimos todo bien, tendremos un problema aceptado. Lo único que hicimos fue recordar que cosas ya habíamos calculado y mejoramos muchísimo el tiempo de ejecución de nuestro programa. A eso que hicimos, de recordar lo calculado, es a lo que se conoce como Programación Dinámica.

Ahora bien, este problema que acabamos de resolver es muy similar a un problema clásico conocido como El Problema de la Mochila. Es buena idea investigar y saber resolver estos problemas clásicos, ya que al hallar la relación con el problema que queremos resolver podemos utilizar la misma estrategia que utilizan estos últimos. Wikipedia tiene una buena variedad de problemas clásicos de programación dinámica que vale la pena revisar.

¿Que sigue ahora? Practicar con otros problemas para terminar de ver como se puede dividir y vencer un problema, así como notar si las llamadas se repiten y luego si puediesen memorizarse. ¿Como reconocer un problema de programación dinámica? Casi siempre se querrá minimizar o maximizar una función y el tamaño de la entrada será muy grande como para intentar resolverlo por Fuerza bruta (Por ejemplo, la versión Divide y Vencerás sin memorización), pero lo suficientemente pequeños como para caber en la memoria de una máquina promedio (Aproximadamente hasta 10^7 enteros). Si la entrada es demasiado grande, posiblemente el problema se resuelva con un algoritmo ambicioso, una programación dinámica que ahorre memoria o una búsqueda binaria, todos tópicos que se cubrirán más adelante en el blog.

Como tarea les dejo que resuelvan el problema MIXTURES, y que luego vean la relación que guarda este último con el problema clásico de programación dinámica conocido como Multiplicación Encadenada de Matrices.

Bueno, espero les haya servido esta pequeña explicación de lo que se trata la Programación Dinámica. Cualquier comentario o sugerencia es como siempre más que bienvenido. ¡Muchísimas gracias por leer! Hasta la próxima.

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!!!