Skip to the content ForoHackers
Log inJoin

Programación competitiva: por dónde empezar

Competitive programming
#3128 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply