Competitive_Programming

1. Foundations & Contest Skills

(Stuff that makes you fast and sane in contests)

• Competitive programming overview
• Programming contests formats & rules
• Contest strategy & practice tips
• Problem-solving mindset
• Reading problem statements efficiently
• Debugging under time pressure
• Using online judges (CSES, Codeforces, etc.)

---

2. Programming Language & Implementation Skills

(Mostly language-agnostic, often C++-focused)

• Input & output optimization
• Fast I/O techniques
• Working with integers & floating-point numbers
• Overflow & precision issues
• Shortening code (macros, typedefs, templates)
• Iterators & ranges
• Compiler optimizations
• Understanding generated assembly (optional but elite)

---

4. Time & Space Complexity

(Core survival knowledge)

• Time complexity rules
• Complexity classes
• Big-O / Big-Θ / Big-Ω
• Estimating efficiency
• Lower bounds
• Amortized analysis

---

5. Sorting & Searching

Sorting

• Sorting theory
• Bubble sort
• Merge sort
• Counting sort
• Comparison-based lower bounds
• Practical sorting tricks

Searching

• Binary search
• Binary search on answers
• Ternary search
• Searching optimal solutions

---

6. Data Structures

6.1 Basic Structures

• Arrays
• Dynamic arrays (vectors)
• Deques
• Stacks & queues

6.2 Ordered Structures

• Sets & multisets
• Maps
• Priority queues
• Policy-based data structures

6.3 Range Query Structures

• Prefix sums
• Binary Indexed Trees (Fenwick Trees)
• Segment Trees
• Lazy propagation
• Dynamic segment trees
• 2D segment trees

6.4 Advanced / Custom Structures

• Treaps
• Union-Find (Disjoint Set Union)
• Data structures inside nodes
• Merging data structures

---

8. Greedy Algorithms

• When greedy works / fails
• Coin problems
• Scheduling
• Tasks & deadlines
• Minimizing sums
• Data compression

---

7. Complete Search & Backtracking

• Generating subsets
• Generating permutations
• Recursive algorithms
• Backtracking
• Pruning search trees
• Heuristic pruning
• Meet in the middle

---

9. Dynamic Programming

Core DP Concepts

• Optimal substructure
• Overlapping subproblems
• Counting vs optimizing
• State design & transitions

Classic Problems

• Maximum subarray sum
• Coin problems
• Longest increasing subsequence
• Grid paths
• Knapsack problems
• Edit distance
• Counting tilings

Advanced DP

• DP over subsets
• DP on permutations
• DP on trees
• DP optimizations:
  • Convex Hull Trick
  • Divide & Conquer optimization
  • Knuth’s optimization

---

14. String Algorithms

Basic

• String terminology
• Trie structures
• DP on strings

Hashing

• Polynomial hashing
• Collision handling
• Applications

Pattern Matching

• Z-algorithm
• Prefix functions
• Suffix arrays
• LCP arrays
• Suffix automata
• Regular languages
• Pattern matching automata

---

10. Bit Manipulation & Bitmasking

• Bit representation
• Bit operations
• Bit optimizations
• Representing sets with bitmasks
• Bit-parallel algorithms
• Hamming distance
• Subset DP with bitmasks

---

11. Graph Algorithms

11.1 Graph Basics

• Graph terminology
• Adjacency lists & matrices

11.2 Graph Traversal

• Depth-first search (DFS)
• Breadth-first search (BFS)
• DFS trees

11.3 Shortest Paths

• Bellman–Ford
• Dijkstra
• Floyd–Warshall

11.4 Directed Graphs

• Topological sorting
• DAG dynamic programming
• Successor graphs
• Cycle detection

11.5 Connectivity

• Strongly connected components
• Kosaraju’s algorithm
• 2SAT problem
• Biconnectivity

11.6 Trees

• Tree traversal
• Tree diameters
• All longest paths
• Binary trees
• Tree queries
• Lowest common ancestor
• Subtrees & paths
• Offline tree algorithms

11.7 Spanning Trees

• Minimum spanning trees
• Kruskal’s algorithm
• Prim’s algorithm
• Union-Find structure

11.8 Paths & Circuits

• Eulerian paths
• Hamiltonian paths
• De Bruijn sequences
• Knight’s tours

11.9 Flow Algorithms

• Ford–Fulkerson
• Maximum flow
• Minimum cut
• Disjoint paths
• Maximum matchings
• Path covers
• Minimum cost flow

---

12. Range Query Techniques

• Static array queries
• Prefix sums
• RMQ
• Offline queries
• Parallel binary search
• Dynamic connectivity

---

3. Mathematics for Competitive Programming

3.1 Number Theory

• Primes & factorization
• Sieve of Eratosthenes
• GCD & Euclid’s algorithm
• Modular arithmetic
• Modular exponentiation
• Euler’s theorem
• Solving linear & modular equations

3.2 Combinatorics

• Binomial coefficients
• Catalan numbers
• Inclusion–exclusion principle
• Burnside’s lemma
• Cayley’s formula
• Counting permutations & subsets

3.3 Probability

• Events & probability calculations
• Random variables
• Expected values
• Markov chains
• Randomized algorithms

3.4 Linear Algebra & Matrices

• Matrix operations
• Linear recurrences
• Matrix exponentiation
• Gaussian elimination
• Graphs represented as matrices

3.5 Game Theory

• Game states
• Nim game
• Sprague–Grundy theorem

3.6 Fourier Transform

• Polynomial multiplication
• FFT algorithm
• Convolution

---

13. Geometry

Core Geometry

• Complex numbers
• Points & vectors
• Lines & segments
• Distance functions
• Polygon area

Advanced Geometry

• Sweep line algorithms
• Intersection detection
• Closest pair of points
• Convex hull

---

15. Advanced Techniques & Miscellaneous

• Two pointers method
• Sliding window minimum
• Nearest smaller elements
• Square root decomposition
• Mo’s algorithm
• Integer partitions
• Parallel binary search
• Dynamic trees
• Dynamic connectivity