Competitive Programmer’s Handbook

BSCS students preparing for programming contests — or anyone who wants a fast-paced, problem-oriented tour of algorithmic techniques — can read the complete textbook “Competitive Programmer’s Handbook” by Antti Laaksonen, free from its official source. It’s a 30-chapter, contest-oriented text organized into three parts, moving from basic techniques through graph algorithms to advanced mathematical and geometric topics.

This edition is published directly by the author, a competitive programming coach closely associated with the CSES Problem Set, and is organized into three clearly labeled parts: Part I covers basic techniques (Chapters 1–10) including sorting, data structures, greedy algorithms, dynamic programming, and range queries; Part II covers graph algorithms (Chapters 11–20) from traversal through network flow; and Part III covers advanced topics (Chapters 21–30) including number theory, combinatorics, game theory, string algorithms, and geometry — making it one of the most widely used free references for ICPC-style contest preparation worldwide.

Book Overview

Chapter List

Part I: Basic Techniques

Chapter 1: Introduction

Difficulty: Beginner · Early Semester · Competitive Programming Foundations · Key topics: what competitive programming is, contest structure, book conventions, mathematical background

The opening chapter introduces competitive programming as a discipline where correctness alone isn’t enough — a solution must also run within strict time and memory limits. It explains typical programming contest formats, how solutions are judged, and the notation and mathematical background (sums, logarithms, basic set theory) the rest of the book assumes. It sets the tone for everything that follows: every algorithm in this book is judged by both correctness and efficiency.

Key Points:

• Competitive programming problems require both a correct solution and one that runs within given time and memory limits, unlike typical classroom programming exercises.
• Contest judges typically test a submitted solution against many hidden test cases, including deliberately large or adversarial ones designed to break inefficient algorithms.
• The chapter previews the book’s overall structure: Part I covers basic techniques, Part II covers graph algorithms, and Part III covers advanced topics like number theory and geometry.
• Basic mathematical background — sum formulas, logarithms, and set notation — is reviewed since it underlies the complexity analysis used throughout the rest of the book.
• The chapter frames competitive programming as valuable practice for recognizing which known algorithmic technique applies to a new, unfamiliar-looking problem.

Memory Tip: Read every problem twice before coding: once for what output is required, and once specifically for the stated time and memory limits — the limits themselves are often the biggest hint toward which algorithmic technique the problem expects.

Common Mistake: Treating a problem as solved once a correct-looking solution compiles and passes small sample cases — a solution that is correct but too slow for the problem’s actual input size limits will fail on a contest judge just as surely as an incorrect one.

Important Questions:

• Q1: What distinguishes a competitive programming problem from a typical classroom programming exercise, according to this chapter? A competitive programming problem requires a solution that is both correct on all valid inputs and efficient enough to run within strict, explicitly stated time and memory limits, while a typical classroom exercise usually only checks for correctness on a small set of sample inputs without such strict efficiency requirements being automatically enforced.
• Q2: Why does the chapter review basic mathematical background like sums and logarithms before getting into algorithms? This mathematical background is the language used throughout the rest of the book to analyze and compare algorithms’ time complexity — without comfort with sums, logarithms, and basic set notation, it would be difficult to follow or reason about why one algorithm is faster than another in later chapters.

Chapter 2: Time Complexity

Difficulty: Beginner · Early Semester · Competitive Programming Foundations · Key topics: big O notation, complexity classes, calculation rules, estimating running time

This chapter formalizes how to estimate an algorithm’s running time using big O notation, independent of the exact hardware it runs on. It walks through the standard complexity classes (constant, logarithmic, linear, linearithmic, quadratic, and beyond), gives concrete rules for calculating the complexity of loops and nested loops, and connects complexity directly back to contest practice by showing how to estimate, from an input size limit alone, roughly which complexity class a passing solution needs to fall into.

Key Points:

• Big O notation describes how an algorithm’s running time grows as input size grows, ignoring constant factors and lower-order terms.
• Standard complexity classes covered include O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), and exponential classes like O(2^n) and O(n!).
• Nested loops multiply their individual complexities, while sequential (non-nested) loops add them, which is the basic rule for calculating a program’s overall complexity from its structure.
• A practical rule of thumb connects input size limits directly to required complexity class: roughly 10^8 basic operations per second is a safe assumption for estimating whether a given complexity will pass within a typical time limit.
• Recognizing an input size limit (like n ≤ 10^5 versus n ≤ 20) is presented as a genuine problem-solving skill, since it directly narrows down which complexity class, and therefore which algorithmic techniques, could possibly be fast enough.

Practice Tip: Before designing an algorithm, work backward from the problem’s stated input size limit: if n ≤ 10^5, an O(n^2) algorithm (10^10 operations) is almost certainly too slow, while if n ≤ 20, even an O(2^n) exponential algorithm may be perfectly fine.

Common Mistake: Assuming a nested loop is automatically O(n^2) without checking what the inner loop actually iterates over — if the inner loop’s range shrinks or depends on the outer loop’s variable, the true complexity can be different (sometimes still O(n^2), sometimes less), and this has to be worked out explicitly rather than assumed from the visual shape of the code.

Important Questions:

• Q1: How does the input size limit given in a competitive programming problem help estimate the required algorithmic complexity? Using the rule-of-thumb estimate of roughly 10^8 basic operations executable per second within a typical time limit, a given input size n can be plugged into each candidate complexity class to check whether the resulting operation count is small enough to finish in time; for example, if n ≤ 10^5, an O(n^2) algorithm requiring about 10^10 operations would almost certainly time out, while an O(n log n) algorithm would comfortably fit, immediately narrowing down which algorithmic approaches are even worth attempting.
• Q2: Why does big O notation ignore constant factors and lower-order terms when describing an algorithm’s running time? Big O notation is meant to describe how running time scales as input size grows arbitrarily large, and for large enough inputs the highest-order term dominates the total running time regardless of constant factors or smaller additive terms; this makes big O a useful tool for comparing the fundamental scalability of different algorithms, even though it deliberately ignores details (like exact constant factors) that can still matter for performance on any one specific, fixed input size.

Chapter 3: Sorting

Difficulty: Beginner · Early Semester · Competitive Programming Foundations · Key topics: sorting algorithms, built-in sorting, comparison operators, binary search

This chapter treats sorting as a foundational building block that many other algorithms rely on. It briefly covers how efficient O(n log n) sorting algorithms work conceptually, but focuses practically on using a programming language’s built-in sort function correctly, including how to define custom comparison criteria for sorting complex data. It closes with binary search, both for finding a value in a sorted array and, more generally, for finding the boundary point of a monotonic condition — a technique reused constantly throughout the rest of the book.

Key Points:

• General-purpose sorting algorithms achieve O(n log n) time complexity, which is proven to be the best possible for comparison-based sorting in the worst case.
• In practice, contestants are expected to rely on a language’s built-in, well-optimized sort function rather than reimplementing sorting algorithms from scratch, focusing instead on defining the right comparison logic.
• Custom sorting criteria (such as sorting objects by one field, then breaking ties by a second field) are handled by supplying a custom comparison function or operator to the built-in sort.
• Binary search finds a target value in a sorted array in O(log n) time by repeatedly halving the search range based on a comparison at the midpoint.
• Binary search generalizes beyond simple array lookup to “binary search on the answer”: finding the boundary point of any monotonic yes/no condition, a technique that reappears throughout later chapters for problems that don’t look like search problems at first.

Memory Tip: Whenever a problem asks to find the smallest or largest value satisfying some condition, and that condition is monotonic (once true, always true for larger/smaller values), consider binary searching directly on the answer rather than checking every possible value one by one.

Common Mistake: Reimplementing a sorting algorithm from scratch in a contest instead of using the language’s built-in sort — built-in implementations are heavily optimized and thoroughly tested, and a hand-written sort is far more likely to contain a subtle bug or be slower, with essentially no benefit in a competitive programming context.

Important Questions:

• Q1: What does it mean for “binary search on the answer” to require the underlying condition to be monotonic? It means that as the candidate answer value increases (or decreases), the yes/no condition being tested must never switch back and forth — once the condition becomes true (or false) as the candidate value increases, it must stay that way for all larger values; this monotonic structure is exactly what lets binary search safely eliminate half of the remaining candidate range at each step, the same way it does when searching a sorted array.
• Q2: Why is O(n log n) considered the best possible time complexity for general comparison-based sorting? It can be proven, using an information-theoretic argument about the number of possible orderings of n elements, that any sorting algorithm relying only on pairwise comparisons between elements must make at least on the order of n log n comparisons in the worst case to guarantee correctly determining the sorted order; this is why standard general-purpose sorting algorithms achieving O(n log n) time (like merge sort or an efficient quicksort variant) are considered asymptotically optimal for this general comparison-based setting.

Chapter 4: Data Structures

Difficulty: Beginner · Early Semester · Competitive Programming Foundations · Key topics: dynamic arrays, set structures, map structures, iterators, stacks, queues, deques, priority queues

This chapter surveys the standard-library data structures a competitive programmer reaches for constantly: dynamic arrays that grow as needed, set structures for maintaining a collection of distinct elements in sorted order, and map structures for key-value association, all typically backed by balanced trees or hash tables with well-understood time complexities. It also covers iterators and ranges as the standard way of working with these structures generically, and closes with a tour of additional structures — stacks, queues, deques, and priority queues — each suited to a different access pattern.

Key Points:

• Dynamic arrays provide O(1) amortized append and O(1) indexed access, making them the default choice for most sequential data in competitive programming.
• Set structures maintain a collection of distinct elements, typically supporting insertion, deletion, and membership testing in O(log n) time when backed by a balanced tree.
• Map structures associate keys with values, similarly typically offering O(log n) operations, and are the standard tool whenever a problem requires looking up information by some key rather than by position.
• Stacks (last-in-first-out) and queues (first-in-first-out) each support O(1) insertion and removal but from opposite ends, matching different problem access patterns.
• A priority queue (typically a binary heap) efficiently maintains a collection where the minimum (or maximum) element can always be retrieved and removed in O(log n) time, which is essential for later algorithms like Dijkstra’s shortest path.

Memory Tip: Match the data structure to the access pattern the problem actually needs: need sorted order and fast lookup? A set or map. Need last-added-first-out? A stack. Need first-added-first-out? A queue. Need repeated access to the current minimum/maximum? A priority queue.

Common Mistake: Defaulting to a plain array or list for every problem out of habit, even when a problem’s access pattern (frequent membership checks, frequent min/max retrieval, or key-based lookup) is a much better match for a set, priority queue, or map — using the wrong structure can silently turn an intended O(n log n) solution into an accidental O(n^2) one.

Important Questions:

• Q1: Why is a priority queue specifically useful for algorithms like Dijkstra’s shortest path, which this book covers in a later chapter? Dijkstra’s algorithm repeatedly needs to find and remove the not-yet-finalized vertex with the currently smallest known tentative distance; a priority queue (typically implemented as a binary heap) supports exactly this operation — efficient insertion and efficient removal of the current minimum — in O(log n) time, which is what gives Dijkstra’s algorithm its practical efficiency rather than having to scan all remaining vertices linearly at every step.
• Q2: What is the key difference in access pattern between a stack and a queue, and how does that map to their typical time complexities? A stack is last-in-first-out, always inserting and removing from the same end, while a queue is first-in-first-out, inserting at one end and removing from the other; despite this difference in which end is used, both structures support their respective insertion and removal operations in O(1) time each, because both can be implemented with simple pointer or index bookkeeping rather than needing to shift or search through the rest of the elements.

Chapter 5: Complete Search

Difficulty: Beginner · Early Semester · Competitive Programming Foundations · Key topics: generating subsets, generating permutations, backtracking, pruning, meet in the middle

This chapter develops complete search — systematically trying every possibility — as a genuinely useful technique for problems small enough to afford it, not just a last resort. It covers how to generate all subsets and all permutations of a set recursively, how backtracking builds a candidate solution incrementally while pruning branches that can no longer succeed, and closes with meet in the middle, a clever technique that splits a problem in half, solves each half by complete search, and combines the results to roughly square-root the effective search space.

Key Points:

