_{BEGINNER → EXPERT}

CP Roadmap

Competitive Programming · 11 Levels · Track Your Progress

⚪ Core topic   ·   🟢 Addvance   ·   🔴 Low CP priority

---

Language & STL Foundations  0/29

🎯 Goal: Be comfortable writing small programs without overthinking

C++ Basics

• ⚪ Variable declarations
• ⚪ Data types
• ⚪ Control flow (if-else, switch)
• ⚪ Loops (for, while)
• ⚪ Functions
• ⚪ Input / Output (cin, cout)
• ⚪ Header files
• ⚪ Namespace management
• 🟢 References & pointers
• 🟢 Pass by value vs reference
• 🟢 Struct & class basics
• 🟢 Lambda functions
• 🔴 OOP / Inheritance
• 🔴 Advanced templates

STL Basics

• ⚪ Vector
• ⚪ Queue
• ⚪ Stack
• ⚪ Deque
• ⚪ Priority queue
• ⚪ Set / Multiset
• ⚪ Map / Multimap
• ⚪ Iterators
• ⚪ sort, find, count algorithms
• 🟢 unordered_map / unordered_set
• 🟢 pair & tuple
• 🟢 lower_bound / upper_bound
• 🟢 next_permutation
• 🟢 accumulate / partial_sum
• 🔴 list — STL linked list

Complexity & I/O  0/17

🎯 Goal: Understand exactly how fast your code runs

Complexity Theory

• ⚪ Big O notation
• ⚪ Time complexity estimation
• ⚪ Space complexity
• ⚪ Amortized analysis
• ⚪ Constant factor optimization
• 🟢 Recognizing O from loop structure
• 🟢 Recursion tree analysis
• 🔴 Omega notation
• 🔴 Theta notation

Practical Limits

• ⚪ Reading input constraints
• ⚪ Memory limitations
• ⚪ Stack overflow prevention
• ⚪ Fast I/O (ios_base::sync)
• 🟢 printf / scanf vs cin speed
• 🟢 Reading until EOF
• 🟢 10^8 ops/sec rule of thumb
• 🟢 Integer overflow — use long long

Basic Data Structures  0/18

🎯 Goal: Understand how data is stored and accessed efficiently

Linear Structures

• ⚪ Static arrays
• ⚪ Dynamic arrays
• ⚪ String manipulation
• ⚪ Bit manipulation
• 🟢 Prefix sums
• 🟢 Difference arrays
• 🟢 Sparse table
• 🔴 Linked lists
• 🔴 Circular buffers

Hashing

• ⚪ Hash functions
• ⚪ Hash tables
• ⚪ Collision resolution
• ⚪ Rolling hash
• ⚪ Custom hash
• 🟢 Polynomial hashing
• 🟢 Anti-hack hash (random seed)
• 🔴 Open addressing (theory)
• 🔴 Chaining vs open addressing theory

Sorting & Searching  0/18

🎯 Goal: Master searching & sorting — a CORE CP skill

Sorting Algorithms

• ⚪ Merge sort
• ⚪ Quick sort
• ⚪ Heap sort
• ⚪ Counting sort
• 🟢 Radix sort
• 🟢 Custom comparators
• 🟢 Inversion count via merge sort
• 🔴 Bubble sort
• 🔴 Insertion sort

Searching Techniques

• ⚪ Binary search
• ⚪ Binary search on answer
• ⚪ Ternary search
• ⚪ Two pointers
• ⚪ Meet in the middle
• 🟢 Sliding window
• 🟢 Fractional binary search
• 🟢 Parallel binary search
• 🔴 Linear search

Number Theory & Math  0/20

🎯 Goal: Solve math-heavy competitive programming problems

Basics

• ⚪ Prime factorization
• ⚪ Sieve of Eratosthenes
• ⚪ GCD
• ⚪ LCM
• ⚪ Modular arithmetic
• ⚪ Fermat's Little Theorem
• 🟢 Linear sieve
• 🟢 Fast exponentiation (binary exp)
• 🟢 nCr mod p — combinatorics
• 🟢 Pascal's triangle

Advanced

• ⚪ Modular inverse
• ⚪ Euler Totient Function
• ⚪ Extended Euclidean Algorithm
• ⚪ Chinese Remainder Theorem
• ⚪ Primality testing
• 🟢 Miller-Rabin primality test
• 🟢 Inclusion-exclusion principle
• 🟢 Game theory — Sprague-Grundy
• 🔴 Discrete logarithm
• 🔴 Pollard's rho factorization

Dynamic Programming  0/20

🎯 Goal: Learn to break hard problems into states

Foundations

• ⚪ Overlapping subproblems
• ⚪ Optimal substructure
• ⚪ Memoization
• ⚪ Tabulation
• ⚪ State definition
• ⚪ Base cases
• 🟢 DP on intervals
• 🟢 DP with monotone queue
• 🟢 Divide & conquer DP optimization
• 🟢 Convex Hull Trick (CHT)

Advanced DP

• ⚪ Digit DP
• ⚪ Bitmask DP
• ⚪ Tree DP
• ⚪ Knapsack variants
• ⚪ LCS
• ⚪ Matrix exponentiation
• 🟢 LIS — O(n log n)
• 🟢 SOS DP — Sum over subsets
• 🟢 Profile DP
• 🟢 DP on DAGs

Graph Theory  0/35

🎯 Goal: Master graph-based problems at every difficulty

Graph Basics

• ⚪ Adjacency matrix
• ⚪ Adjacency list
• ⚪ Edge list
• ⚪ DFS
• ⚪ BFS
• 🟢 Flood fill
• 🟢 Cycle detection
• 🟢 Bipartite check
• 🟢 0-1 BFS
• 🟢 Multi-source BFS

Shortest Path & MST

• ⚪ Dijkstra
• ⚪ Bellman-Ford
• ⚪ Floyd-Warshall
• ⚪ Prim's algorithm
• ⚪ Kruskal's algorithm
• 🟢 SPFA (queue Bellman-Ford)
• 🔴 Johnson's algorithm

Advanced Graph

• ⚪ Topological sort
• ⚪ Strongly connected components (Tarjan/Kosaraju)
• ⚪ Articulation points
• ⚪ Bridges
• ⚪ LCA
• ⚪ Heavy-light decomposition
• 🟢 Euler path / circuit
• 🟢 2-SAT
• 🟢 Functional graph
• 🟢 Virtual tree

Flow & Matching

• ⚪ Max Flow / Min Cut
• ⚪ Dinic's algorithm
• ⚪ Bipartite matching
• ⚪ Hopcroft-Karp
• 🟢 Min-cost max flow
• 🟢 Hungarian algorithm
• 🔴 Ford-Fulkerson — use Dinic's instead
• 🔴 Edmonds-Karp — use Dinic's instead

Advanced Data Structures  0/18

🎯 Goal: Solve high-rated Codeforces problems

Segment Structures

• ⚪ Segment tree
• ⚪ Lazy propagation
• ⚪ Fenwick tree (BIT)
• ⚪ Range minimum query
• 🟢 Merge sort tree
• 🟢 Segment tree beats
• 🟢 2D Fenwick tree
• 🟢 Persistent segment tree

Advanced Trees

• ⚪ Disjoint Set Union (DSU)
• ⚪ Treap
• ⚪ Persistent DS
• ⚪ Centroid decomposition
• 🟢 DSU on tree — small-to-large
• 🟢 Sqrt decomposition
• 🟢 Mo's algorithm
• 🟢 Offline queries
• 🔴 Link-cut trees
• 🔴 Treap — use policy tree instead

Strings & Geometry  0/23

🎯 Goal: Reach Specialist-level mastery

String Algorithms

• ⚪ KMP
• ⚪ Z Algorithm
• ⚪ Rabin-Karp
• ⚪ Manacher's algorithm
• ⚪ Aho-Corasick
• ⚪ Suffix Array
• ⚪ Trie
• 🟢 Suffix Automaton (SAM)
• 🟢 Palindromic tree (Eertree)
• 🟢 Lyndon factorization
• 🔴 Suffix Tree — use SA+LCP instead
• 🔴 Lyndon factorization (rare in contests)

Geometry

• ⚪ Points & vectors
• ⚪ Line intersection
• ⚪ Polygon area
• ⚪ Convex hull
• ⚪ Sweep line
• 🟢 Cross product / dot product
• 🟢 Point in polygon
• 🟢 Rotating calipers
• 🟢 Half-plane intersection
• 🔴 Circle intersection
• 🔴 Half-plane intersection — niche

Greedy & Proof Techniques  0/18

🎯 Goal: Think mathematically and prove your solutions

Greedy Algorithms

• ⚪ Activity selection
• ⚪ Interval scheduling
• ⚪ Fractional knapsack
• ⚪ Change making
• 🟢 Greedy on graphs
• 🟢 Earliest deadline first
• 🟢 Scheduling problems
• 🔴 Huffman coding
• 🔴 Matroid theory

Proof Techniques

• ⚪ Exchange argument
• ⚪ Stay ahead
• ⚪ Induction
• ⚪ Contradiction
• 🟢 Invariant method
• 🟢 Monovariant
• 🟢 Pigeonhole principle
• 🟢 Double counting
• 🔴 Matroid theory — academic only

CP Meta-Skills (Bonus)  0/13

🎯 Goal: Often overlooked — separates good from great

Contest Strategy

• 🟢 Problem reading speed
• 🟢 Identifying problem type quickly
• 🟢 Time allocation per problem
• 🟢 Stress testing
• 🟢 Debugging under time pressure
• 🟢 Penalty awareness — CF scoring

Misc. Techniques

• 🟢 Coordinate compression
• 🟢 Offline processing
• 🟢 Randomization & heuristics
• 🟢 Constructive algorithms
• 🟢 Simulation problems
• 🟢 Interactive problems
• 🟢 Ternary search on unimodal functions

---