Skip to the content ForoHackers
Log inJoin

Programación competitiva: por dónde empezar

Competitive programming
#622 · Ophuscado · · Report

La programación competitiva consiste en resolver contra reloj problemas algorítmicos bien definidos: leer un enunciado, encontrar un algoritmo, programarlo y pasar pruebas ocultas dentro de límites de tiempo y de memoria. Afina la resolución de problemas, el conocimiento de algoritmos y la programación rápida y correcta, y el archivo de problemas de concursos pasados es un conjunto de entrenamiento gratuito e inagotable.

Conceptos clave

  • Primero la complejidad: el tamaño de la entrada te dice qué tiempo de ejecución puede pasar; un millón de elementos descarta un bucle cuadrático.
  • Técnicas básicas: ordenación, búsqueda binaria, decisiones voraces, dos punteros, sumas de prefijos y programación dinámica.
  • Grafos y árboles: BFS, DFS, caminos mínimos, union-find y árboles de expansión.
  • Teoría de números y conteo: aritmética modular, primos y combinatoria.
  • Pruebas: escribe una fuerza bruta lenta y compárala con tu solución rápida en entradas pequeñas aleatorias para encontrar contraejemplos.

Vocabulario

  • Veredicto: la respuesta del juez, como aceptado, respuesta incorrecta o límite de tiempo excedido.
  • Límite de tiempo: lo máximo que puede tardar una solución en una prueba.
  • Editorial: la solución escrita que se publica tras un concurso.
  • Plantilla: código reutilizable que tienes a mano para la entrada, la salida y las estructuras comunes.

Qué estudiar, en orden

  1. Elige un lenguaje, aprende su biblioteca estándar y su entrada y salida rápidas.
  2. Resuelve problemas fáciles de bucles, aritmética y ordenación, y lee la editorial de cada uno que falles.
  3. Aprende búsqueda binaria, sumas de prefijos y métodos voraces; luego programación dinámica con los problemas clásicos.
  4. Implementa de memoria BFS, DFS, el algoritmo de Dijkstra y union-find.
  5. Aprende montículos, árboles de Fenwick y de segmentos, y tablas hash, y cuándo compensa cada uno.
  6. Participa en concursos regulares, practica con cronómetro y haz upsolving de cada problema que falles.

Etiquetas relacionadas

#algorithms #data-structures #complexity #graph-theory #combinatorics

Log in or join to reply.