• Complete search systematically tries every valid possibility, and remains a genuinely correct and often practical technique whenever the problem’s input size is small enough for the resulting search space to fit within the time limit.
• All 2^n subsets of a set, and all n! permutations of a sequence, can each be generated recursively using a simple, reusable recursive pattern.
• Backtracking builds a candidate solution incrementally, one choice at a time, and immediately abandons (“backtracks” out of) any partial candidate that is already known to be unable to lead to a valid solution, avoiding wasted exploration.
• Pruning — adding extra conditions that cut off hopeless branches of the search as early as possible — often turns a complete search from too slow into fast enough in practice, even without changing its worst-case complexity.
• Meet in the middle splits a problem’s search space into two independent halves, exhaustively solves each half separately, then combines the two halves’ results (often via sorting and binary search), turning an O(2^n) search into a much faster roughly O(2^(n/2)) one.

Practice Tip: Before dismissing complete search as “too slow”, check the actual input size limit against 2^n or n! — for n around 20 or smaller, a well-pruned complete search or a meet-in-the-middle technique is very often exactly the intended solution.

Common Mistake: Writing a backtracking search without any pruning at all, then concluding the technique itself is too slow for the problem — often the very same backtracking structure becomes fast enough once obviously hopeless branches are cut off early (for example, stopping immediately once a partial sum already exceeds a target), so pruning should be tried before abandoning complete search entirely.

Important Questions:

• Q1: How does the meet-in-the-middle technique reduce the effective size of a complete search? Instead of exhaustively searching all 2^n possibilities for a problem over n elements directly, meet in the middle splits the n elements into two halves of size n/2 each, exhaustively generates all 2^(n/2) possible results for each half independently, and then combines the two halves’ results (typically by sorting one half’s results and binary searching against the other) to find the overall answer; this reduces the total work from O(2^n) down to roughly O(2^(n/2) · log(2^(n/2))), a dramatic improvement for larger n.
• Q2: What is the difference between complete search in general and backtracking specifically, as presented in this chapter? Complete search broadly refers to any technique that tries every valid possibility to guarantee finding the correct answer; backtracking is a specific, more efficient way of organizing that search, building a candidate solution incrementally one decision at a time and abandoning a partial candidate as soon as it can be proven incapable of leading to a valid full solution, rather than always generating every possibility in full before checking it, which is what makes backtracking generally faster in practice than a naive brute-force enumeration.

Chapter 6: Greedy Algorithms

Difficulty: Intermediate · Early-Mid Semester · Competitive Programming Foundations · Key topics: scheduling problems, tasks and deadlines, the coin problem, greedy versus dynamic programming

This chapter introduces greedy algorithms — making the locally best choice at each step and never reconsidering it — through a sequence of classic scheduling and coin problems. Choosing which events to schedule to maximize the number attended, and ordering tasks by deadline to minimize total waiting time, are both shown to be correctly solved by simple greedy rules. The coin problem (making a target sum using the fewest coins) is used as a cautionary centerpiece: greedy (always take the largest coin that fits) works for some coin systems but provably fails for others, directly motivating the dynamic programming chapter that follows.

Key Points:

• A greedy algorithm makes an irrevocable, locally-optimal-looking choice at each step, and is only correct for problems whose structure guarantees that local choice never needs to be reconsidered later.
• The scheduling problem (choosing the maximum number of non-overlapping events from a set) is correctly solved by greedily always selecting the event that finishes earliest among those still compatible.
• The tasks-and-deadlines problem (minimizing total waiting time when tasks can be processed in any order) is correctly solved by greedily processing tasks in order of increasing duration, regardless of their deadlines.
• The coin problem, asking for the minimum number of coins summing to a target value, has a correct greedy solution (always take the largest denomination that fits) only for certain coin systems, such as standard currency denominations — it fails on other coin systems where a locally larger coin can force a worse total count.
• The chapter deliberately uses the coin problem’s greedy failure case to set up dynamic programming (the next chapter) as the general, always-correct technique for problems where greedy reasoning cannot be proven correct.

Common Mistake: Never assume a greedy strategy for the coin problem is correct just because it works for familiar currency denominations — for an arbitrary set of coin denominations, the “always take the largest coin that fits” greedy rule can produce a suboptimal (or even incorrect) total, which is exactly the chapter’s motivating example for why dynamic programming is needed in general.

Common Mistake: Applying a greedy strategy to a new problem simply because a similar-sounding problem earlier had a working greedy solution — each greedy algorithm in this chapter is correct because of a specific structural property of that particular problem, and correctness always needs to be verified (ideally proven) case by case rather than assumed by analogy.

Important Questions:

• Q1: Why does the greedy rule of always selecting the earliest-finishing compatible event correctly solve the event scheduling problem? Choosing the event that finishes earliest, among all events still compatible with what has already been selected, always leaves the maximum possible remaining time available for scheduling further events; this can be proven correct with an exchange argument showing that any optimal schedule can be modified to include the earliest-finishing choice without reducing the total number of events scheduled, which is exactly the structural property that makes this particular greedy strategy provably optimal.
• Q2: What does the coin problem in this chapter demonstrate about the limits of greedy algorithms, and why does that matter for the rest of the book? It demonstrates that a greedy strategy (“always take the largest coin denomination that still fits”) which works correctly for familiar coin systems does not work correctly for every possible set of coin denominations — there exist coin systems where this greedy choice leads to using more coins than the true minimum, or occasionally to a wrong result entirely; this matters because it shows greedy reasoning cannot simply be assumed correct by analogy, directly motivating the need for dynamic programming (covered in the next chapter) as a general technique guaranteed correct regardless of the specific coin system.

Chapter 7: Dynamic Programming

Difficulty: Intermediate · Mid Semester · Competitive Programming Foundations · Key topics: the coin problem revisited, longest increasing subsequence, paths in a grid, knapsack, edit distance, counting tilings

Directly following up on the previous chapter’s greedy failure case, this chapter develops dynamic programming as the general, always-correct technique for problems built from overlapping subproblems. It re-solves the coin problem correctly and generally using DP, then works through a sequence of classic problems — longest increasing subsequence, counting paths in a grid, the knapsack problem, edit distance between two strings, and counting tilings of a grid — each illustrating how to identify the right subproblem and the recurrence connecting subproblems together.

Key Points:

• Dynamic programming solves the coin problem generally and correctly, for any set of coin denominations, by building up a table of minimum-coins-needed for every value from 0 up to the target, unlike the greedy approach from the previous chapter.
• Longest increasing subsequence and counting paths in a grid are developed as classic one- and two-dimensional dynamic programming examples, each building a table indexed by subproblem parameters.
• The knapsack problem (choosing items with weights and values to maximize value within a weight limit) shows how a DP table’s dimensions directly reflect the problem’s actual constraints (item index and remaining capacity).
• Edit distance (minimum insertions/deletions/substitutions to transform one string into another) is developed as a substantial two-string dynamic programming example, a pattern reused later for string algorithms.
• Counting tilings of a grid with dominoes closes the chapter as a more elaborate DP example, using bitmask-based subproblem states to track a partial row’s coverage — foreshooding the later Bit Manipulation chapter’s dynamic-programming-with-bitmasks technique.

Memory Tip: For every new dynamic programming problem, explicitly answer three questions before coding: what exactly is a subproblem (in words), what recurrence relates it to smaller subproblems, and in what order must the table be filled so every needed smaller subproblem is already computed.

Common Mistake: Writing a recursive solution with memoization without first correctly identifying what parameters actually define a distinct subproblem — a table indexed by too few parameters (or the wrong ones) will silently merge genuinely different subproblems together and produce wrong answers, even though the code runs without any errors.

Important Questions:

• Q1: How does the dynamic programming solution to the coin problem guarantee correctness for any set of coin denominations, unlike the greedy approach from the previous chapter? The dynamic programming solution builds a table giving the minimum number of coins needed for every value from 0 up to the target sum, computing each entry by trying every available coin denomination and taking the best (minimum) result over all of them, rather than committing to a single “obviously best” choice at each step the way the greedy approach does; because every possibility is genuinely considered for every subproblem, the DP approach is guaranteed correct regardless of which specific coin denominations are given, unlike greedy, which is only correct for coin systems with the right special structure.
• Q2: Why does the chapter use bitmask-based subproblem states for counting tilings of a grid with dominoes, rather than a simpler table indexed just by row and column? When tiling a grid row by row with dominoes, whether a given cell in the current row is already covered can depend on a vertically-placed domino from the previous row, so simply knowing the row and column isn’t enough information to correctly continue the tiling; a bitmask representing exactly which cells in the current row boundary are already covered captures precisely the state needed to correctly determine which tiles can be placed next, making it possible to correctly count all valid tilings via dynamic programming over these bitmask states.

Chapter 8: Amortized Analysis

Difficulty: Intermediate · Mid Semester · Competitive Programming Foundations · Key topics: two pointers method, nearest smaller elements, sliding window minimum

This chapter introduces amortized analysis — showing an algorithm is efficient overall even when some individual steps look expensive, by proving the total cost across all steps is bounded. The two pointers method (moving two indices through an array so neither ever moves backward) is the chapter’s central technique, applied to problems like finding subarrays with a given sum. Using a stack to find each element’s nearest smaller element, and using a deque to maintain a sliding window’s minimum, are both shown to run in amortized linear time even though a naive per-step analysis might suggest otherwise.

Key Points:

• Amortized analysis bounds the total cost of a whole sequence of operations, rather than bounding every individual operation’s cost separately, which can reveal an algorithm is efficient overall even when individual steps vary in cost.
• The two pointers method processes an array with two indices that each only ever move forward, giving O(n) total work across the whole array even though it looks like it could involve nested iteration.
• Two pointers is directly applicable to problems like finding whether a subarray with a given target sum exists in a sorted context, avoiding an O(n^2) check of every possible subarray.
• Using a stack to find each array element’s nearest smaller element to its left or right runs in amortized O(n) time, since each element is pushed onto and popped from the stack at most once across the whole process.
• A sliding window minimum (or maximum) can be maintained in amortized O(n) time using a deque that keeps only “potentially useful” candidates, again because each element enters and leaves the deque at most once overall.

Memory Tip: The common thread across every technique in this chapter is the same: even though a single operation can occasionally look expensive, if you can show each element is added to and removed from the relevant structure (pointer position, stack, or deque) at most a constant number of times total, the whole process is amortized linear.

Common Mistake: Analyzing the two pointers method, the stack-based nearest-smaller-element technique, or the deque-based sliding window by looking only at a single step in isolation and concluding it’s O(n) per step (giving a pessimistic O(n^2) total) — the actual efficiency only becomes clear from the amortized, whole-process argument that each element is handled a bounded number of times overall, not from analyzing any one step alone.

Important Questions:

• Q1: Why does the two pointers method achieve O(n) total time despite conceptually looking like it could involve two nested loops? Both pointers only ever move forward through the array and never move backward or restart, so across the entire process, the total number of times either pointer advances is bounded by the array’s length n for each pointer; even though at first glance having two moving indices might suggest an O(n^2) nested-loop structure, the fact that neither pointer ever backtracks means the combined total work across the whole array is only O(n), not O(n^2).
• Q2: How does the stack-based technique for finding each element’s nearest smaller element achieve amortized O(n) time? As the algorithm processes elements left to right, it maintains a stack of candidates, popping elements off the stack whenever a new, smaller element makes them no longer relevant, and pushing the current element on afterward; although a single step could in principle pop many elements off the stack at once, each individual element is pushed onto the stack exactly once and popped off at most once across the entire algorithm, so the total number of push and pop operations summed over the whole process is bounded by O(n), giving amortized O(n) total time even though some individual steps do more work than others.

Chapter 9: Range Queries

Difficulty: Intermediate · Mid Semester · Competitive Programming Foundations · Key topics: static array queries, prefix sums, sparse tables, binary indexed tree, segment tree

This chapter develops the standard toolkit for answering many queries about ranges of an array efficiently. For a static (unchanging) array, prefix sums answer sum queries in O(1) after O(n) preprocessing, and sparse tables extend this idea to O(1) minimum/maximum queries at the cost of O(n log n) preprocessing space. When the array can also be updated between queries, the binary indexed tree (Fenwick tree) and the more general segment tree are introduced as the standard structures giving O(log n) updates and O(log n) range queries, becoming two of the most reused structures in the rest of the book.

