Competitive Programming Fundamentals

12-05-2025

A curated collection of algorithms and techniques for competitive programming contests. Organized by topic for quick reference during problem-solving.

Data Structures

Range Query Structures

Specialized Structures

  • Disjoint Set Union
  • Trie
  • Monotonic Stack and Queue

Graph Algorithms

Shortest Paths

  • Dijkstra's Algorithm
  • Bellman-Ford
  • 0-1 BFS
  • Floyd-Warshall

Tree Algorithms

  • Binary Lifting
  • Euler Tour Technique
  • Tree DP and Rerooting

Advanced Graph Theory

  • Strongly Connected Components
  • Bridges and Articulation Points
  • Topological Sort
  • Bipartite Matching
  • 2-SAT

Dynamic Programming

Optimization Techniques

  • DP Optimizations
  • Monotonic Deque Optimization

Common Patterns

  • Bitmask DP
  • Digit DP
  • Tree DP
  • DP on DAGs
  • Knapsack DP
  • Intervals DP

String Algorithms

Pattern Matching

  • KMP Algorithm
  • Z-Algorithm
  • Rolling Hash

Advanced Techniques

  • Suffix Array and LCP
  • Aho-Corasick
  • Manacher's Algorithm

Number Theory

Foundational

  • GCD and Extended Euclidean
  • Fast Exponentiation
  • Sieve of Eratosthenes
  • Modular Arithmetic

Advanced

  • Euler's Totient Function
  • Chinese Remainder Theorem
  • Matrix Exponentiation

Combinatorics

  • Binomial Coefficients
  • Catalan Numbers
  • Stars and Bars
  • Derangements

Problem-Solving Techniques

Search and Optimization

  • Binary Search on Answer
  • Ternary Search
  • Meet in the Middle

Array Techniques

  • Two Pointers
  • Sliding Window
  • Coordinate Compression

Other

  • Square Root Decomposition
  • Mo's Algorithm
  • Greedy Algorithms

Game Theory

  • Nim Game
  • Grundy Numbers
  • Minimax