Competitive Programming Tutorial
Learn Competitive Programming step by step: 63 lessons in 11 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started with Contests
- What Is Competitive Programming? Learn what competitive programming is: contest formats like ICPC, IOI, Codeforces and AtCoder, how judges grade code, how ratings work, and how to train well.
- Reading a Problem Statement Learn to read competitive programming statements: input and output format, constraints as hints, mapping n to the needed complexity, samples, and hidden traps.
- Python for Contests Use Python in contests: fast input idioms, reading ints and grids, joining output, the recursion limit, speed tips, and knowing when Python is too slow.
- Verdicts and Debugging Understand judge verdicts WA, RE, TLE, MLE and PE, reproduce failures with small hand tests, use assertions and printed state, and hunt off-by-one errors.
Contest Toolkit
- Templates and Habits Build a minimal Python contest template with fast input, small helper functions, clear names and no global mutable state, so your code stays short and readable.
- Estimating Time and Memory Estimate runtime and memory before coding: operations per second, Python constant factors, timing with perf_counter, list versus array memory, and choosing approaches.
- Stress Testing with a Brute Force Find bugs your samples miss: write a slow brute force, generate seeded random tests, compare answers automatically and shrink a failing case to its smallest form.
- Fast Input and Output in C++, Java and Python, and Reading from Files Make contest I/O fast and safe: C++ sync_with_stdio, scanf and custom readers, Java BufferedReader and FastReader, Python sys.stdin, plus file input and output on your own machine.
- Edge Cases and Common Pitfalls A checklist of the mistakes that cost contestants points: n = 1, empty input, overflow, negative numbers, division and modulo rules, duplicates and float comparison.
- Interactive Problems How interactive contest problems work: flushing, query limits, binary-search guessing and a local interactor you can test your solution against, with Python.
- PBDS and C++ Contest STL Tricks Use GNU policy-based data structures in contests: ordered set with find_by_order and order_of_key, hash tables with safe hashes, bitset shifts, plus a Python substitute.
Ad Hoc and Implementation
- Implementation Problems Learn to solve implementation problems: careful simulation, state machines, string and grid handling, and building a solution from small, separately verified pieces.
- Ad Hoc and Constructive Problems Learn how to attack ad hoc and constructive contest problems: find invariants, explore small cases by brute force, guess a pattern, then build and verify an answer.
- Simulation and Cycle Detection Simulate a process for 10^18 steps without waiting: record visited states, detect the cycle, fast-forward with modular arithmetic and verify against direct simulation.
- Grid and Matrix Tricks Master grid problems: direction arrays, border padding, flood fill, rotating and transposing matrices, and 2D prefix sums for constant-time rectangle sums.
Search and Greedy Thinking
- Binary Search on Answer for Contests Contest guide to binary search on the answer: monotonic checks, first-true and last-true templates, scaled integers for real answers, and the bounds bugs that cost penalties.
- Two Pointers and Sliding Windows in Practice Count subarrays in O(n) with two pointers: sum limits, the at-most-k trick for exactly-k distinct values, monotone pointers on sorted data and shortest covering windows.
- Greedy Algorithms and How to Trust Them Learn to trust a greedy solution before you submit: exchange arguments, stays-ahead proofs, and a brute-force counterexample hunt, with interval scheduling and lateness.
- Sorting, Events and Sweeps Use sorting as a contest weapon: custom keys, two-criteria orders, cmp_to_key, coordinate compression and sweep lines over events with correct tie-breaking.
Math for Contests
- Modular Arithmetic Master modular arithmetic for contests: mod 1e9+7, safe subtraction, pow with three arguments, modular inverses, division under a modulus and the traps of C++ remainders.
- Counting and Combinatorics Count fast under a modulus: factorial tables, nCr mod p, stars and bars, inclusion-exclusion with derangements, and Catalan numbers, each verified against brute force.
- Number Theory Toolkit A contest toolkit for number theory in Python: gcd and lcm, extended Euclid, sieves, smallest-prime-factor factorization, divisor enumeration and Euler's totient.
- Probability and Expected Value Contest probability in Python: indicator variables, linearity of expectation, expected-value DP and equations, and printing exact answers as fractions modulo a prime.
- Bit Tricks and XOR Problems Bitmask basics, subset enumeration in 3^n, XOR identities, prefix XOR counting, maximum XOR pair and the linear basis idea, with tested Python examples.
- Gaussian Elimination, Mobius and Inclusion-Exclusion for Contests Contest templates in Python: solve linear systems mod p and over GF(2), count solutions, and count pairs with a given gcd with Mobius in O(n^(2/3)).
- nCr Mod p with Lucas, Catalan and Stirling Numbers Contest counting templates in Python: nCr mod a small prime with Lucas, lattice paths and brackets by reflection, surjections and Stirling numbers.
- FFT and NTT for Contests Multiply polynomials and count pairs by sum in contests: a fast big-integer packing trick for exact results, plus an NTT modulo 998244353, tested against brute force.
- Geometry Toolkit for Contests A contest geometry toolkit in Python: exact cross products, segment intersection, convex hull, point in polygon, rotating calipers and precision rules.
Data Structures in Contest Practice
- Prefix Sums and Difference Arrays Answer range queries in O(1) and apply range updates in O(1) with prefix sums and difference arrays, in 1D and 2D, plus offline counting by sweeping.
- Monotonic Stacks, Heaps and Deques in Contests Contest patterns for monotonic stacks, sliding window maximum with a deque, and priority queues with lazy deletion, each tested against brute force in Python.
- DSU and Tree Problems Contest guide to union-find with path compression, Kruskal's MST, weighted DSU for difference constraints, and tree traversal without recursion in Python.
- Fenwick and Segment Trees for Contests Write short iterative Fenwick and segment trees, count inversions, understand lazy propagation, and know when a sparse table is the better choice.
- Offline Queries, DSU Rollback and Persistence Answer queries out of order, undo union-find merges for dynamic connectivity, keep old versions with a persistent segment tree, and use a Cartesian tree. Python, tested.
Graphs for Contests
- Graph Problems: Modeling and Traversal Turn contest statements into graphs, run BFS over implicit state graphs, use multi-source BFS and 0-1 BFS, and rebuild the path from parent pointers.
- Shortest Paths in Practice Pick the right shortest-path algorithm for a contest: Dijkstra with heapq, state-expanded graphs, Bellman-Ford with negative edges, and Floyd-Warshall limits.
- Trees, Diameters and LCA Solve contest tree problems in Python: iterative DFS, tree diameter, rerooting, binary lifting LCA and Euler tour subtree queries, all stress-tested.
- Centroid Decomposition for Contests Use centroid decomposition to count tree paths of length exactly k or at most k in O(n log n), with an iterative Python implementation verified by brute force.
- Maximum Flow and Matching in Contest Practice A contest template for Dinic max flow in Python, then model bipartite matching, minimum cuts, vertex capacities and project selection, checked by brute force.
- SCC and 2-SAT for Contests Contest Python templates: iterative Tarjan SCC, condensation DAG tricks, edges needed for strong connectivity, and a 2-SAT class with helper clauses.
Dynamic Programming for Contests
- DP Problem Patterns A repeatable recipe for contest DP: define the state, write the transition, set base cases and iterate in the right order, with coin, knapsack and LCS examples.
- Bitmask and Digit DP Solve TSP-style bitmask DP, enumerate submasks in 3^n, assign tasks with dp[mask], and count numbers up to N with digit DP and the tight flag.
- DP Speedups Speed up slow DP transitions in contests: sliding-window sums, monotone deques, the convex hull trick and divide and conquer optimization, each checked against a brute force.
Strings and Games
- String Algorithms in Contests Learn the string toolkit contests rely on: polynomial hashing with a modulus, the Z-function, the prefix function (KMP) and Manacher's palindromes, each tested against brute force.
- Game Theory Solve contest games: label winning and losing states, compute Grundy numbers, add independent games with XOR, recognize Nim variants and use symmetry strategies, all verified by brute force.
- Z, Suffix Array and Aho-Corasick in Contests Contest templates in Python: suffix array by doubling, Kasai LCP, distinct substrings, longest common substring and an Aho-Corasick automaton for many patterns.
Real-World Projects
- Project: A Local Contest Judge Build a small online-judge clone: run solutions on sample tests, compare outputs with a checker, count work with a line budget, and report AC, WA, PE, RE and TLE verdicts.
- Project: A Stress-Testing Framework Turn the stress-testing loop into a reusable framework: seeded generators, a brute force, a checker for many valid answers, crash detection and an automatic input minimizer.
- Project: An Elo-Style Rating Calculator Build an Elo-style rating calculator: win probability from rating gaps, rating changes from contest standings with ties, a zero-sum check and a simulation that recovers true skill.
- Project: An ICPC Scoreboard Build a contest scoreboard: ICPC penalty rules, ranking with ties, and incremental updates with bisect, checked against a full recomputation.
- Project: A Training Plan Tracker Build a practice tracker: log attempts, measure strength per topic, schedule reviews with spaced repetition and generate a daily plan of problems.
Practice and Review
- Practice: Warm-Up Problems with Solutions Twelve easy contest problems with ideas, runnable Python solutions, tests and complexity notes. A gentle start for building speed and confidence.
- Practice: Intermediate Problems with Solutions Twelve mid-level contest problems on greedy, binary search, dynamic programming and graphs, with ideas, runnable Python solutions and brute-force checks.
- Practice: Hard Problems with Solutions Eight harder contest problems with graded hints, then full runnable Python solutions: sliding windows, stacks, bitmask and digit DP, graph states, trees and games.
- CSES Introductory Problems Walkthrough Work through the classic CSES introductory problem set with original explanations and tested Python solutions: math tricks, constructions, backtracking and digit queries.
- CSES Sorting and Searching Walkthrough Original walkthrough of the CSES Sorting and Searching problems: two pointers, interval greedy, binary search, prefix-sum counting and reverse-time tricks, tested in Python.
- CSES DP Problems Walkthrough A guided tour of the CSES dynamic programming section: coin problems, knapsack, edit distance, counting towers, interval games, bitmask and broken-profile DP, all tested in Python.
- CSES Graph Problems Walkthrough Original walkthrough of classic CSES graph problems: grid BFS, multi-source BFS, negative cycles, Dijkstra with state, binary lifting, Hamiltonian counting and Euler circuits in Python.
- CSES Range Query and Tree Problems Walkthrough A walkthrough of CSES range query and tree problems with original Python: segment tree descent, offline Fenwick, binary lifting, Euler tour path sums, path counting and centroids.
- CSES Math, String and Geometry Walkthrough Original walkthrough of CSES math, game, string and geometry problems: divisor sums, derangements, Burnside necklaces, Nim and stair games, borders, minimal rotation, convex hull.
- CSES Advanced and Additional Problems Tour A tour of harder CSES topics with original Python: meet in the middle, Hamming distance, offline dynamic connectivity, Prufer codes and tree isomorphism, each verified by brute force.
- Training Plans and Virtual Contests Build a weekly training routine: virtual contests, upsolving, finding topic gaps and managing your time during a contest, with small runnable models.
- Competitive Programming Interview Questions Twenty-four competitive programming questions with short answers: complexity limits, greedy proofs, modular math, DP, graphs, and debugging, with runnable Python.
- Competitive Programming Cheat Sheet A one-page competitive programming cheat sheet: complexity limits by input size, Python templates, modular math formulas, graph and DP patterns, and debugging checklist.