Key Points:

• Prefix sums answer sum-of-a-range queries in O(1) time after a single O(n) preprocessing pass, by precomputing the cumulative sum up to every array position.
• Sparse tables extend the same idea to range minimum/maximum queries, achieving O(1) query time using O(n log n) precomputed overlapping-interval information, but only work correctly for static (never-updated) arrays.
• A binary indexed tree (Fenwick tree) supports both point updates and prefix-sum range queries in O(log n) time each, using a clever implicit tree structure encoded directly in array indices.
• A segment tree generalizes further, supporting both point (or range) updates and a wide variety of range queries (sum, minimum, maximum, and others) in O(log n) time each, by explicitly storing a binary tree over the array’s positions.
• Choosing between these structures is a genuine design decision: prefix sums/sparse tables for static arrays needing only O(1) queries, and binary indexed trees/segment trees whenever the array needs to support updates between queries.

Memory Tip: Ask two questions to pick the right range-query structure: does the array ever get updated between queries (if not, prefix sums or a sparse table suffice), and does the query need more than a sum (if minimum/maximum/other combining operations are needed with updates, reach for a segment tree).

Common Mistake: Using a sparse table for a problem where the array is actually updated between queries — a sparse table’s O(1) query time relies entirely on its precomputed data staying valid, and it does not support efficient updates at all; a binary indexed tree or segment tree is required instead whenever updates and queries are interleaved.

Important Questions:

• Q1: Why can’t a sparse table efficiently support updates to the underlying array, unlike a segment tree? A sparse table precomputes, for every position, the answer over many different overlapping fixed-length ranges, and its O(1) query speed depends entirely on being able to combine two of these precomputed overlapping ranges directly; if a single array element changes, it can affect many of these precomputed overlapping ranges at once, and there is no efficient way to update all of them without essentially rebuilding much of the table, whereas a segment tree’s explicit tree structure only requires updating O(log n) ancestor nodes when one array element changes.
• Q2: What is the essential structural difference between what a binary indexed tree and a segment tree can each support? A binary indexed tree (Fenwick tree) is specialized and most naturally supports prefix-sum-style queries (and by extension, range sums via subtraction of two prefix sums) along with point updates, using a compact implicit array-based structure; a segment tree is more general, explicitly storing a full binary tree over the array so it can support a wider variety of combining operations for range queries (minimum, maximum, sum, and others) directly, along with both point and, with additional lazy-propagation techniques covered later, range updates — making the segment tree the more flexible, if slightly more complex, choice.

Chapter 10: Bit Manipulation

Difficulty: Intermediate · Mid Semester · Competitive Programming Foundations · Key topics: bit representation, bit operations, representing sets as bitmasks, bit optimizations, dynamic programming with bitmasks

This chapter closes Part I by developing bit manipulation as both a low-level optimization tool and a genuine algorithmic technique. It covers how numbers are represented in binary, the standard bitwise operations (AND, OR, XOR, shifts) and their common uses, and the technique of representing a small set as a single integer bitmask, where set operations become fast bitwise operations. It closes by formalizing dynamic programming over bitmask states — foreshadowed by the previous chapter’s tiling problem — as the standard technique for problems over small sets where the subproblem needs to track exactly which elements have been used so far.

Key Points:

• Standard bitwise operations (AND, OR, XOR, left/right shift) each have well-known uses, such as checking or setting individual bits, or quickly testing whether a number is a power of two.
• A small set of up to about 20–30 elements can be represented as a single integer bitmask, where each bit indicates whether the corresponding element is present, turning set union, intersection, and membership testing into fast constant-time bitwise operations.
• Dynamic programming over bitmask states extends the previous chapter’s DP technique to problems where a subproblem’s state needs to track exactly which subset of elements has already been used or visited, common in problems related to permutations of a small set.
• The classic traveling salesman problem on a small number of cities is solved via bitmask DP in O(n^2 · 2^n) time, dramatically better than the O(n!) of trying every permutation directly, though still only practical for small n.
• Bit manipulation techniques double as practical low-level optimizations (fast set operations, fast parity/power-of-two checks) and as the enabling technique for bitmask dynamic programming, connecting this chapter back to the efficiency concerns from the very start of Part I.

Memory Tip: Reach for bitmask dynamic programming specifically when a problem’s subproblem needs to remember “which exact subset of a small number of elements has been used so far” — a state that a simple index-based table cannot represent, but that fits perfectly into a single integer bitmask.

Common Mistake: Using bitmask DP on a problem where the relevant “universe” of elements is too large — since a bitmask needs one bit per element, bitmask DP is only practical when the number of elements is small (typically up to around 20), since the number of possible bitmasks (2^n) grows exponentially and quickly becomes far too large to enumerate for bigger inputs.

Important Questions:

• Q1: How does representing a set as an integer bitmask make set operations faster than a general-purpose set data structure? When each bit of an integer directly represents whether one specific element is present in the set, standard bitwise operations directly implement set operations: bitwise AND computes the intersection of two sets, bitwise OR computes their union, and checking a specific bit tests membership — each of these becomes a single, extremely fast machine-level operation, in contrast to a general-purpose set data structure (like a balanced tree or hash set) which typically needs O(log n) or amortized O(1) time per individual element operation rather than handling an entire set’s worth of information in one operation.
• Q2: Why does bitmask dynamic programming reduce the traveling salesman problem’s complexity from O(n!) down to O(n^2 · 2^n), and why is this still only practical for small n? Bitmask DP avoids re-exploring the many permutations that revisit the same subset of already-visited cities by using a state (current city, bitmask of visited cities) that captures everything needed to continue optimally, computing each distinct state’s answer only once instead of once per full permutation that happens to pass through it; this reduces the total work to roughly (number of states) × (transition cost) = O(2^n · n) × O(n) = O(n^2 · 2^n), a huge improvement over O(n!), but 2^n itself still grows exponentially, so this approach remains practical only for a relatively small number of cities (typically up to around 20).

Part II: Graph Algorithms

Chapter 11: Basics of Graphs

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: graph terminology, graph representation, adjacency list, adjacency matrix, edge list

Opening Part II, this chapter lays the graph-theoretic groundwork the rest of the book depends on: formal terminology for graphs (directed/undirected, weighted/unweighted, paths, cycles, connectivity), and the three standard ways to represent a graph in code — adjacency lists, adjacency matrices, and edge lists — each with a different space/time trade-off suited to different algorithms. Choosing the right representation for a given algorithm and graph size is framed as a real, practical decision that affects both correctness of implementation and overall performance.

Key Points:

• A graph consists of nodes and edges, and can be directed or undirected, weighted or unweighted, depending on what real-world relationship or structure is being modeled.
• An adjacency list stores, for each node, a list of its neighboring nodes (and edge weights if applicable), using space proportional to the number of edges — efficient for sparse graphs.
• An adjacency matrix stores an n×n grid indicating whether an edge exists between every pair of nodes, using space proportional to the square of the number of nodes but allowing O(1) edge-existence checks.
• An edge list simply stores every edge as a (from, to, weight) triple in a flat list, which is often the most convenient representation for algorithms like Kruskal’s that process edges directly, covered in a later chapter.
• Choosing a graph representation is a genuine trade-off: adjacency lists suit most traversal algorithms on sparse graphs, adjacency matrices suit dense graphs or algorithms needing fast edge-existence checks, and edge lists suit edge-centric algorithms.

Memory Tip: Default to an adjacency list unless a specific reason points elsewhere: it uses space proportional to the actual number of edges (good for the typically sparse graphs seen in most problems) and supports the traversal algorithms in the next chapter efficiently.

Common Mistake: Defaulting to an adjacency matrix regardless of graph size out of habit — for a graph with many nodes but relatively few edges (a sparse graph, common in most contest problems), an adjacency matrix wastes enormous amounts of space and time compared to an adjacency list, and can easily exceed memory limits for larger graphs.

Important Questions:

• Q1: What is the key space trade-off between an adjacency list and an adjacency matrix? An adjacency list uses space proportional to the actual number of edges in the graph, since each node only stores information about its actual neighbors; an adjacency matrix uses space proportional to the square of the number of nodes regardless of how many edges actually exist, since it must store a value indicating the presence or absence of an edge for every possible pair of nodes — making the adjacency matrix far more space-wasteful for sparse graphs (relatively few edges compared to the number of possible ones), which is the typical case in most competitive programming problems.
• Q2: When would an edge list representation be preferred over an adjacency list? An edge list is preferred when an algorithm needs to process the graph’s edges directly and independently, rather than by walking from node to node — the classic example, covered in a later chapter, is Kruskal’s minimum spanning tree algorithm, which needs to consider all edges sorted by weight regardless of which nodes they connect; an adjacency list, by contrast, is organized around each node’s neighbors, which is more natural for traversal-based algorithms (like depth-first or breadth-first search) that move from one node to its neighbors step by step.

Chapter 12: Graph Traversal

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: depth-first search, breadth-first search, applications of graph traversal

This chapter develops the two fundamental graph traversal algorithms, depth-first search (DFS) and breadth-first search (BFS), and shows how each is naturally suited to different questions about a graph. DFS, typically implemented recursively or with an explicit stack, explores as deep as possible before backtracking, and is well suited to questions about connectivity and structure. BFS, using a queue, explores level by level outward from a starting node, and is the natural tool for finding shortest paths in an unweighted graph. Both are shown applied to practical problems like counting connected components and finding shortest unweighted paths.

Key Points:

• Depth-first search explores a graph by going as deep as possible along each branch before backtracking, naturally implemented either recursively or with an explicit stack.
• Breadth-first search explores a graph level by level outward from a starting node, using a queue, visiting all nodes at distance 1 before any node at distance 2, and so on.
• Both DFS and BFS visit every reachable node and edge exactly once, giving each an O(n + m) time complexity (nodes plus edges), making both efficient even on large graphs.
• DFS is naturally suited to structural questions like counting connected components, detecting cycles, or exploring all reachable states in a search space.
• BFS is naturally suited to shortest-path questions in unweighted graphs, since its level-by-level exploration order guarantees the first time a node is reached is via a shortest path from the source.

Memory Tip: Choose between DFS and BFS by what the problem actually asks: need shortest paths in an unweighted graph, or minimum number of steps? Reach for BFS. Need to explore full structure, connectivity, or just visit everything reachable? DFS is usually simpler to implement, often recursively.

Common Mistake: Using depth-first search to find shortest paths in an unweighted graph — DFS’s exploration order provides no guarantee about finding the shortest path first, since it can go arbitrarily deep down one branch before ever exploring a shorter alternative route; breadth-first search’s level-by-level order is what specifically guarantees shortest paths in an unweighted graph.

Important Questions:

• Q1: Why does breadth-first search correctly find shortest paths in an unweighted graph, while depth-first search does not? Breadth-first search explores nodes in strict order of increasing distance from the source — visiting all nodes at distance 1 before any node at distance 2, and so on — which guarantees that the very first time any node is reached during the traversal, it has been reached via a shortest possible path; depth-first search instead follows one branch as deep as possible before backtracking, with no such guarantee about exploration order, so it can easily reach a node via a much longer path long before a shorter path to that same node would have been discovered.
• Q2: Why do both DFS and BFS achieve O(n + m) time complexity on a graph with n nodes and m edges? Both algorithms visit every node exactly once (marking it visited to avoid revisiting) and, for each visited node, examine each of its outgoing edges exactly once to decide whether to continue the traversal along them; since each node contributes O(1) work for being visited and each edge is examined a constant number of times total across the whole traversal, the combined total work across the entire graph is O(n + m), regardless of whether the traversal proceeds depth-first or breadth-first.

Chapter 13: Shortest Paths

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: Bellman-Ford algorithm, Dijkstra’s algorithm, Floyd-Warshall algorithm

This chapter extends shortest-path computation from the previous chapter’s unweighted BFS case to weighted graphs, covering three algorithms suited to different situations. Bellman-Ford handles graphs that may contain negative edge weights (and can detect negative cycles) using repeated edge relaxation. Dijkstra’s algorithm, implemented efficiently with a priority queue, greedily computes single-source shortest paths quickly but only when all edge weights are non-negative. Floyd-Warshall computes shortest paths between every pair of nodes at once using a compact dynamic program, trading some efficiency for simplicity and generality on smaller graphs.

Key Points:

• Bellman-Ford computes single-source shortest paths correctly even with negative edge weights, by relaxing every edge repeatedly (up to n – 1 times), and can additionally detect the presence of a negative cycle.
• Dijkstra’s algorithm greedily finalizes the closest not-yet-finalized node at each step, and is correct only when all edge weights are non-negative, but is significantly faster than Bellman-Ford when that condition holds.
• A priority queue is the standard efficient implementation for Dijkstra’s algorithm, giving an overall O(m log n) running time by efficiently finding the next closest node at each step.
• Floyd-Warshall computes shortest paths between every pair of nodes simultaneously using a simple triple-nested-loop dynamic program, running in O(n^3) time, making it best suited to smaller, dense graphs where all-pairs information is needed.
• Choosing among the three algorithms depends on the specific problem: Bellman-Ford for possible negative weights or cycle detection, Dijkstra’s for fast non-negative single-source shortest paths, and Floyd-Warshall for all-pairs shortest paths on smaller graphs.

Common Mistake: Running Dijkstra’s algorithm on a graph that has any negative edge weights is a classic and common mistake — its greedy “finalize the closest node” step assumes a finalized node’s distance can never later improve, an assumption that a negative edge can silently violate.

Common Mistake: Reaching for Floyd-Warshall’s O(n^3) all-pairs algorithm out of convenience on a large, sparse graph where only single-source shortest paths are actually needed — on a graph with many nodes, Floyd-Warshall’s cubic complexity can be far slower than running Dijkstra’s or Bellman-Ford’s algorithm from the single required source instead.

Important Questions:

• Q1: What specific extra capability does Bellman-Ford provide that Dijkstra’s algorithm does not, and why? Bellman-Ford correctly handles graphs with negative edge weights and can detect the existence of a negative cycle (a cycle whose total weight is negative, which would make some shortest paths undefined since a path could loop around it indefinitely to keep decreasing in total weight); it can do this because it repeatedly relaxes every edge rather than greedily and permanently finalizing distances one node at a time the way Dijkstra’s algorithm does, so a distance can still be corrected multiple times as better paths are discovered, and if any distance can still be improved after n – 1 relaxation rounds, that indicates a negative cycle is present.
• Q2: Why is Floyd-Warshall well suited specifically to the all-pairs shortest path problem, rather than to single-source shortest paths? Floyd-Warshall’s dynamic program computes, for every pair of nodes simultaneously, the shortest distance by considering each node in turn as a potential intermediate stop on the path between that pair; because it naturally produces shortest distances for every pair of nodes as a side effect of its single triple-nested-loop computation, running in O(n^3) time total, it is efficient specifically when all-pairs information is genuinely needed, whereas for single-source shortest paths alone, running Dijkstra’s or Bellman-Ford’s algorithm just once from the one required source is typically far more efficient than computing the unnecessary information for every other pair as well.

Chapter 14: Tree Algorithms

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: properties of trees, tree traversal, diameter of a tree, all longest paths, binary trees

This chapter specializes graph algorithms to trees — connected graphs with no cycles — exploiting their simpler structure for faster, more elegant algorithms. It covers basic tree properties and traversal, then develops two related classic problems: computing a tree’s diameter (the longest path between any two nodes), solvable with two well-chosen depth-first searches, and computing, for every node, the length of the longest path passing through it, using a clever “rerooting” technique that reuses work across the whole tree. The chapter closes with binary trees as a special, especially common case.

Key Points:

• A tree is a connected graph with exactly n – 1 edges for n nodes and no cycles, giving it a uniquely simple recursive structure that many graph algorithms can exploit for extra efficiency.
• A tree’s diameter (the length of the longest path between any two nodes) can be found in just two depth-first searches: one from an arbitrary node to find the farthest node from it, and a second from that farthest node to find the true diameter endpoint.
• Computing the length of the longest path passing through every single node efficiently uses a “rerooting” technique: an initial DFS computes information relative to one root, and a second pass propagates and adjusts that information as the root is conceptually moved to each node in turn, avoiding a separate expensive computation per node.
• Binary trees, where every node has at most two children, are treated as an especially common and important special case, with standard traversal orders (preorder, inorder, postorder) each useful for different purposes.
• Because a tree has no cycles, many general-graph algorithms simplify significantly when restricted to trees, which is why tree-specific algorithms are worth learning separately rather than always falling back on general graph techniques.

Memory Tip: Remember the diameter-finding trick as “farthest, then farthest again”: DFS from any node to find the farthest node A, then DFS from A to find the farthest node B — the path from A to B is guaranteed to be the tree’s diameter.

Common Mistake: Assuming the diameter of a tree must pass through some specific “central” node chosen arbitrarily, and searching only from that one node — a single DFS from an arbitrary starting node only reliably finds one endpoint of the diameter; the second DFS from that endpoint is what’s actually required to correctly find the diameter’s true length.

Important Questions:

• Q1: Why does starting a depth-first search from an arbitrary node, finding the farthest node A, and then searching again from A correctly find the tree’s diameter? It can be proven that the farthest node from any arbitrary starting node in a tree must be one endpoint of some diameter path; once that endpoint A is found by the first DFS, a second DFS starting specifically from A is then guaranteed to find the true other endpoint B of the actual longest path in the tree, because A being a genuine diameter endpoint guarantees the farthest node from A specifically is the other true endpoint — a guarantee that does not hold for an arbitrary, non-endpoint starting node.
• Q2: What problem does the “rerooting” technique solve, and why is it more efficient than computing the answer separately for each node? Rerooting efficiently computes, for every single node in the tree, the length of the longest path passing through that particular node, without having to run a separate expensive computation rooted at each node individually; it works by first computing relevant path-length information with the tree rooted at one arbitrary node via a normal DFS, then propagating and adjusting that information in a second pass as the conceptual root is incrementally shifted from each node to its neighbors, reusing most of the previously computed information at each step rather than recomputing from scratch, which brings the total work down to O(n) overall instead of O(n) work repeated once per node (O(n^2) total).

Chapter 15: Spanning Trees

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: minimum spanning trees, Kruskal’s algorithm, union-find, Prim’s algorithm

This chapter covers the minimum spanning tree (MST) problem — connecting all nodes of a weighted graph with the minimum total edge weight, using no cycles — through its two classic algorithms. Kruskal’s algorithm considers edges globally, cheapest first, adding each one unless it would create a cycle, using the union-find (disjoint-set) data structure to check this efficiently. Prim’s algorithm instead grows a single tree outward from one starting node, always adding the cheapest available connecting edge. Both are shown to be correct greedy strategies for the same underlying problem.

Key Points:

• A minimum spanning tree connects every node of a weighted, connected graph using the minimum possible total edge weight, with no cycles — using exactly n – 1 edges for n nodes.
• Kruskal’s algorithm sorts all edges by weight and greedily adds each edge, cheapest first, unless doing so would create a cycle with edges already added.
• The union-find (disjoint-set) data structure efficiently supports Kruskal’s cycle-checking step, letting the algorithm check in nearly constant time whether two nodes are already connected by previously added edges.
• Prim’s algorithm instead grows a single connected tree outward from one starting node, at every step adding the cheapest edge connecting a new node to the tree built so far, typically implemented efficiently with a priority queue.
• Both Kruskal’s and Prim’s algorithms are correct, despite their different operational styles, because of the same underlying cut property: the cheapest edge crossing any cut of the graph is always safe to include in some minimum spanning tree.

Memory Tip: Keep the two algorithms straight by what they’re greedy about: Kruskal considers all edges globally, cheapest first, using union-find to avoid cycles; Prim grows one single tree outward, always adding that tree’s cheapest available connecting edge next.

Common Mistake: Implementing Kruskal’s algorithm’s cycle check with a naive DFS or BFS reachability check on every candidate edge instead of using union-find — a naive reachability check can cost O(n) per edge, making the overall algorithm much slower than necessary; union-find’s near-constant-time operations are exactly what make Kruskal’s algorithm efficient in practice.

Important Questions:

• Q1: What role does the union-find data structure play in making Kruskal’s algorithm efficient? Kruskal’s algorithm needs to repeatedly check, for each candidate edge in increasing order of weight, whether that edge’s two endpoints are already connected by edges added so far (which would mean adding it creates a cycle); the union-find data structure tracks which nodes currently belong to the same connected component and supports both this “same component” check and merging two components after adding an edge in nearly constant amortized time each, which is what keeps Kruskal’s overall running time efficient (dominated by the initial edge sort) rather than being slowed down by an expensive cycle check at every step.
• Q2: What is the key operational difference between Kruskal’s algorithm and Prim’s algorithm for finding a minimum spanning tree? Kruskal’s algorithm considers all of the graph’s edges globally, in increasing order of weight, adding each one as long as it connects two currently-separate components, regardless of which specific components those are; Prim’s algorithm instead grows a single connected tree outward from one chosen starting node, at every step adding only the cheapest edge that connects some new, not-yet-included node directly to the tree already built so far — so while both algorithms are correct minimum spanning tree algorithms justified by the same cut property, Kruskal’s works edge-by-edge across the whole graph while Prim’s works node-by-node outward from a single starting point.

Chapter 16: Directed Graphs

Difficulty: Intermediate · Mid Semester · Graph Algorithms · Key topics: topological sorting, dynamic programming on directed acyclic graphs, successor graphs, cycle detection

This chapter focuses on directed graphs, developing topological sorting — ordering a directed acyclic graph’s (DAG) nodes so every edge points forward — as the key technique that makes dynamic programming directly on a graph’s structure possible. It covers detecting whether a directed graph contains a cycle at all (which would make topological sorting impossible), and introduces successor graphs (also called functional graphs, where every node has exactly one outgoing edge) as a special, especially structured case with its own efficient techniques for answering “where do I end up after k steps” style questions.

Key Points:

• A directed acyclic graph (DAG) can be topologically sorted — its nodes ordered so that every directed edge points from an earlier node to a later one in the order — if and only if it contains no directed cycle.
• Topological order can be computed via depth-first search, recording each node’s finishing order and then reversing it, or via repeatedly removing nodes with no remaining incoming edges.
• Once a DAG is topologically sorted, many dynamic programming problems defined directly on the graph’s structure (such as longest path in a DAG) can be solved in a single linear-time pass processed in that order.
• Detecting whether a directed graph contains any cycle at all (making topological sorting impossible) can be done during a DFS by watching for a “back edge” — an edge to a node still active on the current recursion path.
• A successor graph (functional graph), where every node has exactly one outgoing edge, has a special structure (eventually leading into a single cycle from any starting node) that allows efficient techniques, such as binary lifting, for answering “where do I end up after k steps from node x” queries quickly.

Memory Tip: Remember topological sort’s core payoff: once a DAG’s nodes are ordered so every edge points forward, any dynamic program defined over the graph’s structure can be computed in a single linear-time pass in that order, since every predecessor is guaranteed already processed.

Common Mistake: Attempting to topologically sort a directed graph without first confirming (or without the algorithm implicitly confirming) that it’s actually acyclic — a directed graph containing a cycle has no valid topological order at all, and an implementation that doesn’t detect this can either loop forever or silently produce a meaningless, invalid ordering.

Important Questions:

• Q1: Why does a directed graph need to be acyclic for a topological sort to exist? A topological sort requires an ordering of all nodes such that every directed edge points from an earlier node to a later node in that ordering; if the graph contains a directed cycle, then following the cycle’s edges would require some node to simultaneously come both before and after another node on that same cycle in the ordering, which is a direct contradiction — so no valid ordering satisfying every edge’s direction constraint can exist whenever a directed cycle is present, which is exactly why topological sorting is only defined for directed acyclic graphs.
• Q2: How does topological order enable a single linear-time dynamic programming pass for a problem like longest path in a DAG? Processing nodes in topological order guarantees that, by the time any given node is processed, every one of its predecessors (nodes with an edge pointing into it) has already been fully processed and has its final DP value computed; this means each node’s DP value (for example, the longest path ending at that node) can be correctly computed just once, by combining the already-finalized values of its predecessors, without ever needing to revisit or recompute an earlier node’s value later — giving a total running time proportional to the number of nodes plus edges, processed in a single pass.

Chapter 17: Strong Connectivity

Difficulty: Advanced · Late-Mid Semester · Graph Algorithms · Key topics: strongly connected components, Kosaraju’s algorithm, the 2SAT problem

This chapter extends directed-graph analysis to strong connectivity — identifying maximal groups of nodes in a directed graph that can all reach each other. Kosaraju’s algorithm is developed as an elegant, efficient way to find all strongly connected components using two carefully ordered depth-first searches, one on the original graph and one on its edge-reversed version. The chapter closes with the 2SAT problem — determining whether a boolean formula in a restricted two-variable-per-clause form is satisfiable — shown to reduce elegantly to checking strong connectivity in a cleverly constructed implication graph.

Key Points:

• A strongly connected component (SCC) is a maximal set of nodes in a directed graph where every node in the set can reach every other node in the set via directed edges.
• Kosaraju’s algorithm finds all strongly connected components in linear time using two depth-first search passes: one on the original graph to compute a finishing-order, and one on the graph with all edges reversed, processed in reverse finishing order.
• Contracting each strongly connected component of a directed graph into a single node always produces a directed acyclic graph (the “condensation” of the original graph), giving a clean higher-level summary of its structure.
• The 2SAT problem asks whether a boolean formula made of clauses each involving at most two variables can be satisfied, and is solvable efficiently (unlike general satisfiability) despite superficially resembling the NP-hard general SAT problem.
• 2SAT is solved by building an implication graph where each clause becomes two directed implication edges, then checking strong connectivity: the formula is satisfiable if and only if no variable and its negation end up in the same strongly connected component.

Memory Tip: Remember Kosaraju’s two-pass structure: first DFS on the original graph to get a finishing order, then DFS on the reversed graph processed in reverse finishing order — each resulting DFS tree in the second pass is exactly one strongly connected component.

Common Mistake: Assuming 2SAT’s efficient solvability means general boolean satisfiability (with three or more variables per clause) is also efficiently solvable the same way — the reduction to strong connectivity in an implication graph specifically relies on each clause having at most two variables; with three or more variables per clause, this same graph-based technique does not apply, and general SAT remains NP-complete.

Important Questions:

• Q1: Why does Kosaraju’s algorithm need to run depth-first search on both the original graph and its edge-reversed version? The first DFS pass, on the original graph, computes a finishing order that has the useful property that any strongly connected component containing a “later” node (in the reversal-graph exploration) can never accidentally get merged with an unrelated component if processed correctly; the second DFS pass, run on the graph with every edge reversed and processed specifically in reverse order of the first pass’s finishing times, then correctly groups nodes into their true strongly connected components, because reversing the edges combined with this specific processing order guarantees each resulting DFS tree in the second pass stays exactly within one strongly connected component and does not leak into another.
• Q2: How does the 2SAT problem get reduced to a strong connectivity question, and what does the result tell you about satisfiability? Each clause in a 2SAT formula (an OR of two literals) is translated into two directed implication edges in a graph over all variables and their negations — for a clause (a OR b), the edges say “not a implies b” and “not b implies a”; after building this full implication graph from every clause, the original formula is satisfiable if and only if no variable and its own negation ever end up in the same strongly connected component of this graph, since that situation would mean the variable is forced to imply both its own negation and vice versa, which is a direct logical contradiction that makes the formula unsatisfiable.

Chapter 18: Tree Queries

Difficulty: Advanced · Late-Mid Semester · Graph Algorithms · Key topics: finding ancestors, binary lifting, subtrees and paths, lowest common ancestor, offline algorithms

This chapter develops efficient techniques for answering many queries about a tree’s structure, building on both the Tree Algorithms and Range Queries chapters. Binary lifting precomputes enough information to jump to any ancestor of a node in O(log n) time per query. Subtree and path queries are handled by flattening the tree into an array using entry/exit timestamps, turning tree queries into the range queries from Chapter 9. The lowest common ancestor (LCA) problem is covered through several approaches, and the chapter closes with offline algorithms that process all queries together for extra efficiency when queries don’t need to be answered in real time.

Key Points:

• Binary lifting precomputes, for each node, its 2^k-th ancestor for increasing powers of k, letting any “k-th ancestor of node x” query be answered in O(log n) time by combining the right precomputed jumps.
• Flattening a tree into an array using entry and exit timestamps from a single DFS turns subtree queries into simple contiguous range queries, directly reusing the range-query structures (like segment trees) from an earlier chapter.
• The lowest common ancestor (LCA) of two nodes is the deepest node that is an ancestor of both, and can be found efficiently using binary lifting, or via a reduction to a range-minimum-query problem over the DFS traversal order.
• Path queries between two arbitrary nodes in a tree can be decomposed using the LCA: the path from u to v passes through their lowest common ancestor, splitting the query into two more tractable pieces.
• Offline algorithms process all queries together, often sorted in a convenient order, rather than answering each query independently and immediately — useful when the problem allows all queries to be known in advance, often simplifying or speeding up the overall solution.

Memory Tip: Remember the tree-flattening trick: a single DFS assigning each node an entry time and exit time turns “is node y in the subtree of node x” and subtree-sum-style queries into simple range checks and range queries over that DFS-order array.

Common Mistake: Recomputing a node’s ancestors from scratch (walking up one step at a time) for every single “k-th ancestor” or LCA query in a problem with many queries — this naive approach costs O(n) per query in the worst case, which is far too slow when there are many queries; binary lifting’s O(log n) per query, after O(n log n) one-time preprocessing, is the standard efficient alternative.

Important Questions:

• Q1: How does binary lifting answer a “find the k-th ancestor of node x” query in O(log n) time? During preprocessing, binary lifting computes, for every node, its ancestor at distance exactly 2^0, 2^1, 2^2, and so on (up to roughly log n), storing these as a table; to answer a query for the k-th ancestor of a specific node, k is written in binary, and the precomputed jumps corresponding to each set bit of k are applied one after another, moving the current node upward by exactly the right total distance in O(log n) total jump steps, rather than walking up one ancestor at a time.
• Q2: How does flattening a tree with DFS entry and exit timestamps turn a subtree query into a range query? A single DFS traversal assigns each node an entry timestamp (when it is first visited) and an exit timestamp (when the DFS finishes exploring everything reachable from it); because DFS explores an entire subtree contiguously before backtracking, every node in a given node’s subtree is guaranteed to have an entry timestamp falling strictly between that node’s own entry and exit timestamps, which means checking subtree membership, or answering a subtree-sum-style query, reduces directly to a simple contiguous range check or range query over the array of nodes ordered by entry timestamp — letting the range-query structures from an earlier chapter be reused directly for tree problems.

Chapter 19: Paths and Circuits

Difficulty: Advanced · Late Semester · Graph Algorithms · Key topics: Eulerian paths and circuits, Hamiltonian paths, De Bruijn sequences, knight’s tours

This chapter covers two related but very differently-behaved graph problems: Eulerian paths/circuits (visiting every edge of a graph exactly once) and Hamiltonian paths/circuits (visiting every node exactly once). Eulerian paths have a simple, efficiently checkable existence condition based on node degrees and connectivity, and an efficient algorithm (Hierholzer’s algorithm) to construct one when it exists. Hamiltonian paths, by contrast, have no known simple existence condition and are NP-hard to find in general, connecting this chapter to the NP-hardness material referenced elsewhere. Two well-known applications, De Bruijn sequences and knight’s tours, close the chapter.

Key Points:

• An Eulerian circuit visits every edge of a graph exactly once and returns to its starting node; it exists if and only if the graph is connected (ignoring isolated nodes) and every node has even degree, a simple and efficiently checkable condition.
• An Eulerian path (not necessarily returning to the start) exists under a similarly simple, efficiently checkable condition: the graph is connected and exactly zero or two nodes have odd degree.
• Hierholzer’s algorithm efficiently constructs an Eulerian circuit or path, when one exists, in time linear in the number of edges, by repeatedly finding and merging cycles.
• A Hamiltonian path or circuit visits every node of a graph exactly once, and unlike the Eulerian case, determining whether one exists is NP-hard in general — no simple efficiently-checkable condition is known.
• De Bruijn sequences (compact sequences containing every possible substring of a given length exactly once) and the knight’s tour problem (a Hamiltonian path of a knight’s moves on a chessboard) are presented as classic, concrete applications connecting this chapter’s theory to specific well-known puzzles.

Memory Tip: Keep Eulerian and Hamiltonian straight by what they count: Eulerian is about visiting every EDGE exactly once (efficiently checkable via node degrees), Hamiltonian is about visiting every NODE exactly once (NP-hard in general, no simple existence condition).

Common Mistake: Confusing the efficiently-solvable Eulerian path/circuit problem with the NP-hard Hamiltonian path/circuit problem because their definitions sound superficially similar — the existence of an Eulerian path or circuit can be checked in linear time from node degrees alone, while no such simple check is known for Hamiltonian paths or circuits, and finding one (or proving none exists) is believed to require exponential time in the worst case.

Important Questions:

• Q1: What simple condition determines whether a connected graph has an Eulerian circuit, and why does this condition make sense? A connected graph has an Eulerian circuit if and only if every node has even degree; this makes sense because every time the circuit passes through a node (other than possibly the very start/end), it must use one edge to enter and a different edge to leave, using up the node’s edges in pairs — so a node with odd degree would eventually leave one edge unpaired, making it impossible to traverse every edge exactly once and return cleanly to the start, while a node with even degree can always have all of its edges paired up correctly as the circuit passes through it possibly multiple times.
• Q2: Why is determining whether a graph has a Hamiltonian path considered a fundamentally harder problem than determining whether it has an Eulerian path? Unlike the Eulerian case, where a simple, efficiently checkable condition based only on node degrees and connectivity fully determines existence, no such simple efficiently-checkable condition is known for Hamiltonian paths, and the problem of determining Hamiltonian path existence is proven to be NP-hard in general; this means that, unless P equals NP, there is no known algorithm that can decide Hamiltonian path existence (let alone find one) in polynomial time for all graphs, in sharp contrast to the linear-time Eulerian path check and construction.

Chapter 20: Flows and Cuts

Difficulty: Advanced · Late Semester · Graph Algorithms · Key topics: maximum flows, Ford-Fulkerson algorithm, disjoint paths, maximum matchings, path covers

Closing Part II, this chapter introduces network flow — modeling a graph as a network of pipes with per-edge capacities and asking how much total flow can be pushed from a source to a sink — and its many surprising applications. The Ford-Fulkerson augmenting-path algorithm is developed as the fundamental method for computing maximum flow, alongside the maxflow-mincut theorem connecting maximum flow to minimum cut capacity. The chapter closes by showing how many seemingly unrelated problems — finding disjoint paths, maximum bipartite matching, and minimum path covers — can all be modeled and solved as maximum flow problems.

Key Points:

• A flow network models each edge as a pipe with a maximum capacity, asking for the largest total flow that can be pushed from a designated source to a designated sink without violating any capacity constraint.
• The Ford-Fulkerson algorithm repeatedly finds an augmenting path from source to sink with remaining spare capacity in the residual graph (which includes reverse edges allowing flow to be effectively “undone”) and pushes more flow along it, until no such path remains.
• The maxflow-mincut theorem states that the maximum possible flow in any network is always exactly equal to the minimum-capacity cut separating source from sink, giving a way to certify a flow is truly maximum.
• Finding the maximum number of edge-disjoint (or vertex-disjoint, with a small modeling adjustment) paths between two nodes reduces directly to computing maximum flow with unit edge capacities.
• Maximum bipartite matching (optimally pairing items from two groups according to compatibility) and minimum path cover problems both reduce elegantly to maximum flow, showing the technique’s reach well beyond problems that look like flow problems at first glance.

Practice Tip: When a new problem asks for a maximum count of disjoint paths, an optimal pairing/matching, or feasibility subject to capacity-like constraints, explicitly ask what the source, sink, nodes, edges, and capacities would need to be to model it as a maximum flow problem.

Common Mistake: Forgetting that Ford-Fulkerson’s augmenting paths must be found in the residual graph, not the original graph — the residual graph’s reverse edges let the algorithm effectively “undo” previously sent flow if a better overall routing is later found, and omitting them is a common source of incorrect maximum flow implementations.

Important Questions:

• Q1: How does maximum bipartite matching reduce to a maximum flow problem? A flow network is built with a source node connected by unit-capacity edges to every node on one side of the bipartite graph, a sink node connected by unit-capacity edges from every node on the other side, and unit-capacity edges connecting each compatible pair of nodes between the two sides; the maximum flow achievable in this network then exactly equals the maximum number of compatible pairs that can be matched simultaneously without reusing any node, because each unit of flow through the network corresponds to using exactly one compatible pairing, and the unit capacities everywhere prevent any node from being matched more than once.
• Q2: What does the maxflow-mincut theorem state, and why does it provide more than just an upper bound on achievable flow? It states that the maximum possible flow from source to sink in a flow network is always exactly equal to the minimum-capacity cut separating them; this is more than an intuitive upper bound (which is easy to see, since flow can never exceed any cut’s total capacity) because the theorem additionally guarantees this bound is always achievable exactly — there always exists some cut whose capacity exactly matches the true maximum flow, giving a concrete way to prove a candidate flow is truly maximum by exhibiting a matching cut, rather than only being able to show it is no worse than some upper bound.

Part III: Advanced Topics

Chapter 21: Number Theory

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: primes and factors, modular arithmetic, solving equations, Fibonacci numbers

Opening Part III, this chapter develops the number-theoretic algorithms behind many advanced competitive programming problems. It covers efficient primality testing and factorization for single numbers, modular arithmetic (including fast modular exponentiation and modular inverses via the extended Euclidean algorithm), and solving linear Diophantine equations. It closes with a look at Fibonacci numbers and other classic number-theoretic sequences as recurring examples of the algorithmic techniques developed throughout the chapter.

Key Points:

• Trial division up to the square root of a number is the standard basic technique for both primality testing and factorization of individual numbers, running in O(√n) time.
• The sieve of Eratosthenes efficiently precomputes primality (or smallest prime factor) for every number up to some limit at once, in O(n log log n) time, much faster than testing each number individually when many queries are needed.
• Modular exponentiation by repeated squaring computes a^b mod m efficiently in O(log b) time, essential for problems involving large exponents combined with a modulus.
• The extended Euclidean algorithm computes both the greatest common divisor of two numbers and the coefficients of Bézout’s identity, which is exactly what’s needed to compute modular multiplicative inverses (when they exist).
• Linear Diophantine equations (of the form ax + by = c) can be solved for integer solutions using the extended Euclidean algorithm, connecting the chapter’s individual techniques into a general equation-solving tool.

Memory Tip: Remember when to reach for the sieve of Eratosthenes versus trial division: a single number’s primality is fine to check with O(√n) trial division, but many queries about numbers up to some shared limit call for precomputing everything at once with a sieve instead.

Common Mistake: Computing a modular inverse by naively trying every possible value until one works, instead of using the extended Euclidean algorithm — the naive approach can take O(m) time, while the extended Euclidean algorithm computes the same modular inverse correctly in O(log m) time, and is also the standard tool for solving general linear Diophantine equations.

Important Questions:

• Q1: Why is the sieve of Eratosthenes preferred over trial division when a problem requires primality information for many numbers up to some shared limit? Trial division checks a single number’s primality in O(√n) time, so checking many numbers individually this way would cost O(k√n) for k numbers; the sieve of Eratosthenes instead computes primality (or the smallest prime factor) for every number up to a limit n simultaneously in a single O(n log log n) pass, by repeatedly marking off multiples of each found prime, which is dramatically faster overall whenever primality information is needed for many numbers up to a shared limit rather than for just one isolated number.
• Q2: How does the extended Euclidean algorithm enable computing a modular multiplicative inverse? The extended Euclidean algorithm finds integers x and y satisfying ax + by = gcd(a, b) for any two integers a and b; when a and m are coprime (gcd(a, m) = 1), applying the extended Euclidean algorithm to a and m finds an x satisfying ax + my = 1, which means ax ≡ 1 (mod m) — exactly the definition of x being the modular multiplicative inverse of a modulo m, computed in O(log m) time rather than by any slower trial-based search.

Chapter 22: Combinatorics

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: binomial coefficients, Catalan numbers, inclusion-exclusion, Burnside’s lemma

This chapter develops counting techniques for problems that ask “how many ways” rather than “find one way”. Binomial coefficients are covered both for their direct combinatorial meaning and for efficient computation modulo a prime using precomputed factorials and modular inverses. Catalan numbers are introduced as the answer to a family of classic counting problems (balanced parentheses, binary tree shapes, and more) that share a common recursive structure. The chapter closes with two more advanced general-purpose counting tools: the inclusion-exclusion principle for counting unions of overlapping sets, and Burnside’s lemma for counting distinct objects up to symmetry.

Key Points:

• Binomial coefficients (n choose k) count the number of ways to choose k items from n, and can be computed efficiently modulo a prime using precomputed factorials and their modular inverses, giving O(1) queries after O(n) preprocessing.
• Catalan numbers count a surprising variety of combinatorial structures that all share the same underlying recursive structure, including balanced parenthesis sequences, distinct binary tree shapes with n nodes, and certain lattice path counts.
• The inclusion-exclusion principle correctly counts the size of a union of overlapping sets by adding individual set sizes, subtracting pairwise intersections, adding back triple intersections, and so on, alternating signs.
• Inclusion-exclusion is a general technique applicable well beyond simple set-counting problems, often used to count objects satisfying “none of” a list of forbidden properties by counting the complement via unions of the forbidden cases.
• Burnside’s lemma counts the number of distinct objects up to symmetry (such as distinct necklace colorings up to rotation) by averaging, over every symmetry operation in the relevant group, the number of objects left unchanged by that operation.

Memory Tip: Recognize a Catalan number problem by its recursive shape: whenever a counting problem naturally splits into two independent, smaller instances of the exact same problem at every possible split point (like balanced parentheses splitting at the matching bracket), Catalan numbers are likely involved.

Common Mistake: Simply adding the sizes of overlapping sets to count their union, without subtracting the overlaps — this double-counts elements that belong to more than one set; the inclusion-exclusion principle’s alternating add/subtract/add pattern across all possible intersections is specifically what corrects for this overcounting.

Important Questions:

• Q1: How does precomputing factorials and modular inverses allow binomial coefficients to be computed in O(1) time per query? The binomial coefficient formula n choose k equals n! divided by (k! times (n-k)!); by precomputing every factorial value up to the maximum needed n modulo a prime, and precomputing the modular inverse of every one of those factorials as well, any specific binomial coefficient can then be computed with just a constant number of multiplications (using the precomputed factorial and inverse-factorial values directly) rather than recomputing factorials or inverses from scratch for every individual query, which would otherwise cost more time per query.
• Q2: What does Burnside’s lemma compute, and why is simply counting all possible colorings (or arrangements) without it usually incorrect for “distinct up to symmetry” counting problems? Burnside’s lemma counts the number of genuinely distinct objects when arrangements that can be transformed into each other by some symmetry (like rotation or reflection) are considered the same object, by averaging, over every symmetry operation in the relevant group, the number of arrangements left completely unchanged by that specific operation; simply counting all raw arrangements without accounting for symmetry overcounts the true number of distinct objects, since many raw arrangements that look different are actually the same object once symmetry equivalences (like two colorings that are just rotations of each other) are correctly taken into account.

Chapter 23: Matrices

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: matrix operations, linear recurrences, graphs and matrices, Kirchhoff’s theorem

This chapter develops matrices as both a computational tool and a modeling framework. Basic matrix operations (multiplication in particular) are covered alongside matrix exponentiation by repeated squaring, which lets linear recurrences (like the Fibonacci sequence, revisited from the very start of the book) be computed in logarithmic time instead of linear time. The chapter also develops the connection between graphs and matrices — an adjacency matrix’s powers count walks of a given length — and closes with Kirchhoff’s theorem, a striking result counting a graph’s spanning trees using a matrix determinant.

Key Points:

• Matrix multiplication is the core operation this chapter builds on, and understanding its O(n^3) naive complexity (or faster, via Strassen-style algorithms from earlier in the broader field) matters for applications like repeated squaring.
• Any linear recurrence (a sequence where each term is a fixed linear combination of previous terms, like Fibonacci) can be expressed as repeated multiplication by a fixed transformation matrix, letting matrix exponentiation by repeated squaring compute the n-th term in O(log n) matrix multiplications instead of O(n) simple steps.
• Raising a graph’s adjacency matrix to the k-th power gives, in each entry, the number of distinct walks of exactly length k between the corresponding pair of nodes, connecting matrix powers directly to graph structure.
• This walk-counting connection lets matrix exponentiation solve certain graph problems (like counting walks of a given length, or finding shortest paths of a bounded number of edges) efficiently for large k using the same repeated-squaring technique.
• Kirchhoff’s theorem (the matrix-tree theorem) counts the exact number of distinct spanning trees of a graph as a specific determinant of a matrix built from the graph’s structure (the graph Laplacian), a surprising and elegant connection between linear algebra and combinatorics.

Memory Tip: Recognize when matrix exponentiation applies: whenever a sequence’s next term is a fixed linear combination of a fixed number of previous terms, and you need the n-th term for a very large n, matrix exponentiation gives O(log n) time instead of the O(n) of direct iteration.

Common Mistake: Computing the n-th term of a linear recurrence like Fibonacci by direct iteration when n is extremely large (well beyond what O(n) time permits) — the chapter’s whole point is that expressing the recurrence as matrix multiplication and using repeated squaring brings this down to O(log n) matrix multiplications, which matters enormously once n grows into the billions or beyond.

Important Questions:

• Q1: How does expressing the Fibonacci recurrence as a matrix let it be computed in O(log n) time instead of O(n)? The Fibonacci recurrence can be written as a matrix equation where multiplying a vector containing two consecutive Fibonacci numbers by a fixed 2×2 transformation matrix produces the next pair; computing the n-th Fibonacci number then becomes equivalent to raising this fixed transformation matrix to the n-th power (and applying it to the initial pair), and matrix exponentiation by repeated squaring computes this n-th power using only O(log n) matrix multiplications, each of which takes constant time for a fixed small matrix size, giving overall O(log n) time instead of the O(n) time needed to iterate the recurrence one step at a time.
• Q2: What does raising a graph’s adjacency matrix to the k-th power represent, and how is this useful? If A is a graph’s adjacency matrix, then the entry in row i and column j of A raised to the k-th power gives exactly the number of distinct walks of length exactly k from node i to node j (where a walk, unlike a path, is allowed to repeat nodes and edges); this is useful because it turns certain graph-counting problems — such as counting walks of a specific length, or, with small modifications, finding whether a path of at most k edges exists between two nodes — into matrix exponentiation problems that can be solved efficiently with repeated squaring, especially valuable when k is very large.

Chapter 24: Probability

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: probability calculation, events, random variables, Markov chains

This chapter develops basic probability theory as it applies to competitive programming problems, covering how to calculate probabilities of events, combine probabilities of independent and dependent events, and work with random variables and their expected values (including the useful linearity of expectation, which holds even for dependent random variables). It closes with Markov chains — systems that move between states with fixed transition probabilities — as a framework for problems involving long-run or step-by-step probabilistic behavior.

Key Points:

• Basic probability calculations combine simpler events using rules for independent events (multiplying probabilities) and mutually exclusive events (adding probabilities), forming the foundation for more complex probability problems.
• A random variable’s expected value summarizes its average outcome across all possibilities, weighted by probability, and is often easier to compute for a complex quantity by breaking it into simpler pieces.
• Linearity of expectation states that the expected value of a sum of random variables always equals the sum of their individual expected values, even when those variables are not independent — a surprisingly powerful simplification tool.
• Many seemingly complex expected-value problems become tractable by decomposing a complicated random variable into a sum of simple indicator variables (each either 0 or 1) and applying linearity of expectation to each piece separately.
• A Markov chain models a system moving between a fixed set of states with fixed transition probabilities depending only on the current state, and questions about its long-run or step-by-step behavior can often be answered using the matrix techniques from the previous chapter.

Memory Tip: When an expected value looks hard to compute directly, try breaking the quantity into a sum of simple 0/1 indicator variables and applying linearity of expectation to each separately — it works even when the underlying events are not independent of each other.

Common Mistake: Assuming linearity of expectation requires the random variables involved to be independent — this is a common misconception; linearity of expectation holds unconditionally for the sum of any random variables, independent or not, which is exactly what makes it such a broadly useful simplification technique for otherwise complicated expected-value calculations.

Important Questions:

• Q1: Why is linearity of expectation considered such a powerful tool, given that it holds even for dependent random variables? Many expected-value problems involve a complicated overall quantity that would be very difficult to analyze directly, especially when the underlying random events influence each other (are dependent); because linearity of expectation guarantees the expected value of a sum of random variables always equals the sum of their individual expected values regardless of any dependence between them, a complicated quantity can be decomposed into simpler pieces (often simple 0/1 indicator variables), each of whose individual expected value is easy to compute separately, and then simply summed together to get the correct overall answer without needing to reason about the complex dependencies directly.
• Q2: What defines a Markov chain, and why does the “depends only on the current state” property matter? A Markov chain models a system that moves between a fixed set of states over time, where the probability of transitioning to each possible next state depends only on the current state, not on the full history of how the system arrived there (a property sometimes called “memorylessness”); this property matters because it is exactly what allows the system’s transition probabilities to be captured compactly in a single transition matrix, letting questions about the system’s behavior after many steps, or in the long run, be answered efficiently using matrix exponentiation and related matrix techniques from the previous chapter, rather than needing to track the entire history of past states.

Chapter 25: Game Theory

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: game states and strategies, the Nim game, the Sprague-Grundy theorem

This chapter covers combinatorial game theory — two-player games with no randomness or hidden information, where players alternate moves until someone cannot move (and loses). It develops the general technique of classifying game states as winning or losing positions via backward reasoning, then covers the classic Nim game in depth, including its elegant closed-form solution using the XOR of pile sizes. The chapter closes with the Sprague-Grundy theorem, which generalizes Nim’s solution to a huge class of combinatorial games by reducing any such game to an equivalent Nim pile.

Key Points:

• In a combinatorial game where the player unable to move loses, every game state can be classified as either a winning position (the player to move can force a win) or a losing position (any move leads to a winning position for the opponent), determined by backward recursive reasoning from terminal states.
• The Nim game (players remove any positive number of objects from one of several piles, and the player unable to move loses) has an elegant closed-form solution: a position is losing for the player about to move if and only if the XOR of all pile sizes is zero.
• The Sprague-Grundy theorem assigns every state of a huge class of combinatorial games (impartial games, where both players have the same available moves from any given state) a single number, the Grundy number, capturing everything relevant about that state’s game-theoretic value.
• A state’s Grundy number is computed as the minimum excludant (“mex”) — the smallest non-negative integer not among the Grundy numbers reachable in one move from that state — generalizing the same recursive idea behind Nim’s solution.
• The Sprague-Grundy theorem shows that a combination of several independent impartial games behaves exactly like a Nim game whose pile sizes are the individual games’ Grundy numbers, letting Nim’s simple XOR rule solve an enormous variety of seemingly unrelated games.

Memory Tip: Remember Nim’s rule as “XOR to zero means you lose”: if the XOR of all current pile sizes is zero, the player about to move is in a losing position (assuming optimal play from both sides); any nonzero XOR is a winning position for the player about to move.

Common Mistake: Assuming that classifying a game state as “winning” or “losing” only requires checking whether at least one move leads to a good outcome, without correctly alternating the win/lose logic between whose turn it is — a state is a winning position specifically when at least one available move leads to a losing position for the opponent, and a losing position specifically when every available move leads to a winning position for the opponent; getting this alternation backward inverts the entire analysis.

Important Questions:

• Q1: What is the closed-form rule for determining whether a Nim position is a losing position for the player about to move, and why does XOR specifically capture this? A Nim position is a losing position for the player about to move if and only if the bitwise XOR of all the pile sizes equals zero; XOR captures this because it is exactly the operation for which a position with XOR zero has the property that every possible move (removing objects from exactly one pile) necessarily changes the XOR to a nonzero value, while a position with nonzero XOR always has at least one available move that changes the XOR back to zero — meaning a player facing an XOR-zero position is always forced into leaving a nonzero-XOR position for the opponent, and a player facing a nonzero-XOR position can always restore XOR to zero for the opponent, which is precisely the recursive structure of winning and losing positions.
• Q2: What does the Sprague-Grundy theorem let you do with a combination of several independent impartial games being played simultaneously? The Sprague-Grundy theorem lets a combination of several simultaneously-played independent impartial games be analyzed as if it were a single Nim game, where each individual game contributes one “pile” whose size is that game’s own Grundy number (computed via the mex rule from the states reachable within that individual game); the combined game’s overall winning/losing status is then determined exactly the same way as ordinary Nim — by XORing together each individual game’s Grundy number — which means Nim’s simple, efficiently computable XOR rule can be reused to solve a very wide variety of games that don’t look anything like Nim on the surface.

Chapter 26: String Algorithms

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: string matching, the Z-array, string hashing, pattern matching, suffix arrays

This chapter develops efficient algorithms for problems about strings, moving well beyond naive character-by-character comparison. The Z-array (giving, for every position, the length of the longest substring starting there that matches the string’s prefix) is developed as a versatile tool for pattern matching in linear time. String hashing provides a fast, probabilistic way to compare substrings for equality in O(1) after preprocessing. The chapter closes with suffix arrays, a powerful structure sorting all of a string’s suffixes, enabling a wide range of advanced string queries efficiently.

Key Points:

• The Z-array, computed in linear time, gives at every position the length of the longest substring starting there that matches the string’s own prefix, and is a versatile building block for many string problems including pattern matching.
• Using the Z-array (or similar techniques), finding all occurrences of a pattern string within a longer text string can be done in linear time in the combined length of both strings, far faster than naive O(nm) character-by-character checking.
• String hashing maps each substring to a numeric hash value, allowing two substrings to be compared for equality in O(1) time after O(n) preprocessing, at the cost of a small, controllable probability of a hash collision giving a false positive.
• Using multiple independent hash functions together reduces the already-small probability of a hash collision to a negligible level, making string hashing a reliable practical tool despite being technically probabilistic rather than deterministic.
• A suffix array sorts all of a string’s suffixes lexicographically, and combined with the related longest common prefix (LCP) array, enables a wide range of advanced string queries (like counting distinct substrings, or finding the longest repeated substring) efficiently.

Common Mistake: Relying on a single string hash function without considering collision risk in an adversarial contest setting can be exploited — using two independent hash functions together (different moduli and/or bases) makes an accidental or deliberate collision astronomically unlikely.

Common Mistake: Comparing substrings directly character by character inside a loop that runs many times, instead of using string hashing or another linear-time technique — naive substring comparison costs O(length) per comparison, and doing this repeatedly across many queries can easily blow past the time limit where O(1) hash-based comparison after preprocessing would have been fast enough.

Important Questions:

• Q1: How does string hashing allow two substrings to be compared for equality in O(1) time? String hashing precomputes, in O(n) time, the hash value of every prefix of the string using a formula that lets the hash of any substring be derived quickly by combining two precomputed prefix hashes (using modular arithmetic); once this preprocessing is done, computing the hash of any specific substring, and therefore comparing two substrings for equality by comparing their hash values, takes only O(1) time per comparison, in contrast to the O(length) time a direct character-by-character comparison would require for each query.
• Q2: Why is it good practice to use two independent hash functions together for string hashing, rather than relying on just one? Any single hash function, no matter how well chosen, has some nonzero probability that two genuinely different substrings happen to produce the same hash value (a collision), and in an adversarial competitive programming setting, test cases can sometimes be deliberately constructed to trigger collisions against a commonly used single hash function and modulus; using two independent hash functions (with different moduli and/or different bases) together, and only treating two substrings as equal when both hash values match, multiplies together the already-small individual collision probabilities, making an accidental or deliberately engineered collision astronomically unlikely in practice.

Chapter 27: Square Root Algorithms

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: square root decomposition, batch processing

This chapter develops square root decomposition as a general algorithmic strategy: splitting a problem’s input into roughly √n equally-sized blocks so that both a full scan across all blocks and a full scan within a single block cost roughly √n, balancing the two costs against each other. It’s applied to range-query problems as a simpler, if sometimes less efficient, alternative to segment trees, and to batch processing offline queries, where sorting or grouping queries cleverly using a √n-sized block structure can make an otherwise expensive sequence of queries collectively efficient.

Key Points:

• Square root decomposition splits an array or input into roughly √n blocks of size roughly √n each, so that operations combining across-block and within-block work both cost around O(√n).
• For range queries, square root decomposition offers a simpler, if generally somewhat less efficient (O(√n) rather than O(log n)), alternative to a segment tree, and can be easier to adapt to unusual or non-standard combining operations.
• Applying square root decomposition to updates as well as queries requires care about how much information needs to be recomputed when a single block’s contents change.
• Batch (offline) processing of many range queries can use a √n-sized block structure to sort or group queries cleverly (a technique closely related to Mo’s algorithm), so that answering all queries together costs much less overall than answering each independently.
• Square root decomposition is presented as a general, flexible strategy rather than one fixed algorithm — the same underlying idea (balance across-block and within-block cost around √n) can be adapted to many different specific problems.

Practice Tip: Consider square root decomposition specifically when a segment tree feels awkward to apply — for example, when the combining operation doesn’t have a simple associative structure, or when queries and updates have an unusual shape that’s easier to reason about at the block level.

Common Mistake: Reaching for square root decomposition by default even when a segment tree would apply cleanly and more efficiently — O(√n) per query, while often fast enough, is asymptotically worse than a segment tree’s O(log n) per query; square root decomposition is most valuable specifically when its simplicity or flexibility solves a problem a segment tree handles awkwardly, not as a universal first choice.

Important Questions:

• Q1: Why does splitting an array into roughly √n blocks of roughly √n elements each balance the cost of across-block and within-block operations? If there are roughly √n blocks total, then scanning or combining information across all blocks costs O(√n); if each individual block contains roughly √n elements, then scanning within a single block also costs O(√n); choosing the block size to be exactly around √n is what makes these two costs balance against each other, since making blocks larger would reduce the number of blocks (cheaper across-block cost) but increase the within-block scan cost, and vice versa — the √n choice specifically minimizes the combined worst-case cost of an operation that might need to touch both some full blocks and part of one partial block.
• Q2: In what situation might square root decomposition be preferred over a segment tree for a range query problem, despite its worse asymptotic complexity? Square root decomposition can be preferred when the query’s combining operation is unusual, non-standard, or doesn’t fit cleanly into a segment tree’s requirement of an efficiently combinable, typically associative operation over contiguous ranges; because square root decomposition works at the coarser level of whole blocks plus a partial remainder, it can sometimes be easier to adapt to such unusual combining logic, or to unusual update patterns, even though its O(√n) per-operation cost is asymptotically worse than a segment tree’s O(log n) — making it a pragmatic, simpler-to-implement choice in situations where a segment tree would be either very awkward to adapt or not obviously applicable at all.

Chapter 28: Segment Trees Revisited

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: lazy propagation, dynamic-sized segment trees, binary indexed tree extensions, two-dimensional queries

Returning to segment trees from Chapter 9, this chapter covers the more advanced techniques needed for harder range-query problems. Lazy propagation extends segment trees to support efficient range updates (not just point updates), deferring update work to child nodes until it’s actually needed. Dynamic-sized (or implicit/sparse) segment trees handle enormous coordinate ranges without allocating memory for every possible position upfront. The chapter also revisits the binary indexed tree with extensions for range updates, and closes with a look at extending range-query techniques into two dimensions.

Key Points:

• Lazy propagation extends a segment tree to support range updates (applying a change to every element in a range) in O(log n) time, by deferring the actual work of pushing an update down to child nodes until those children are actually needed for a later query or update.
• Without lazy propagation, a naive range update on a segment tree would need to update every affected leaf individually, costing O(n) in the worst case instead of the O(log n) lazy propagation achieves.
• Dynamic-sized (implicit or sparse) segment trees handle problems with an enormous possible coordinate range (too large to allocate an array for upfront) by only creating tree nodes for regions actually touched by an update or query, keeping memory usage proportional to the number of operations rather than the full coordinate range.
• The binary indexed tree from Chapter 9 can be extended, using two coordinated BITs, to support efficient range updates combined with range sum queries, an alternative to a lazy-propagation segment tree for that specific combination of operations.
• Range-query techniques extend into two dimensions (for grid-based problems) using combinations of the one-dimensional techniques, such as a 2D binary indexed tree or nested segment trees, though at increased complexity and memory cost.

Memory Tip: Remember lazy propagation’s core idea as “defer, don’t push immediately”: mark a node with a pending update and stop there, only actually pushing that pending update down to its children the next time those specific children need to be visited for a query or a different update.

Common Mistake: Implementing a segment tree range update by naively looping over and updating every individual leaf in the range — this costs O(range size) per update, which defeats the purpose of using a segment tree in the first place for problems with many range updates; lazy propagation’s deferred-update technique is what’s needed to keep range updates down to O(log n).

Important Questions:

• Q1: How does lazy propagation achieve O(log n) time for a range update, when naively updating every affected leaf would cost O(n)? Instead of immediately pushing an update all the way down to every individual leaf in the affected range, lazy propagation applies the update directly to the O(log n) tree nodes that together exactly cover the update range, and marks each of those nodes with a pending (“lazy”) update describing what still needs to be applied to their children if those children are ever visited later; this pending update is only actually pushed down to a node’s children the next time that specific node needs to be traversed further (for a later query or update), which means the cost of fully propagating an update down to every individual leaf is spread out and only paid for the specific leaves that are actually visited later, rather than being paid upfront for the entire range every time.
• Q2: Why are dynamic-sized (implicit) segment trees needed for problems with an enormous coordinate range, and what do they save compared to a standard segment tree? A standard segment tree allocates a fixed array sized proportional to the full coordinate range it covers, which becomes impossible when that range is extremely large (for example, coordinates up to 10^9) even though the actual number of distinct positions touched by queries and updates might be much smaller; a dynamic-sized segment tree instead only creates tree nodes on demand, specifically for regions that an update or query actually touches, keeping the total memory used proportional to the number of operations performed rather than to the full theoretical coordinate range, which is what makes it feasible to handle such enormous coordinate ranges at all.

Chapter 29: Geometry

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: complex numbers for geometry, points and lines, polygon area, distance functions

This chapter develops the basic computational geometry toolkit: representing points (sometimes conveniently as complex numbers), working with lines and line segments, computing a polygon’s area using the shoelace formula, and various distance functions between geometric objects. Careful attention is paid throughout to numerical precision and the subtle edge cases (collinear points, degenerate shapes) that make geometry problems notoriously easy to get almost-but-not-quite right, setting up the more advanced sweep line algorithms covered in the book’s final chapter.

Key Points:

• Points in the plane are often conveniently represented as complex numbers, since operations like rotation, translation, and computing angles between points map naturally onto complex number arithmetic.
• The cross product of two vectors (derived from three points) determines their relative orientation — clockwise, counterclockwise, or collinear — a building block used constantly throughout computational geometry algorithms.
• The shoelace formula computes a simple polygon’s area directly from its vertex coordinates using a specific alternating-sum formula, without needing to decompose the polygon into triangles manually.
• Distance functions between different types of geometric objects (point-to-point, point-to-line, point-to-segment) each require slightly different formulas, and correctly handling their edge cases (like a point whose closest point on a segment is one of the segment’s endpoints) is a recurring source of subtle bugs.
• Geometry problems are highlighted as especially prone to precision and edge-case errors (floating-point rounding, collinear or coincident points, degenerate zero-length segments), making careful, defensive implementation a genuine skill emphasized throughout the chapter.

Common Mistake: Comparing floating-point coordinates or computed geometric values for exact equality is a classic source of bugs — small floating-point rounding errors mean two values that are mathematically equal can differ slightly in code, so comparisons should generally use a small tolerance (epsilon) instead of exact equality.

Common Mistake: Failing to specifically handle degenerate geometric cases — collinear points, zero-length segments, or a point lying exactly on a line — when implementing a geometry algorithm; these edge cases are common in contest test data specifically because they’re easy for a solution to overlook, and a solution that only handles the “generic” case will fail on them.

Important Questions:

• Q1: Why is the cross product of vectors such a widely reused building block throughout computational geometry algorithms? The sign of the cross product of two vectors (derived from three points) directly indicates their relative rotational orientation — whether going from the first vector to the second is a clockwise turn, a counterclockwise turn, or the three points are collinear (cross product exactly zero); this single, cheaply computable piece of information (orientation) underlies many higher-level geometric questions, such as determining which side of a line a point falls on, checking whether a polygon is convex, or determining the direction of a turn while building a convex hull, which is why it appears repeatedly as a core building block across many different geometry algorithms.
• Q2: Why does the chapter emphasize using a small tolerance (epsilon) instead of exact equality when comparing floating-point geometric values? Floating-point arithmetic cannot represent most real numbers exactly, so a sequence of geometric calculations (like computing an intersection point or an angle) that is mathematically guaranteed to produce a specific exact value can instead produce a value that differs from the true mathematical answer by a tiny rounding error; comparing such computed values for exact equality can therefore incorrectly report two mathematically equal quantities as different (or vice versa) due to this accumulated rounding error, which is why geometry implementations generally compare floating-point values by checking whether their difference falls within a small tolerance (epsilon) rather than requiring bit-for-bit exact equality.

Chapter 30: Sweep Line Algorithms

Difficulty: Advanced · Late Semester · Advanced Mathematics for Algorithms · Key topics: line segment intersections, the closest pair problem, the convex hull

Closing the book, this chapter develops the sweep line technique: conceptually moving an imaginary line across the plane (typically left to right) and processing geometric events in that order, maintaining just enough information about objects currently “active” near the sweep line to answer the problem efficiently. It’s applied to three classic problems: detecting whether any pair of line segments intersects, finding the closest pair of points among a set, and computing the convex hull of a set of points — each turning an apparently quadratic brute-force problem into an efficient O(n log n) algorithm.

Key Points:

• The sweep line technique conceptually moves a line across the plane, processing relevant geometric “events” (like a segment starting or ending, or a point being reached) in sorted order, while maintaining an efficient data structure representing only the objects currently near the sweep line.
• Detecting whether any pair of line segments among many intersects can be solved in O(n log n) time using a sweep line that tracks the current vertical ordering of active segments, checking only neighboring segments for potential intersections rather than all pairs.
• The closest pair of points problem, naively O(n^2) by checking every pair, is solved in O(n log n) using a sweep line combined with a clever argument bounding how many nearby points need to be checked at each step.
• Computing the convex hull (the smallest convex polygon containing all given points) is solved in O(n log n) time using a sweep-based approach that sorts points and maintains the hull’s boundary incrementally as points are processed.
• All three of this chapter’s classic problems share the same underlying pattern: an apparently O(n^2) brute-force problem is reduced to O(n log n) by exploiting geometric structure to avoid ever having to compare every pair of objects directly.

Memory Tip: Recognize a sweep line opportunity by the shared pattern across this chapter’s problems: whenever a brute-force approach would check every pair of objects (segments, points), but only “nearby” objects at any given moment can actually matter, sorting events and sweeping across them while maintaining just the currently-relevant objects is likely to give a large speedup.

Common Mistake: Checking every pair of line segments (or every pair of points) directly for the intersection or closest-pair problems, resulting in an O(n^2) solution — the whole point of the sweep line technique in this chapter is that maintaining only the currently “active” or “nearby” objects as the sweep progresses avoids ever needing to compare every possible pair, bringing the complexity down to O(n log n).

Important Questions:

• Q1: What is the core idea shared by the sweep line solutions to the segment intersection, closest pair, and convex hull problems in this chapter? In each case, a naive brute-force approach that checks every possible pair of objects (segments or points) would cost O(n^2) time; the sweep line technique instead processes the objects in a specific sorted order (by x-coordinate, typically), maintaining only a compact, efficiently-queryable representation of the objects currently “active” or “nearby” the sweep line’s current position, which means that at each step only a small, bounded number of comparisons against currently-relevant neighbors are needed rather than comparisons against every other object — this is what brings each problem’s complexity down from O(n^2) to O(n log n).
• Q2: Why does the sweep line approach to detecting line segment intersections only need to check neighboring segments in the current vertical ordering, rather than all pairs? As the sweep line moves across the plane, the active line segments it currently crosses can be maintained in sorted order by their vertical position at the sweep line’s current x-coordinate; two segments can only possibly intersect at a point where their relative vertical order would swap, which can only first happen between segments that are currently adjacent to each other in this sorted order — segments that are not adjacent would have to cross some segment currently between them first, so checking only adjacent pairs at each event (when the sweep line reaches a segment’s endpoint or a discovered intersection) is sufficient to detect every actual intersection without ever needing to compare every possible pair of segments directly.

Read or Download Competitive Programmer’s Handbook for Free

This book is free from its official source — Antti Laaksonen publishes the complete PDF of the Competitive Programmer’s Handbook directly on the CSES (Code Submission Evaluation System) website he maintains, free for anyone to read or download, alongside the companion CSES Problem Set for practice. The legitimate free way to read or download the complete book is the official page below.

How to Study This Book

Part I (Chapters 1–10) is the essential foundation — time complexity, sorting, data structures, complete search, greedy algorithms, dynamic programming, amortized analysis, range queries, and bit manipulation are assumed knowledge for nearly everything in Parts II and III, so work through them in order and don’t rush the dynamic programming chapter in particular.

Part II (Chapters 11–20) builds cumulatively on graph traversal — DFS and BFS from Chapter 12 underlie the shortest path, tree, and flow algorithms that follow, so make sure basic graph traversal feels completely comfortable before tackling strong connectivity or network flow.

Part III (Chapters 21–30) is intentionally more modular than Parts I and II — number theory, combinatorics, probability, game theory, string algorithms, and geometry are largely independent of each other, so these chapters can be read in whatever order matches a specific contest syllabus or interest, rather than strictly in sequence.

Treat every chapter’s worked examples as problems to re-derive independently before reading the solution — this book is written for active problem-solving practice, and the CSES Problem Set it links to is designed to be solved chapter by chapter alongside reading.

Revisit Chapters 9 (Range Queries) and 28 (Segment Trees Revisited) together once Part III’s harder chapters are underway — several advanced topics reuse and extend the range-query structures introduced early in the book.

Used In These Programs

This book is used as a Competitive Programming or Algorithms Practice elective text, and as contest training reference material, in: BSCS and Programming coursework. Browse all Computer Science category books.

Who Should Read This

Competitive Programmer’s Handbook is written for students and self-learners preparing for programming contests (such as ICPC, national olympiads, or online judges), and for anyone who wants a fast-paced, problem-oriented tour of algorithmic techniques after an introductory data structures and algorithms course. It assumes comfort with basic programming and moves quickly from foundational techniques through graph algorithms to advanced mathematical and geometric algorithms, always oriented around solving contest-style problems efficiently.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Competitive Programming or Algorithms Practice elective, or for students preparing independently for ICPC and similar contests, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners building contest and technical-interview problem-solving skills.

FAQs

Related Books

• Problem Solving with Algorithms and Data Structures using Python (a gentler, implementation-focused companion for readers who want more foundational depth before this book’s fast-paced contest tour)
• Data Structures in C++ – Aikman Series (foundational data structures background that pairs naturally with this book’s Data Structures and Range Queries chapters)
• Think OS – Allen B. Downey (systems-level background useful for readers building broader computer science fundamentals alongside contest-focused algorithmic training)

Competitive Programmer’s Handbook by Antti Laaksonen is a free, fast-paced, problem-oriented algorithms reference — covering basic techniques, graph algorithms, and advanced mathematical and geometric topics in 30 chapters across 3 parts, published directly by its author alongside the CSES Problem Set for practice. Browse more Computer Science books for the rest of your semester.

Competitive Programmer’s Handbook, by Antti Laaksonen. Free to read online from its official source, published by the author. Access for free at https://cses.fi/book/