Introducción de cero a la programación competitiva

Escribo esta entrada porque varios me han pedido consejo de por dónde empezar a introducirse a la programación competitiva.


Voy a suponer que tienen conocimientos de programación básicos. Quizás más adelante agregue alguna referencia de dónde pueden aprender a programar pero creo que hay muchísimo más material de esto que de programación competitiva en sí.

Recomiendo seguir los siguientes tres puntos para empezar de 0. No están hechos para hacerse en orden sino a la par. Esto puede llevar tiempo, así que a no desmotivarse. Más abajo listo material útil. Y por último doy algunos tips que se me fueron ocurriendo a medida que escribía esto.

Introduciéndose:

        1. Si nunca submiteaste un problema, create una cuenta en USACO (ver link del compilado) y ver la primer seccion para ver como es la dinámica, el formato que tenés que respetar, de como submitear una solución en un juez online.

        2. Ver el libro de Steven Halim. La sección introductoria y de problemas ad hoc es un buen punto de partida. Otro portal por el que se puede empezar es URI que tiene problemas ordenados por dificultad y podemos elegir los más fáciles.

        3. Crearse una cuenta en Codeforces. Podés empezar haciendo problemas A de Div2 (los más fáciles y tratar de hacerlos). Si tu respuesta es incorrecta te permite ver por qué y cómo debería ser la respuesta correcta del programa.

        4. Seguir el libro Halim en secciones posteriores (como Greedy, Programación Dinámica, Grafos) para incorporar conocimientos teóricos nuevos que nos van a permitir resolver un espectro más amplio de problemas. Siempre es importante no quedarnos con los problemas fáciles que se nos ocurren rápidamente ni tratar sólo los tan difíciles que debamos ver siempre la solución, sino ir ampliando de a poco nuestro horizonte y dejar un tiempo razonable el problema en el tintero. Ojo, que también es importante que si no salió el problema, buscar la solución tratar de implementarla por uno mismo y entender por qué no me salió (tal vez algo teórico que no sabía y deba aprender, o quizás alguna manera de enfocarlo distinto), incorporar este nuevo conocimiento y pensar cómo podría ayudarme a resolver otros problemas distintos.

Material útil:

USACO: http://train.usaco.org/usacogate
Es una página de entrenamiento para competencias (IOI) de secundario de los norteamericanos.
Muy amena introducción. Recomendable para hacer la primer sección como introducción a la dinámica de la progrmación competitiva.
Recomiendo seguir la guía si estás entrenando para el secundario pero sino no sugiero hacerlo, creo que hay lugares mejores orientados a la ICPC.
Es motivante el hecho de que necesitás hacer los problemas de una sección para pasar a la siguiente pero a veces traba un poco, en estos casos recomiendo buscar alguna solución en internet y submitearla.

Codeforces: http://codeforces.com/
Es una comunidad muy piola que organiza competencias online periódicamente. También hay algunas guías de temas teóricos desde básicos hasta muy avanzados.
Súper recomiendo crearse una cuenta acá y empezar a ver problemas. Los problemas están clasificados en dos divisiones (Div2, fáciles y Div1 avanzados). Además en las competencias suelen estar ordenados por dificultad creciente.
La página tiene una sección llamada Gym, muy útil para practicar con tu equipo competencias oficiales anteriores ya que simula el scoreboard como si estuvieras compitiendo con las personas que participaron antes.

Training Camp Argentina: https://sites.google.com/site/trainingcampargentina2016/
De los training camps argentinos da para hablar mucho, pero en resúmen es un evento HIPER recomendable (diría que hasta escencial!) para participar. Organizado por gente muy buena onda y copada, con mucho trabajo solidario aporta para que este tema de las competencias se extienda en todo el país.
Siempre decimos que sin ayuda de estos eventos nunca hubiéramos clasificado a nuestra primer mundial. Se hacen en junio generalmente y consiste en un curso donde todos los días tener clases teóricas a la mañana y simulacro de competencia por las tardes. Es muy intensivo pero re vale la pena hacerlo!!
Acá puse la página de la edición 2016 pero si googlean por año, aparecen todos lo anteriores. Tiene slides de teoría que se dio y links a las competencias que se simularon.

Live Archive https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8
Uno de los tantos jueces en línea. Acá tenemos, por ejemplo, los regionales de años anteriores. Aunque particularmente no recomiendo quemarse problemas de estos así pueden simularlos después con sus equipos.

UVa Online Judge: https://uva.onlinejudge.org/
Otro juez en línea. El libro de Halim tiene referencias a problemas que se encuentran acá.

