ACM ICPC ( A ssociation for Computing M achinery – I nternational Collegiate P rogramming C ontest ) es un concurso mundial anual de programación de varios niveles que se organiza desde hace más de trece años. El concurso está patrocinado por IBM.
Este artículo se enfoca en todos los temas que son importantes para la programación competitiva y que deben estudiarse especialmente para capacitarse para el próximo concurso ACM-ICPC.
Reglas del Concurso – Reglas finales mundiales para 2021 Haga clic aquí
Participantes indios : Codechef realiza todos los Regionales indios. Haga clic aquí para saber sobre formación de equipos, reembolsos, etc.
ICPC for Schools de CodeChef : esta competencia sirve como una puerta de entrada para que los estudiantes de la escuela participen en el concurso ACM ICPC junto con los participantes universitarios de ICPC que se llevan a cabo en toda la India. Es una idea concebida por CodeChef y apoyada por la Universidad Amrita.
Ejemplo de un problema ICPC: un problema ICPC habitual tiene las siguientes características:
- Enunciado del problema: describe el problema y qué salida se va a generar.
- Entrada: asegúrese de leer esta sección con total atención, ya que perderse cualquier detalle menor puede llevarlo a una zona de respuesta incorrecta.
- Salida: Al igual que arriba, este también debe leerse detenidamente.
- Restricciones: pueden incluir restricciones de entrada, tiempo, memoria, tamaño del código, etc.
- Límite de tiempo: vea si su algoritmo puede funcionar en este rango. Si no, ¡es hora de cambiarlo!
- Límite de memoria: si te gusta asignar memoria para cada pequeña cosa, es un buen momento para que lo cambies.
Preparación para ACM-ICPC
El primer y más importante paso: PRÁCTICA: a continuación se encuentran los recursos que se pueden consultar para practicar los concursos y problemas similares de ACM-ICPC. Para todos estos Jueces en línea, comience con los problemas con envíos máximos y verifique otras soluciones para ver cómo puede mejorar. Participe en sus concursos mensuales para mantenerse al día.
- Problemas pasados de ACM-ICPC – Archivo ICPC , práctica en Codechef
- TopCoder : proceda aumentando gradualmente los niveles de problemas
- Codeforces -Lista de conjuntos de problemas
- Codechef : los principiantes pueden comenzar con Codechef Beginners y continuar
- SPOJ : pasar de problemas fáciles a difíciles
- USACO – Excelente recurso de capacitación
- uvaOnline Judge – Enorme repositorio de problemas
- Hackerrank : practique los problemas por temas y participe en series preparatorias
- Hackerearth – Participa en serie preparatoria
- Práctica : buena para principiantes. Tiene problemas que van desde el nivel de dificultad Escuela hasta Difícil.
- Lista de varios concursos de programación competitivos disponibles en línea durante todo el año
¿Qué estudiar?
Saber solo los conceptos básicos de la programación no será fructífero para los aspirantes a ACM ICPC. También es necesario tener un conocimiento profundo de los algoritmos avanzados utilizados. Los siguientes temas enumeran los temas y algoritmos necesarios que uno debe conocer para mejorar y tener una oportunidad en la competencia real.
Estructuras de datos elementales: Para comenzar con la programación competitiva, uno debe dominar las Estructuras de datos. A continuación se muestra la lista de las estructuras de datos más utilizadas:
Estructuras de datos avanzadas
Colas de prioridad , conjuntos de búsqueda de unión, árboles de intervalo (aumentados), BST equilibrados (aumentados) y árboles indexados binarios
- Árbol indexado binario o árbol Fenwick
- Árbol de segmentos ( RMQ , Range Sum y Lazy Propagation )
- Árbol KD (Ver insertar , mínimo y eliminar )
- Conjunto disjunto de búsqueda de unión ( detección de ciclo y compresión por rango y ruta )
- Intentos
- Árbol de intervalos
Estructuras de datos más avanzadas.
Clasificación y búsqueda: concéntrese para aprender los conceptos básicos y también familiarícese con todas las funciones de biblioteca disponibles.
Manipulación de strings: las strings hacen que los problemas de programación sean interesantes y difíciles también y probablemente esa es la razón por la que se usan ampliamente en tales concursos. El aprendizaje de las funciones de la biblioteca para String en realidad resulta muy útil (C++: Ver this y this , String en Java ).
Elegir el lenguaje correcto: C++ es hasta la fecha el lenguaje más preferido seguido de Java cuando se trata de concursos de programación, pero siempre debe elegir un lenguaje con el que se sienta cómodo. Tener CONFIANZA en cualquier idioma es lo más importante.
Biblioteca de plantillas estándar : la quintaesencia, especialmente para aquellos que usan C++ como lenguaje de codificación
- Encienda C++ STL por Topcoder – Parte 1 , Parte 2
- Magos de C++: algoritmos STL
Programación dinámica
- Subsecuencia común más larga
- Subsecuencia creciente más larga
- Editar distancia
- Partición mínima
- Formas de cubrir una distancia
- Ruta más larga en Matrix
- Problema de suma de subconjuntos
- Estrategia óptima para un juego
- 0-1 Problema de mochila
- Programación de la línea de montaje
- Árbol de búsqueda binario óptimo
AtrásSeguimiento
- Rata en un laberinto
- Problema de la reina N
- Suma de subconjunto
- m Problema de coloración
- ciclo hamiltoniano
Más artículos sobre el retroceso
Algoritmos codiciosos
- Problema de selección de actividades
- Algoritmo de árbol de expansión mínimo de Kruskal
- Codificación de Huffman
- Codificación eficiente de Huffman para entrada ordenada
- Algoritmo de árbol de expansión mínimo de Prim
Más artículos sobre algoritmos codiciosos
Algoritmos gráficos: uno de los temas más importantes que no puede ignorar si se prepara para ACM – ICPC.
- Búsqueda primero en amplitud (BFS)
- Primera búsqueda en profundidad (DFS)
- Ruta más corta desde el origen hasta todos los vértices **Dijkstra**
- Ruta más corta de cada vértice a cualquier otro vértice **Floyd Warshall**
- Árbol de expansión mínimo **Prim**
- Árbol de expansión mínimo **Kruskal**
- Clasificación topológica
- algoritmo de johnson
- Puntos de articulación (o vértices de corte) en un gráfico
- Puentes en un gráfico
Matemáticas Básicas
Aritmética: los programadores deben saber cómo se representan internamente los números enteros y reales y deben poder codificar números de alta precisión. Los trucos de manipulación de bits y el conocimiento de las funciones de biblioteca para la aritmética básica de números serían muy útiles.
Teoría de números: Conocer algunos de estos conceptos ahorraría mucho tiempo y esfuerzo a la hora de programar en los concursos.
- Exponenciación modular
- Inverso multiplicativo modular
- Prueba de primalidad | Juego 2 (Método Fermat)
- Función totiente de Euler
- Tamiz de Eratóstenes
- Casco convexo
- Algoritmos euclidianos básicos y extendidos
- Tamiz segmentado
- Teorema del resto chino
- Teorema de Lucas
Combinatoria: aunque directamente puede no parecer importante, la combinatoria es importante para estimar la complejidad asintótica de los algoritmos.
Algoritmos Geométricos
- Casco convexo
- Escaneo de graham
- Intersección de línea
- Exponenciación matricial y esto
- Construcción en línea de casco convexo 3-D
- Algoritmo de Bentley Ottmann para enumerar todos los puntos de intersección de n segmentos de línea
- Técnica de calibradores giratorios
- Área/Perímetro de Unión de Rectángulos
- Par de puntos más cercano
- Área de Unión de Círculos
- Triangulación de Delaunay de n puntos
- Diagramas de Voronoi de n puntos usando el algoritmo de Fortune
- Punto en un problema de polígono
Algoritmos de flujo de red
- Implementación de Maxflow Ford Furkerson Algo y Edmond Karp
- corte mínimo
- Problema de matrimonio estable
- Algoritmo de Dinic para flujo máximo y wiki
- Problema de flujo de costo mínimo
- Algoritmo de ruta sucesiva más corta
- Algoritmo de cancelación de ciclo
- Coincidencia bipartita ponderada máxima (algoritmo de Kuhn Munkres/método húngaro)
- Algoritmo de corte mínimo de Stoer Wagner
- Coincidencia máxima en gráfico general (Blossom Shrinking)
- Árboles Gomory-Hu
- Problema del cartero chino (consulte esto también)
- Algoritmo Hopcroft-Karp para coincidencia máxima
Todos los artículos sobre algoritmos geométricos
Cosas más avanzadas
Algoritmos de bits , Algoritmos aleatorios , Rama y límite , Algoritmos matemáticos , Descomposición ligera pesada , Búsqueda A*
Artículos informativos que te pueden gustar leer
- Una lista impresionante para la programación competitiva – Codeforces
- ¿Cuáles son los algoritmos necesarios para resolver todos los problemas de C++ en Concursos? – Quora
- Los mejores libros y sitios para prepararse para ACM-ICPC – Quora
- Concurso Introducción a la Programación – Stanford.edu
- Final Mundial Problemas de ACM-ICPC – icpc.kattis
Referencias:
Plan de estudios del campamento de programación
Este artículo es una contribución de Vishwesh Shrimali en asociación con Team GeeksforGeeks . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto, si falta o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA