Tips para ser competitivo

Programación Competitiva

Dados problemas bien conocidos, resolverlos tan rápido como sea posible.

Tip 1: Escribe código rápido

Tip 2: Indentifica rápidamente los problemas

Los equipos reciben un conjunto de problemas (entre 7 y 12) de diferentes tipos. Es importante lograr categorizar estos problemas. Algunas de las temáticas más comunes son las siguientes:

  • Ad Hoc [1-2]
  • Búsqueda completa [1-2]
  • Divide y vencerás [0-1]
  • Algoritmos Greedy [0-1]
  • Progamación dinámica [1-3]
  • Grafos [1-2]
  • Matemáticas [1-2]
  • Procesamiento de cadenas [1]
  • Geometria Computacional [1]
  • Problemas raros/dificiles [1-2]

Tip 3: Hacer análisis de algoritmos

Dado el límite de las entradas... ¿Puede nuestra solución, dada su complejidad pasar el limite de tiempo dado para el problema?

Muchas veces, existe más de una manera de solucionar un problema. Nuestra tarea es elegir la solución más simple que funcione (que su ejecución no supere el tiempo limite y aún así produzca una respuesta correcta).

Mayor número de datos n que puede procesarse dada la complejidad del algoritmo.

Tip 4: Probar el código (Debuggear)

  • Verifica que tus salidas sean exactamente iguales a las salidas dadas en los casos de prueba del problema.
  • Para ejercicios con múltiples casos de prueba, podrías incluir en tus pruebas un mismo caso varias veces. Esto ayuda a determinar si olvidaste inicializar alguna variable al finalizar la ejecución de un caso de prueba.
  • Tus casos de prueba deben incluir casos tricky. Intenta probar con el peor caso posible que se te ocurra.
  • Tus casos de prueba deben incluir casos grandes. Ve incrementando el tamaño de la entrada hasta alcanzar los limites propuestos por el problema.

Tip 5: Trabajo en equipo

Ser cuidadosos al copiar el código del formulario o los apuntes

No se quieren tener errores o penalizaciones por copiar mal un algoritmo.

Hacer siempre el siguiente problema más facil aún no resuelto

Una de las preocupaciones del equipo durante la competencia debe ser: ¿Cuál es el siguiente problema más fácil?

Comenzar leyendo todo

Cuando aparece un problema fácil, se avisa y alguien debe programarlo. Si aparece otro aún más fácil lo pueden priorizar. Al cabo de cierto tiempo todos los problemas ya deberian estar leidos, no es necesario que todos los miembros del equipo hayan leido todos los problemas, sino que cada problema al menos un integrante del equipo lo debería haber leído.

Usar el Scoreboard

Es una herramienta valiosa para detectar los problemas fáciles y también los difíciles/tramposos. Un problema que a los 4 minutos ya tiene un Aceptado, seguramente será un problema sencillo de programar. De la misma manera un problema que han enviado muchos equipos y ninguno a acertado es problablemente difícil o muy tramposo. NO se debe perder tiempo mirando el scoreboard en cada actualización.

Al principio de la competencia no debería trabajar más de un participante en el mismo problema.

Los participantes se pueden pasar problemas entre ellos pero la idea no es paralelizar la solución de un mismo problema al inicio de la competencia.

Releer el enunciado completo

Si hay dudas, el ejercicio parece raro y más aún si hubo un Wrong Answer se debe releer el enunciado. Es necesario prestar mucha atención a los límites ya que estos pueden cambiar totalmente el problema.

Aprovechar el ordenador

Si creen que el que esta en el ordenador esta tardando demasiado y tienen otro ejercicio que pueden terminar mucho más rápido... hagan un cambio: Programen a papel el ejercicio en el que estan tardando mucho y mientras aprovechen el ordenador para hacer el otro.

Probar muy bien el problema antes de enviarlo al juez

Antes de realizar el envio, tomense un tiempo para probar el código y ejecuten algunos casos de prueba interesantes.

Al final del concurso deben trabajar en 1 o 2 problemas como máximo

Cerca del final (faltando 1 hora más o menos) deben tratar de abordar 1 o 2 problemas como mucho. Deben descartar aquellos problemas que consideren que no van a salir en el tiempo y a diferencia del inicio de la competencia deben tratar de trabajar juntos en la solución de un mismo problema, ya sea aportando sugerencias, detectando errores y demás ya que conviene asegurar al menos 1 problema más.

Tip 6: Práctica y más práctica

Existe una gran cantidad de plataformas que les permitirán mejorar sus habilidades de solución de problemas. (No pierdas mucho tiempo intentando mejorar la velocidad de una solución es mejor solucionar muchos problemas)

Pero lo más importante de todo es... ¡Disfruten del concurso! :)

Fuentes

  • Competitive Programming 3