Saltar al contenido ForoHackers

Programación competitiva: por dónde empezar

Programación competitiva
#3128 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder