Roadmaps › Placement
Competitive Programming Roadmap
From your first contest to a strong Codeforces rating — fast I/O, maths, advanced data structures and contest strategy.
Level: Intermediate → Advanced · Duration: 6–12 months
Step 1: Setup & language
C++ is the standard for CP because of speed and the STL.
Competitive programming rewards speed of thinking and of coding. C++ with the STL is the standard because it is fast and has every data structure built in.
- C++ syntax and STL containers
- A personal contest template
- The main contest platforms
Resources: C++ documentation · C++ roadmap · ▶ Competitive Programming Course
C++ & STL
vector, map, set, priority_queue, algorithms.
Knowing the STL by heart saves minutes in every contest.
- vector, pair, map, set, unordered_map
- priority_queue, deque, stack, queue
- sort, lower_bound, upper_bound, next_permutation
- long long and overflow
Resources: C++ cheat sheet
Fast I/O & templates
ios::sync_with_stdio(false), a clean template.
Slow input/output can turn a correct solution into Time Limit Exceeded.
- ios::sync_with_stdio(false); cin.tie(nullptr);
- Using '\n' instead of endl
- Macros and a reusable template
- Handling multiple test cases
Contest platforms
Codeforces, CodeChef, AtCoder, LeetCode contests.
Each platform has a style; Codeforces is the main rating ladder.
- Codeforces Div 1/2/3/4 rounds
- CodeChef Starters
- AtCoder Beginner Contests
- LeetCode weekly contests
Resources: Codify contests
Step 2: Complexity & constraints
Read n and know which algorithm is expected.
Constraints tell you the intended complexity before you think of an algorithm.
- Estimating operations
- Mapping constraints to algorithms
Resources: Big-O Complexity documentation · Notes: Big-O
Big-O analysis
Loops, recursion, amortised cost.
About 10⁸ simple operations run in one second.
- Loops and nested loops
- Recursion and the master theorem
- Amortised analysis
Constraints → algorithm
10⁵ means O(n log n), 20 means 2ⁿ.
n ≤ 20 hints at bitmasks, n ≤ 5000 at O(n²), n ≤ 2·10⁵ at O(n log n).
- Reading constraints first
- Memory limits (256 MB ≈ 6·10⁷ ints)
- Sum of n over test cases
Step 3: Basic techniques
The tools behind most Div 2 A–C problems.
Most Div 2 A–C problems need one of these ideas plus careful implementation.
- Sorting and greedy
- Prefix sums and two pointers
- Binary search
- Constructive thinking
Resources: DSA Patterns documentation
Sorting & greedy
Exchange arguments.
Sort, then choose greedily — and prove it with an exchange argument.
- Custom comparators
- Interval scheduling
- Proving greedy choices
Resources: Practice: Greedy problems · Notes: Greedy Algorithms
Prefix sums & two pointers
Range queries, windows.
Answer range questions in O(1) and scan windows in O(n).
- 1-D and 2-D prefix sums
- Difference arrays
- Two pointers and sliding windows
Resources: Practice: Arrays problems · Practice: Sliding Window problems
Binary search
On answers.
If "can we achieve X?" is monotonic, binary search the answer.
- lower_bound / upper_bound
- Binary search on the answer
- Avoiding off-by-one errors
Resources: Practice: Binary Search problems
Constructive & implementation
Careful coding, edge cases.
Some problems ask you to build an answer or simulate carefully.
- Finding patterns with small cases
- Careful edge-case handling
- Clean, simple code
Step 4: Mathematics
Number theory and combinatorics appear in every contest.
Maths appears in almost every round — especially number theory and counting.
- Number theory
- Combinatorics
- Bit tricks
- Probability
Resources: Notes: Number System Shortcuts
Number theory
GCD, sieve, modular arithmetic, fast power, inverses.
Primes, divisors and modular arithmetic.
- GCD/LCM and the Euclidean algorithm
- Sieve of Eratosthenes and factorisation
- Modular arithmetic and fast exponentiation
- Modular inverse (Fermat)
Combinatorics
nCr mod p, inclusion–exclusion.
Count arrangements without listing them.
- Factorials and nCr modulo a prime
- Inclusion–exclusion
- Stars and bars
Bit manipulation
XOR tricks, masks.
Bits give compact sets and clever XOR tricks.
- AND, OR, XOR, shifts
- Iterating over subsets
- Counting set bits (__builtin_popcount)
Resources: Practice: Bit Manipulation problems · Notes: Bit Manipulation
Probability & expected value (optional)
Linearity of expectation.
Expected value problems are common in harder rounds.
- Linearity of expectation
- Modular fractions (p · q⁻¹ mod M)
Step 5: Graphs
Model the problem as a graph.
Many problems become easy once you see the graph: cities and roads, states and moves, grids.
- Traversals
- Shortest paths and spanning trees
- DSU and DAGs
- Advanced graph algorithms
Resources: Notes: Graphs — BFS and DFS · Practice: Graphs problems
BFS, DFS & components
Grids, connectivity.
The two basic traversals solve a large share of graph problems.
- Adjacency lists
- Grid BFS
- Connected components and bipartite check
- Cycle detection
Shortest paths & MST
Dijkstra, Bellman–Ford, Kruskal.
Weighted graphs need specialised algorithms.
- Dijkstra with a priority queue
- 0-1 BFS, Bellman–Ford, Floyd–Warshall
- Kruskal and Prim
Resources: Notes: Shortest Paths and MST
DSU & topological sort
Union–find, DAGs.
DSU answers connectivity quickly; topological sort orders dependencies.
- Union–find with path compression
- Kahn's algorithm
- DP on DAGs
Advanced graphs (optional)
SCC, bridges, LCA with binary lifting.
Needed for Div 1 and higher ratings.
- Strongly connected components
- Bridges and articulation points
- LCA with binary lifting
Step 6: Dynamic programming
The hardest and most rewarding topic.
DP problems are the most common hard problems in contests. Practise defining states.
- Classic DP families
- Bitmask DP
- Tree DP
- Advanced optimisations
Resources: Notes: Dynamic Programming · Practice: Dynamic Programming problems
Classic DP
Knapsack, LIS, LCS, grid.
Master the standard patterns first.
- Knapsack variants
- LIS in O(n log n)
- LCS and edit distance
- Grid and interval DP
Bitmask DP
Subsets as states.
When n ≤ 20, a subset can be a state.
- dp[mask] and dp[mask][i]
- Travelling salesman style problems
- Sum over subsets
DP on trees
Subtree answers, rerooting.
Combine answers from children to compute the parent.
- Subtree DP
- Rerooting technique
- Tree diameter and matching
Digit DP & optimisations (optional)
Digit DP, convex hull trick.
Specialised techniques for high-rated problems.
- Digit DP for counting numbers
- Prefix sums inside DP
- Convex hull trick, divide-and-conquer DP
Step 7: Advanced data structures
Fast range queries and updates.
Range queries with updates need logarithmic structures.
- Segment trees
- Fenwick trees
- Sparse tables
- String structures
Resources: CP-Algorithms
Segment tree
Range queries, lazy propagation.
The most versatile range-query structure.
- Build, point update, range query
- Lazy propagation for range updates
- Merging custom node data
Fenwick tree
Prefix sums with updates.
A short, fast structure for prefix sums with updates.
- Point update, prefix query
- Counting inversions
- Range update with two BITs
Sparse table
O(1) range minimum.
Immutable arrays allow O(1) range minimum queries after O(n log n) build.
- Building the table
- Idempotent queries (min, max, gcd)
Trie & string algorithms (optional)
KMP, Z-function, hashing.
String problems use hashing and linear-time matching.
- Polynomial string hashing
- KMP prefix function and Z-function
- Tries and XOR tries
Resources: Notes: Trie
Step 8: Contest strategy
Rating comes from consistency.
Rating grows with regular contests and learning from every one of them.
- Practising under time pressure
- Learning from missed problems
- Debugging quickly
- Setting goals
Resources: Weekly contests
Virtual contests
Practise under time pressure.
Past contests in real time are the best practice.
- Weekly schedule
- Problem rating ladder (+200 above your level)
Upsolving
Solve the problems you missed after each contest.
The problems you couldn't solve teach you the most.
- Read editorials after trying
- Re-implement without looking
- Keep a notebook of tricks
Debugging fast
Stress testing with a brute force.
Wrong Answer on test 2 is common — find the bug systematically.
- Stress testing against a brute force
- Checking overflow and edge cases
- Assertions and small tests
Rating goals
Pupil → Specialist → Expert on Codeforces.
Clear goals keep you motivated.
- Codeforces: Pupil 1200, Specialist 1400, Expert 1600
- CodeChef stars
- ICPC team practice