Competitive Programing (Libro de Halim)
https://sites.google.com/site/stevenhalim/
Este libro lo compramos nosotros. No se comercializa acá y hay que esperar algunos meses a que llegue acá en Argentina, pueden intentar buscar alguna versión por Internet.
Yo creo que está bueno para empezar, de hecho nosotros empezamos por acá y le debemos mucho mucho a Steven Halim. Tuvimos la oportunidad de agradecerle personalmente y sacarnos una foto con él! (siempre asiste como invitado a las finales)
Está bueno que presenta un panorama general de las categorías de problemas existentes y cada sección tiene un desarrollo que llegua a conceptos avanzados, dando código de ejemplo y referencias a problemas de jueces online.
También existe el libro Programming Challenges de Steven Skiena, que tiene un approach un poco menos centrado a las competencias pero más claro en cuánto a las introducciones a los temas.

URI online Judge (https://www.urionlinejudge.com.br/judge/en/login)
Es un juez brasilero. Cada vez más está incorporando y traduciendo problemas al español. Una de las ventajas de URI frente a otros portales es que tiene los problemas clasificados por dificultad.
Ésto esta muy bueno, entre muchas varias otras cosas porque cuando uno empieza no tiene la capacidad de discernir cuando un problema es complicado y no está a su alcance ó cuando simplemente le tiene que dedicar más tiempo. Y está bueno empezar con problemas fáciles, especialmente si uno aprendió a programar hace poco es probable que tenga muchos errores las primeras veces.

e-maxx.ru: http://e-maxx.ru/algo/
Es una página con muchísimo material avanzado en ruso. Los rusos son la vanguardia en esto así que es común ver material en ruso. Yo siempre usé Google para traducir pero quizás Yandex sea mejor.


Tips:
  • Qué es un Juez en Línea? Es un sitio donde hay problemas y puedes submitear código para que checkee si resuelve el problema.

    Es muy importante que a la hora de hacer problemas no sólo los pienses, sino programes y submitees. Es muy común al principio tener errores en los que nuestro programa anda bien en CASI todos los casos pero hay alguno que falla porque no lo contemplamos. De hecho no cometer errores implementando el problema, aún teniendo una idea correcta es una gran parte de la competencia. Por eso creo que es escencial que para mejorar hagan problemas que ESTEN SEGUROS que van a poder submitear el código en algún juez y verificar que sea correcto.
  • Los jueces corrigen MUY ESTRICTAMENTE como van a ver si hacen la primera sección del USACO. Son máquinas, así que una mayúscula en vez de minúscula, un espacio o un salto de línea de más hará que nuestra solución este MAL.
  •   Programar en C++: siempre escoger el lenguaje, dentro de los que permiten las competencias, es una cuestión de gustos. Pueden elegir Java si prefieren. Yo recomeidno C++ por varias razones:
    1. Creo que hay más material en C++ que en Java.
    2. Python creo que fue introducido para incentivar la participación ya que se está enseñando mucho en primeros años. En la ICPC se lo está comenzando a adoptar pero aún tiene varios problemas que genera que NO todos los problemas puedan ser resueltos en python. Esto se debe a que usa los tiempos límite de ejecucción de Java y no tiene tiempos límite propios, puede que muchas veces Python sea más lento y un programa que resuelve satisfactoriamente y en la complejidad requerida el problema y aún así el veredicto sea Time Limit Exceeded .
    3. Por sobre C, C++ tiene la STL con muchas estructuras ya hechas que aporta mucha ventaja (set, map, priority_queue, etc).
  • Considerar ir al training camp es una excelente idea. Si sos alumno de la FCEIA, año a año se ha tratado que los gastos de traslado sean cubiertos con apoyo del departamento de Computación. A veces el evento cuenta con sponsors que cubren gastos de alojamiento.  El respeto y relevancia que la ICPC inspira así como los resultados que hemos logrados han hecho tomar conciencia a los profesores de REPROGRAMAR fechas de examenes. No sólo en Computación sino desde la Escuela de Ciencias Exactas hay una voluntad de hacer prosperar esto. Así que si de algún modo es impedimento para su participación algún compromiso académico, esto se puede llegar a ver y tratar razonablemente.
  •  Rodeate de gente con la que puedas compartir y apoyarte. La idea que surgan talleres, entrenadores y materias optativas sobre Programación Competitiva es para satisfacer la necesidad de estos espacios. En nuestro inicio tuvimos la suerte de formar el equipo y apoyarnos entre nosotros fue muy importante para seguir avanzando.


       

3 comentarios: