Si estás en este blog, probablemente te pase como a nosotros: te gusta la informática. Y, por ende, la programación. Hoy venimos a descubriros un mundo que tal vez no conozcáis, puesto que no es una práctica muy extendida por las universidades españolas (al menos no en las de Madrid): la programación competitiva. Si quieres saber qué es, cómo funciona y qué tiene de especial la programación competitiva, sigue leyendo este post, estamos seguros de que despertará tu interés.

Cuando yo empecé mi vida en la universidad sólo sabía que la informática era un mundo que me llamaba muchísimo la atención y que era a lo que quería dedicarme. No sabía escribir una sola línea de código. Poco a poco me fui adentrando en el mundo de la programación y descubrí algo más: me encantaba. Para mí era la posibilidad de automatizar trabajos tediosos, construir cosas nuevas y útiles y, en definitiva, un arte. En mi segundo año de universidad descubrí, gracias a quien hoy es un buen amigo, otra cara de la programación: la programación competitiva. Desde InfSeg trataremos de explicaros en qué consiste, los concursos que hay actualmente, cómo podéis participar, etc.

¿Qué es la programación competitiva?

Muchos os estaréis preguntando ¿cómo que programación competitiva?¿existe algo más para programar que las prácticas de clase o lo que me mandan en el trabajo? Pues aunque parezca mentira, sí. La programación competitiva es un método de programación en el que tienes que dar todo de ti y aplicar todos tus conocimientos sobre algoritmia y estructuras de datos. Pero no te asustes, no hace falta ser un experto en programación para participar en concursos de programación. La modalidad que siguen estas competiciones es la siguiente:

Un equipo compuesto por tres personas, no necesariamente todos informáticos (en la sección de “Equipos” podrás aclarar esto), se enfrentan a una serie de problemas propuestos y deben intentar solucionarlos en el menor tiempo posible y de la forma más eficiente en cuanto a memoria y tiempo de ejecución. Normalmente estos concursos suelen tener una duración de entre 3 y 5 horas y los problemarios suelen tener una longitud de entre 8 y 12 problemas. Puedes plantear una solución a cada problema escrito en el lenguaje que elijas, aunque normalmente en los concursos oficiales están restringidos a unos pocos, como C, C++ o Java (Python está ganando terreno poco a poco y de aquí a un tiempo probablemente se incorporará a esta lista). Cada problema tiene unas restricciones propias en cuanto a límites en memoria y tiempo de ejecución. Debes tenerlas en cuenta a la hora de codificar tu solución (no es lo mismo utilizar un Array que un Hashmap, por ejemplo). Una vez que has programado tu solución, debes probarla. Todos los problemas vienen con algún ejemplo de entrada y la salida que debe ofrecer tu programa para que la solución sea considerada correcta. Pero no debes conformarte con que los casos de prueba que se te dan funcionen; lo aconsejable es que pongas al límite a tu programa y pruebes los casos más extraños (casos límite) que se te ocurran para probar tu programa. Cuando estés seguro de que tu solución va a superar la prueba, el siguiente paso es enviarlo para su aprobación al juez online. Un juez online es un software que se dedica a probar los programas que se envían como solución a un problema, sometiéndolo a miles de casos de prueba con datos de entrada similares a los que se dan como ejemplo. Si has probado bien tu programa, seguramente alguno de tus casos límite anteriores también se encuentre en la batería de test del juez. Si tu código supera todos los casos de prueba del juez, ¡enhorabuena! has resuelto un problema. Hay varios tipos de respuesta que puede ofrecer un juez de prueba:

  • Accepted: Es la respuesta más esperada por todo equipo. Significa que tu programa supera todos los casos de test del juez online y que tu solución es correcta.
  • Time Limit Exceeded: Significa que tu problema no respeta los límites de tiempo de ejecución del programa. Deberás revisar el orden de complejidad de tu código y reducirlo.
  • Memory Limit Exceeded: Es parecido al mensaje anterior, con la salvedad de que esta vez estamos consumiendo demasiada memoria en nuestro código. Revisa las estructuras de datos que empleas en el mismo y otros factores que puedan afectar a ello, como el tipo de datos de las variables (no es lo mismo reservar memoria para un integer que para un float).
  • Wrong Answer: Este mensaje indica que tu código está arrojando una respuesta errónea ante un test de prueba. Debes revisar el planteamiento de tu algoritmo y el enunciado del problema, tal vez se te esté escapando algo en lo que no habías caído.
  • Presentation Error: Esto significa que tu código puede ser correcto, pero que el formato en que presentas la solución no es el que piden en tu problema. Revisa la salida de ejemplo que se ha dado en el problema y comprueba que la estás ofreciendo exactamente como se pide.
  • Runtime Error: Este error indica que hay algo en la ejecución de tu programa que no va bien. Comprueba que no tienes ningún bucle infinito o algo similar en tu código.
  • Compilation Error: Este error no deberías tenerlo nunca si has seguido nuestro consejo y has probado tu código antes de enviarlo. Significa que hay un error de compilación en el código.

Lo habitual en este tipo de competiciones es que dos de los participantes lean el problemario mientras que otro (el que más rápido teclee o menos nervioso se ponga bajo presión) está programando o preparando las plantillas para los problemas. Las plantillas son código básico que habitualmente va en todos los programas, como por ejemplo el main o la importación de las librerías necesarias. Lo que se suele hacer es buscar el problema más fácil y resolverlo el primero. ¿Por qué se hace esto? Bien, el factor más importante en un concurso de programación es el tiempo. Me explico. Cada vez que resuelves un problema, el juez online tiene en cuenta el tiempo que has tardado en resolverlo y el número de envíos que has realizado antes de llegar a la solución correcta para un determinado problema. Cada vez que envías un código que devuelve un mensaje distinto de “Accepted”, se penaliza al equipo con una cantidad extra de tiempo. Al final del concurso, el vencedor se declara teniendo en cuenta lo siguiente: 1.- El número de problemas resueltos. Si un equipo ha resuelto más problemas que ningún otro, automáticamente es el ganador. 2.- El tiempo en el que se han resuelto los problemas. Si se da un empate en número de problemas resueltos, lo siguiente que se tiene en cuenta es el tiempo empleado por cada equipo en la resolución de los mismos. Este tiempo final es la suma del tiempo que se ha tardado en resolver cada problema sumado a las penalizaciones.

Por eso es tan importante probar tu programa a conciencia antes de realizar un envío. Imagina obtener una penalización por error de compilación. Querrás que la tierra te trague (si no te come tu equipo antes).

Equipos

Los miembros que conforman un equipo de programación son muy variopintos. No todos son informáticos, sino que también hay miembros que estudian otras ramas en las que también se aprende a programar, como por ejemplo matemáticos, físicos o ingenieros de telecomunicaciones. Esto es así por una razón muy simple: en los concursos, habitualmente hay programas que se resuelven de forma mucho más sencilla mediante una fórmula física o matemática (problemas de estadística, geometría…) que con un algoritmo. Lo ideal para un equipo de programación sería que estuviese compuesto por un matemático, un físico y un informático, pero no te asustes si no cuentas con estos perfiles entre tus filas (en mi equipo, por ejemplo, todos somos informáticos). El modo de trabajar de cada equipo debe cumplir una sola regla: que sea el que más cómodo les resulte a sus miembros. Existen distintas estrategias a la hora de abordar un concurso de programación. Por ejemplo, podéis hacer lo que yo llamo “baile de sillas”. Cada cierto tiempo se van rotando las posiciones entre los miembros del equipo y el que estaba programando pasa a leer problemas o intentar resolverlos en papel y uno de los que leía pasa a programar. Esto puede hacerse cuando la persona que programa está saturada o simplemente cuando uno de los miembros tiene muy claro cómo codificar la solución de un problema. Otra estrategia es que uno de los miembros del equipo comience a leer el problemario por el principio y otro por el final (esta es la estrategia que seguimos en nuestro equipo y funciona bien, pero cada uno debe pulir su técnica y aplicar la que le vaya mejor). De este modo conseguimos localizar el problema más sencillo más rápidamente. Si el tercer miembro ha terminado de escribir sus templates, también puede iniciar la lectura por la mitad del problemario y así agilizar la búsqueda (si es que no se ha encontrado ya el problema más simple). Como decimos, existen muchas estrategias y cada equipo debe elegir la suya y optimizarla para obtener la mayor eficiencia posible. Hay una figura dentro de los equipos de la que aún no hemos hablado. Esta figura es el coach. Su misión es básicamente la de acompañar al equipo a las competiciones y representarlo. Puesto que los equipos de competición suelen nacer en las universidades, el coach suele ser un profesor de la universidad, aunque esto no es siempre así (incluso hay equipos sin coach).

¿Cómo compito?

Ahora que ya conoces lo que es la programación competitiva, tal vez quieras empezar a probar en este mundo y comenzar a entrenar para presentarte a una competición. En algunas universidades (como la Universidad de Valladolid) organizan concursos locales en la universidad para seleccionar a los mejores equipos y que les representen en competiciones más grandes a nivel nacional, regional o incluso mundial. En Madrid conocemos el caso de la Universidad Complutense que organiza el Ada Byron, aunque a este concurso pueden presentarse alumnos de cualquier universidad. La Universidad Rey Juan Carlos está comenzando a promover esta iniciativa entre sus alumnos. Si perteneces a esta universidad y quieres más información acerca del grupo de programación competitiva puedes ponerte en contacto con nosotros y te informaremos acerca de cómo participar. La Universidad Autónoma también cuenta con un grupo de programación competitiva, aunque desconocemos cómo funciona su proceso de selección de equipos para las competiciones. A nivel nacional, la Universidad Politécnica de Cataluña cuenta con un equipo de programación que destaca bastante en las competiciones. La Universidad de Valladolid cuenta incluso con un juez online propio (más abajo encontraréis información acerca de jueces online con los que entrenaros).

