Preparación para la ACM ICPC

Introducción

La ACM ICPC es una competición internacional de programación por equipos que se celebra todos los años en la que compiten estudiantes universitarios de todo el mundo. Se organizan fases regionales de clasificación y los mejores equipos de cada región compiten en la fase final.

Preparación

La mejor manera de entrenar para esta competición es resolver muchos problemas del mismo tipo que los que ponen en el concurso. También es necesario conocer muy bien la sintaxis y el funcionamiento del lenguaje de programación que utilicemos (C, C++ o JAVA). La únicas librerias que se permiten son las estándar que acompañan a los compiladores. Es importante conocer los distintos tipos de problemas que se presentan y esto se consigue con la práctica. A menudo suelen aparecer problemas de los siguientes tipos:

Matemáticos: Calculos numéricos, Aritmética con números grandes, Números primos, Aritmética modular, Teoría de números, Otros (Fibonacci, Goldbach...)
Teoría de grafos: dfs, bfs Búsqueda del camino mínimo, Árbol de recubrimiento mínimo, Network Flow, Ordenación topológica
Geometría: Líneas, rectas, circumferencias, Envoltura convexa
Programación dinámica
Algoritmos voraces
Simulación: Problemas en los que simplemente hay que seguir una series de reglas indicadas en el enunciado. Ej: Dirigir un robot por un mapa siguiendo las órdenes escritas en un fichero.
Combinatoria: Calcular el número de combinaciones de un conjunto, muchas veces se pueden resolver con programación dinámica, Recurrencias, Coeficientes binomiales
Ordenación: Ordenar una serie de elementos complejos (por ejemplo elefantes)
Problemas de entrada/salida: La única complicación es tratar con la entrada o la salida del problema. Por ejemplo dibujar letras con asteriscos

Páginas con problemas

Los dos principales sitios para practicar son la página de USA Computing Olympiad (USACO) y el Problem Set Archive de la Universidad de Valladolid (Uva).

La USACO tiene una gran cantidad de problemas ordenados (más o menos) por su dificultad. Para acceder a nuevas secciones de problemas hay que resolver las anteriores. Las secciones suelen venir acompañadas de algún texto introductorio sobre algoritmos que es interesante leer. Los problemas de esta página son en general sencillos de entender, están bien definidos en su enunciado y no tienen trampas. La página de la UVa tiene más de mil de problemas del mismo tipo que los que ponen en la SWERC. Se puede acceder a todos los enunciados desde el principio (no hay "secciones" como en USACO) y no hay ninguna clasificación para los problemas, los más sencillos están mezclados con los más difíciles. Los problemas de esta página hay que leerlos muy atentamente para descubrir todos los detalles y las posibles trampas en el enunciado.

Otra página interesante es The 2000's ACM-ICPC Live Archive Around the World . Pertenece también a la Universidad de Valladolid y tiene una base de datos con los problemas que han aparecido en el ACM ICPC durante los últimos años.Tiene cientos de problemas de todas las fases clasificatorias del mundo y también de las fases finales. Lamentablemente esta página no tiene solución para muchos de los problemas que contiene por lo que no es tan útil como las otras dos para practicar.

---

Volver Arriba

INTERESADOS ESCRIBIR A: