¿Cuáles son los algoritmos necesarios para resolver todos los problemas (usando C ++) en cualquier concurso de codificación competitivo?

Matemáticas:

(a) Teoría de los números

  1. Generación de números primos (tamiz, tamiz segmentado)
  2. Teorema de Euler Totient
  3. Teorema de Fermat
  4. HCF y LCM (Euclides)
  5. Ecuaciones lineales de diofantinas (Euclides extendidos)
  6. Aritmética de módulo (suma, multiplicación, sustracción, inversa modular)
  7. Hallazgo del ciclo (Floyd Algo y Brent Algo)
  8. Factorización entera (División de prueba, método Pollard Rho)
  9. Teorema de Lucas (simple y avanzado)
  10. Teorema del resto chino
  11. Teorema de Wilson
  12. Miller – Rabin Primality Testing
  13. Números perfectos
  14. Conjetura de Goldbach

(b) Probabilidad

  1. Probabilidad básica y probabilidad condicional
  2. Variables aleatorias
  3. Funciones generadoras de probabilidad
  4. Expectativa
  5. Distribución de probabilidad [Binomial, Poisson, Normal, Bernoulli]

(c) Contando

  1. Principio de casillero
  2. Exclusión inclusión
  3. Números especiales [Stirling, Fibonacci, catalán, euleriano, armónico, Bernoulli]
  4. Conteo de polia
  5. Lema de Burnside

(d) Ciclos de permutación

(e) Álgebra lineal

  1. Suma y resta de matrices
  2. Multiplicación (algoritmo de Strassen), exponenciación logarítmica
  3. Transformaciones de matriz [Transposición, rotación de matriz, que representa transformaciones lineales usando matriz]
  4. Determinante, rango e inverso de la matriz [Eliminación Gaussiana, Eliminación Gauss Jordan]
  5. Sistema de resolución de ecuaciones lineales
  6. Matriz de exponenciación para resolver recurrencias
  7. Eigenvalores y vector Eigen
  8. Raíces de un polinomio [Factorización prima de un polinomio, raíces enteras de un polinomio]
  9. Interpolación de Lagrange

(e) Teoría del juego

  1. Conceptos básicos y juego de Nim [Teorema de Grundy, número de Grundy]
  2. Hackenbush

(f) Teoría del grupo

  1. Lema de Burnside
  2. Teorema de Polya

Gráficos:

(a) Representación gráfica

  1. Matriz de adyacencia
  2. Lista de adyacencia
  3. Matriz de incidencia
  4. Lista de borde

(b) Tipos de gráficos

  1. Dirigido
  2. No dirigido
  3. Ponderado
  4. No ponderado
  5. Plano
  6. Hamilton
  7. Euler
  8. Gráficos especiales

(c) DFS y su aplicación

  1. Detección de ciclo
  2. Puntos de articulación
  3. Puentes
  4. Componente fuertemente conectado
  5. Componente conectado
  6. Encontrar el camino
  7. Resolviendo el laberinto
  8. Biconnectividad en el gráfico
  9. Clasificación topológica
  10. Comprobación bipartita
  11. Prueba de planaridad
  12. Algoritmo de relleno de inundación

(d) BFS y su aplicación

  1. Camino más corto (número de bordes)
  2. Comprobación bipartita
  3. Componentes conectados

(d) Árbol de expansión mínima

  1. Algoritmo de Prim
  2. Algoritmo de Kruskal

(d) Ruta más corta de fuente única

  1. Dijkstra
  2. Bellman Ford

(e) Todos los pares de la ruta más corta

  1. Algoritmo de Floyd Warshall

(f) Euler Tour

(g) Flujo

  1. Ford-Fulkerson [PFS, DFS, BFS]
  2. Algoritmo de Dinic
  3. Costo mínimo: flujo máximo [Algo de ruta más corto sucesivo, algoritmo de cancelación de ciclo]
  4. BPM ponderado máximo [algoritmo Kuhn Munkres / Método húngaro]
  5. Stoer Wagner Min-Cut Algo
  6. Hop-Kraft BPM
  7. Algoritmo de reducción de Edmond Blossom

(h) Otros temas importantes sobre gráficos

  1. 2-SAT,
  2. LCA
  3. Máxima coincidencia de cardinalidad
  4. Flujo de aplicación
  5. Min Path Cover Over Dag
  6. Trayectoria independiente de borde independiente
  7. Cubierta mínima de vértice
  8. Máximo conjunto independiente

Estructuras de datos:

  1. Matrices
  2. Lista enlazada
  3. Árboles (árbol binario y árbol de búsqueda binaria)
  4. Pilas
  5. Colas
  6. Montón
  7. Tablas Hash
  8. Estructuras de datos de conjunto disjunto
  9. Trie
  10. Árbol de segmento
  11. Árbol de índice binario
  12. Treap

Búsqueda y clasificación:

  1. Búsqueda lineal
  2. Búsqueda binaria
  3. Búsqueda ternaria
  4. Selección Ordenar
  5. Ordenamiento de burbuja
  6. Tipo de inserción
  7. Ordenar fusión
  8. Ordenación rápida
  9. Selección rápida
  10. Heap Sort
  11. Radix Sort
  12. Contando Ordenar

Codicioso:
Problemas clásicos de codicia y concepto
ejemplo: mochila fraccional

Programación dinámica Problemas clásicos

  1. Editar distancia
  2. Rompecabezas de caída de huevos
  3. Mochila entera
  4. Conjunto independiente más grande
  5. La secuencia biotónica más larga
  6. Subsecuencia común más larga
  7. Subcadena común más larga
  8. Subsecuencia creciente más larga
  9. La secuencia palindrómica más larga
  10. Subcadena palindrómica más larga
  11. Subcadena más larga sin repetir carácter
  12. Multiplicación de cadena matricial
  13. Submatriz cuadrada de tamaño máximo con una
  14. Longitud máxima de pares de cadenas
  15. Subsecuencia creciente de suma máxima
  16. Árbol de búsqueda binario óptimo
  17. Problema de partición de palíndromo
  18. Establecer problema de partición
  19. Subconjunto Suma
  20. Word Wrap Problem

Programación dinámica Técnicas avanzadas

  1. DP + Tree
  2. DP + enmascaramiento de bits
  3. DP + Búsqueda binaria
  4. DP + Graph
  5. DP + exponenciación matricial
  6. DP + espacio de probabilidad
  7. DP + Recurrencia de grietas

Divide y vencerás
Problemas y conceptos clásicos

  1. Ordenar fusión
  2. Puntos de par más cercanos

Otras técnicas de diseño de algoritmos:

  1. BackTracking
  2. Hombre en medio
  3. Newton-Raphson para llegar al punto fijo
  4. Fuerza bruta
  5. Algo constructivo
  6. Ventana deslizante
  7. Clasificación de panqueques

Recursos:
Estructuras de datos y algoritmo:
Tutoriales de algoritmos
Estructuras de datos y algoritmos
Inverso Multiplicativo Modular
Descomposición ligera pesada
Tutorial: Actualizaciones de rango en Fenwick Tree por Amey Dharwadker en Concursos de programación
visualizar estructuras de datos y algoritmos a través de animaciones
Truco del concurso de codificación: reunirse en el medio
Introducción a la programación dinámica
Problemas de práctica de programación dinámica
Resolución de recurrencia lineal para concurso de programación
Tutorial sobre Trie y problemas de ejemplo de Lalit Kundu en Threads @ IIIT Hyderabad
Árboles indexados binarios con algún ejemplo resuelto.
Problemas de programación dinámica con bitmasking
Permítanos codificar: Segmentar árboles

C ++:
Tutorial de programación de C ++
Contenedores – Referencia de C ++
Guía del programador de la biblioteca de plantillas estándar

Actualizado con algunos enlaces más.

Related Content

¿Es posible cuantificar la experiencia laboral?

Mientras codifica problemas algorítmicos durante una entrevista usando C, ¿está bien asumir funciones de biblioteca?

¿Cuáles son todas las estructuras de datos que conoce? ¿Cuál de estos usas con frecuencia? Agrúpelos en "Básico" y "Avanzado".

¿Cuáles son los mejores algoritmos para el análisis de sentimientos?

¿Podría un algoritmo informático convertirse en el presidente de los Estados Unidos?


Aquí está mi lista de ayudantes. Enumera la mayoría de los algoritmos / conceptos necesarios. Algunos elementos no son algoritmos (por ejemplo, falsos, estados / preocupaciones) y pequeñas repeticiones.

Pero 1 consejo final:

Inicialmente, se le presta gran atención a las habilidades de pensamiento más que al conocimiento. Esto es útil tanto para las competiciones como para tu futuro. Para hacerlo, asegúrese de ser tan bueno en adhocks, donde no se requieren algoritmos, solo pensamiento puro.

Una forma de hacerlo es enfocarse con TC Div2 y CodeForces Div2. En cada uno, avance en el problema nivel por nivel. Ej. Master Div2-250, luego pasar a Div2-500

Hussein Elsayed

Las estructuras de datos y algoritmos más utilizados son:

  1. Búsqueda binaria
  2. Ordenación rápida
  3. Ordenar fusión
  4. Matriz de sufijo
  5. Algoritmo de Knuth-Morris-Pratt (KMP)
  6. Algoritmo Rabin-Karp
  7. Intentos
  8. Profundidad primer recorrido de un gráfico
  9. Amplitud Primero transversal de un gráfico
  10. Algoritmo de Dijkstra
  11. Árbol indexado binario
  12. Árbol de segmentos (con propagación perezosa)
  13. Árbol de segmento persistente
  14. Algoritmo Z
  15. Algoritmo de Floyd Warshall
  16. Tabla dispersa (RMQ)
  17. Heap / Priority Queue / Heapsort
  18. Inverso Multiplicativo Modular
  19. nCr% M
  20. Sufijo Automaton
  21. Antepasado común más bajo
  22. Contando inversiones
  23. Algoritmo Extendido de Euclides
  24. Árbol de sufijo
  25. Programación dinámica
  26. Estructuras de datos básicos
  27. Exponenciación logarítmica
  28. Gráficos
  29. Árbol de expansión mínima
  30. Factorización Prime eficiente
  31. Combinatoria
  32. Conjunto de búsqueda / disjunto de unión
  33. Problema de mochila
  34. Algoritmo de coincidencia de cadenas Aho-Corasick
  35. Componentes fuertemente conectados
  36. Algoritmo de Bellman Ford
  37. Descomposición de luz pesada
  38. Casco convexo
  39. Implementación del algoritmo Jarvis
  40. Intersección de línea
  41. Tamiz de Erastothenes
  42. Árbol de intervalo
  43. Contando Ordenar
  44. Las probabilidades
  45. Matriz de exponenciación
  46. Flujo de red
  47. Flujo máximo (Ford-Fulkerson)
  48. Árbol Kd:
  49. Deque
  50. Árbol de búsqueda binaria
  51. Selección rápida
  52. Treap / Árbol cartesiano
  53. Teoría de juego
  54. STL (C ++)
  55. Máxima coincidencia bipartita
  56. Algoritmo de Manacher
  57. Prueba de primalidad de Miller-Rabin
  58. Problema de matrimonio estable
  59. Algoritmo Húngaro
  60. Algoritmo de línea de barrido
  61. LCP
  62. Eliminación gaussiana
  63. Factorización de Rho Pollard Integer
  64. Clasificación topológica
  65. Detección de ciclos en un gráfico: dirigido, no dirigido
  66. Geometría
  67. Retroceso
  68. Caminos Eulerianos y Hamiltonianos
  69. Coloración gráfica
  70. Encontrarse en el medio
  71. Entero de precisión arbitraria (BigInt)
  72. Radix Sort
  73. Clasificación de cubo
  74. Algoritmo de Johnson
  75. Máxima coincidencia en un gráfico general
  76. Recursividad
  77. Principio de inclusión y exclusión
  78. Compresión coordinada
  79. Descomposición cuadrada
  80. Árbol de corte de enlace
  81. Función totiente de Euler
  82. Lema de Burnside
  83. Editar / Distancia Levenshtein
  84. Branch and Bound
  85. Matemáticas para la programación competitiva
  86. Algoritmo de Mo

Respuesta original: la respuesta de Pratyush Khare a ¿Cuáles son los 10 algoritmos que uno debe conocer para resolver la mayoría de los desafíos / acertijos de algoritmos?

Jordan Alexander

Antes de hacer esta pregunta, debe comprender esto: en la programación competitiva, menos del 10% de los algoritmos se pueden usar para resolver más del 90% de los problemas.

Si eres realmente bueno en algoritmos básicos (DP, gráfico, estructuras de datos (pila, cola, montón, árbol de segmentos, árbol de fenwick), matemática básica), puedes hacerlo rojo en Codeforces / Topcoder. Debería aprender más solo si está realmente interesado en el algoritmo, en cuyo caso no creo que deba hacer esta pregunta en primer lugar.

Dominar cada algoritmo lleva tiempo. Estoy en CP por alrededor de 8 años, rojo en Codeforces y todavía no entiendo algunos algoritmos / no puedo implementar algunos. Mi consejo es que no necesita todas esas enormes listas de algoritmos. Simplemente aprenda cosas nuevas cuando las vea, o cuando se sienta interesado en ciertos temas.

Thanh Trung Nguyen

Para agregar a esta lista, saqué algunos del blog CodeForces y un Google Doc que encontré en línea de Bohdan Pryshchenko.

Buenos recursos de publicaciones de blog sobre algoritmos y estructuras de datos – Codeforces

Tiene literalmente todos los tutoriales en blogs de CodeForces. Realmente espero que esto ayude! Incluye:

  • C ++ STL
  • Procesamiento de cadenas
  • Estructuras de datos
  • Teoría de juego
  • Programación dinámica
  • Geometría
  • Gráficos
  • Ordenar y buscar
  • Teoría de los números
  • Misceláneos

Google Doc de Bohdan Pryshchenko: (escrito por Poojit Sharma)

Programa de campamento de programación

Este es un documento realmente bueno con problemas de práctica, descripción general de todos los temas para la programación de concursos.

Finalmente, la lista extra larga en CodeChef que tiene tutoriales, problemas de práctica y más 🙂

CodeChef estructuras de datos y algoritmos

Un grano de sal con estas listas: la práctica es clave. La comprensión es la clave. Por lo tanto, asegúrese de comprender muy bien los algoritmos antes de practicar y siempre implemente para mejorar su comprensión.

¡Buena suerte!

Vaibhav Savla

Hola chicos, echen un vistazo a este nuevo curso sobre resolución de problemas de Codechef. Introducción a la programación competitiva en Codechef – Parte 2 – Unacademia

Fardous Ahmed 
  int main ()
 {
   // La solución va aquí
 }
Jordan Alexander

Conocer el algoritmo y cómo funciona no siempre es suficiente para resolver problemas requiere conocerlo … pero practicar tanto como puedas sería mejor …

Comience a aprender algoritmos, impleméntelos usando su idioma preferido, comience a resolver problemas y practíquelos para que obtenga muchas habilidades que siempre son necesarias e importantes para la programación competitiva.

Tampoco es algo relacionado con el lenguaje de programación … siempre y cuando conozca el algoritmo y cómo funciona, puede implementarlo usando cualquier lenguaje de programación, siempre que pueda programar con él.

Bhavik Dhandhalya

Siga este @Google Translate y luego estudie paso a paso e implemente todos los algoritmos. Podrás descifrar cualquier concurso de codificación competitivo 🙂
Happy Coding 🙂

Gaurav Bajpai

Consulte este enlace
Estructuras de datos y algoritmos
tiene una lista de todas las estructuras de datos y algoritmos relevantes también
Hay tutoriales, y practican problemas.
aunque es una lista larga

Thanh Trung Nguyen

Cree que nunca has terminado de aprender algoritmos para la programación competitiva. Aquí hay una pequeña lista para ti.
Listado de algoritmos
quizás también quieras pasar por esto
Lista de estructuras de datos.

La mejor de las suertes.

Mostafa Saad Ibrahim

Puede encontrar una lista muy completa de algoritmos aquí Estructuras de datos y algoritmos

Fardous Ahmed

Como consejo lea “programación de perlas”
Después de esto, desarrollarás un enfoque diferente para resolver los problemas y te ayudará a elegir el mejor entre ellos.

Thanh Trung Nguyen

More Interesting

¿Existe un algoritmo para encontrar un árbol con una longitud de ruta mínima ponderada para un gráfico conectado genérico?

Programación competitiva: dado un polígono y tres cuadrados congruentes alineados con el eje, ¿puede determinar en tiempo polinómico si el polígono puede cubrirse por completo de manera que los tres cuadrados, que pueden superponerse, cubran una cantidad igual de área en el polígono?

¿Cuál es la operación que tiene la constante más pequeña?

¿Cuál es la forma más compleja de reducir 1 + 1?

¿Cuáles serían las implicaciones si pudiera demostrar que he descifrado el algoritmo criptográfico RSA en tiempo polinómico? ¿Qué debería hacer después?

¿Es este algoritmo para la predicción de acciones bueno o lógico? ¿Es original?

¿Se ha completado Javascript Turing?

¿Cuáles son los algoritmos básicos de aprendizaje automático que todo principiante debe saber antes de comenzar el aprendizaje automático?

¿Existen buenos libros o recursos para resolver problemas y algoritmos en C #, para la preparación de entrevistas SDET?

Descubrí el algoritmo de Dijkstra yo mismo. ¿Puedo decir que soy bueno en informática?

¿Cuál es una explicación intuitiva para el algoritmo de maximización condicional de expectativa (ECM)?

¿Tiene sentido saltar directamente a las máquinas de vectores de soporte en lugar de probar con otros algoritmos lineales, primero, en el aprendizaje automático?

Cómo maximizar el XOR entre un número constante y múltiples matrices con un solo trie si los elementos de la matriz pueden ser comunes

¿Qué significa "adherencia del brazo" en los algoritmos de programación de E / S?

¿Qué significa 'estructuras de datos de dimensión única' en programación?