Lo mejor que puedes hacer si quieres competir es preguntar en tu universidad si existe algún grupo de este tipo y si no existe, ¡siempre puedes crearlo tú mismo!

Otra forma de competir que tenemos es el modo online. Los concursos son normalmente presenciales, pero algunas entidades celebran concursos online a los que puedes apuntarte y practicar. Puedes encontrar algunos de estos concursos en codechef. Tu equipo y tú podéis utilizar estos concursos a modo de entrenamiento. Otra manera de entrenar son los jueces online, sitios web donde se pone a nuestra disposición un juez como los que se utilizan en los concursos, con la salvedad de que no competimos contra nadie ni hay límite de tiempo. Una buena forma de iniciarse en el mundo de la programación es ir a estos sitios e intentar resolver unos cuantos problemas. Todas las soluciones a los mismos suelen estar disponibles en internet, por lo que si no sabes cómo afrontar un problema siempre puedes ver cómo lo han hecho otros antes y aprender de ellos. Probablemente esto te lleve a conocer algoritmos que tal vez no conocías o técnicas distintas para programar. Siempre aprenderás algo con cada ejercicio resuelto. La programación competitiva es una gran forma de mejorar tus habilidades en programación y algoritmia.

Jueces online

Como os hemos mencionado antes, existen jueces online que ofrecen ejercicios que podemos resolver sin ningún tipo de presión para practicar. A continuación os listamos algunos de ellos para que podáis empezar a poner a trabajar vuestro cerebro:

  • UVA Online Judge: Este es el juez de la universidad de Valladolid. También cuenta con una sección de concursos que se convocan cada cierto tiempo y a los que te puedes apuntar libremente.
  • SPOJ (Sphere Online Judge): Este juez cuenta con más de 6000 problemas públicos para resolver.
  • ¡Acepta el reto!: Este es un juez con problemas escritos en español, en el que además proponen un problema a la semana que les ha parecido curioso o entretenido.
  • Codeforces: Otro juez en el que puedes poner en práctica tus habilidades, con un foro activo en el que la comunidad plantea cuestiones acerca de los problemas, concursos próximos… (Aunque todos los jueces suelen disponer de foro).

Estos son cuatro ejemplos, si buscáis en Google “online judges” seguro que aparece alguno más (no dudes en comentar con tu juez favorito si es alguno diferente a los de la lista de arriba) Al final todos los jueces online son similares. Puedes elegir el que más te guste, el que tenga los problemas que te parezcan más interesantes… Al final lo importante es practicar para mejorar.

Competiciones

Si has llegado hasta este punto del artículo tal vez te interese saber qué competiciones hay para apuntarte con tu equipo. Habitualmente, hay tres divisiones de competiciones: locales, regionales y mundial. Si la afluencia de equipos es muy alta, a veces se realiza una competición a nivel nacional para pasar a la regional, pero no es lo habitual. El proceso que habitualmente se sigue es: se realiza un concurso local en cada universidad. Los ganadores de los locales, van a los regionales y los equipos que ganen las regionales acuden al mundial. Para informarte de las competiciones locales debes acudir a tu universidad y enterarte de si hay algún concurso organizado. Si no lo hay y te animas, puedes hablar con tu escuela e intentar organizar uno por tu cuenta con su ayuda. En Madrid, tenemos el Ada Byron, concurso organizado por la UCM y al que se pueden apuntar los estudiantes de las Universidades madrileñas. La próxima edición del concurso se realizará los días 24 y 25 de Febrero de 2017, por lo que aún estás a tiempo de formar tu equipo y participar. La competición más conocida a nivel regional es el SWERC. Este es un concurso organizado por la ACM y esponsorizado por empresas de renombre como IBM o Microsoft. El SWERC es la competición de la región sudoeste de Europa y cada año se celebra en una ciudad europea distinta (esta última edición ha sido celebrada en Oporto, Portugal). Los dos mejores equipos del SWERC pasan a competir en la competición mundial.

Conclusiones

Como has visto no todo en el mundo de la programación es hacer las prácticas de clase. Existen formas más divertidas de enfocarla. Personalmente creo que la programación competitiva ayuda a mejorar mucho las skills de programación, además de acostumbrarte a situaciones de presión en las que necesitas una capacidad de concentración bastante elevada. Si de verdad te gusta programar, desde InfSeg te animamos a que pruebes este tipo de ejercicio al menos una vez, aunque sea por curiosidad; si no te gusta, con no volver a abrir un juez de programación será suficiente. Y si te acaba anidando el gusanillo que te ha picado, sólo te falta entrenar y formar equipo para hacer algo grande en este curioso mundo.

Para finalizar, os dejo un listado de enlaces que pueden ser útiles si te interesa el mundillo:

Libro sobre técnicas de programación competitiva (Inglés, PDF) Listado de recursos para programación competitiva Otro listado