¿Cuál es una buena manera de ordenar temas en términos de qué aprender primero para la programación competitiva?
No hay una respuesta unánime a su pregunta. Eso es porque lo que funcionó para mí podría no funcionar para usted y viceversa. Significa que mi sugerencia probablemente no sea la mejor para usted y debería verla solo como una guía, pero no como la verdad absoluta.
El orden de las materias por tema que me parece más didáctico es el siguiente:
- ¿Cuál es el mejor libro para ayudar a entender la programación práctica orientada a objetos?
- Cómo resolver este problema con un árbol de segmentos o BIT
- ¿Cómo abordar este problema gráfico? ¿Es NP-completo?
- ¿Es posible desarrollar un algoritmo que pueda hacer predicciones perfectas en el mercado de valores?
- ¿Cuál es la mejor manera de usar la notación O grande para determinar la tasa de crecimiento del tiempo de ejecución de un algoritmo?
Introducción: búsqueda binaria, análisis de complejidad de algoritmos, trucos geniales de C ++ para usar en un concurso de programación, algoritmos de clasificación (cuadrático, lineal y lineal) y búsqueda ternaria.
Matemáticas: Encuentre todos los divisores en tiempo logarítmico, factorización en tiempo logarítmico, tamiz de Eratóstenes, propiedades básicas aritméticas modulares, búsqueda inversa utilizando algoritmo euclidiano extendido, pequeño teorema de Fermat, exponenciación en tiempo logarítmico (iterativo, recursivo, modular y con matrices), utilizando exponenciación matricial para resolver ecuaciones de recurrencia lineal en tiempo logarítmico, teorema del resto chino y FFT.
Estructuras de datos: Cola, pila, deque, cola prioritaria, std :: set, std :: map, std :: pair, union find, árbol indexado binario, árbol de segmentos, descomposición sqrt y treap.
Algoritmos de gráficos: DFS, BFS, usando BFS para resolver SSSP en un gráfico no dirigido, usando BFS para encontrar el diámetro del árbol y su centro, encontrar componentes conectados, detectar ciclos, relleno de inundación, clasificación topológica, encontrar puntos de articulación y puentes, algoritmo de Prim, Algoritmo de Kosaraju, problema 2-SAT, algoritmo de Kruskal, algoritmo de Prim, algoritmo de Bellman-Ford, algoritmo de Dijkstra, SSSP en DAG, algoritmo de Floyd-Warshall, ancestro común más bajo Método de Ford-Fulkerson, algoritmo de Edmonds-Karp, algoritmo de Dinic, cobertura mínima del borde, cobertura mínima de vértice, conjunto independiente máximo y problema de coincidencia máxima utilizando el algoritmo Hopcroft-Karp.
Paradigmas: dos punteros, retroceso, divide y vencerás, algoritmos codiciosos, problema de selección de actividad, programación dinámica, búsqueda del término n-ésimo de Fibonacci en tiempo lineal, problema de cambio de monedas, problema de mochila, problema de vendedor ambulante, encuentro en el medio y optimizaciones de programación dinámica.
Geometría: Puntos, vectores, tuplas, polígonos, orientación de puntos (en sentido horario o antihorario), verificar si un polígono es convexo, verificar si un punto está dentro de un polígono en tiempo logarítmico, transformaciones lineales y algoritmos de barrido de línea.
Cadenas: algoritmo Rabin-Karp, prueba la estructura de datos, el algoritmo de Manacher, la función Z y el algoritmo Z, Algoritmo KMP, algoritmo Aho-Corasick y árbol de sufijos.
Es una idea terrible centrarse en un tema y estudiarlo hasta dominar cada tema. El algoritmo de Graph, por ejemplo, es un tema que dura toda la vida. Nunca lo dominarás por completo en el corto plazo y, por lo tanto, nunca comenzarás a estudiar geometría computacional (por ejemplo).
La mejor idea es estudiar un poco cada tema y cambiar el tema después de algunos días. El libro Competitive Programming 3 ofrece una buena sugerencia de un curso introductorio de 13 semanas. Cada semana cubre uno o dos temas.
- Wk1: Introducción
- Wk2: Estructuras de datos y bibliotecas
- Wk3: Búsqueda completa, dividir y conquistar, codicioso
- Wk4: Programación dinámica 1 (Ideas básicas)
- Wk5: Programación dinámica 2 (más técnicas)
- Wk6: Concurso de equipo de mitad de semestre
- Wk7: Gráfico 1 (flujo de red)
- Wk8: Gráfico 2 (Coincidencia)
- Wk9: Matemáticas (descripción general)
- Wk10: Procesamiento de cadenas (habilidades básicas, matriz de sufijos)
- Wk11: Geometría Computacional
- Wk12: Temas más avanzados
- Wk13: Final Team Contest
Tenga en cuenta que Steve Halim y Felix Halim (los autores) eligieron un orden diferente para su sugerencia de curso. No es un problema, porque todo es solo una guía para usted.
