Subject · 20 posts
Big-O counts steps and assumes every step costs the same. It does not. A cache miss costs a hundred steps, and that is why a linked list loses to an array.
Problem Solving From Zero21
Prefix sums break the moment an element changes. Two structures answer range questions and point updates in logarithmic time, and one of them is twenty lines.
Problem Solving From Zero19
Where does this pattern occur? Three answers in linear time, each with a different trade: one is easy and probabilistic, two are exact and need a table.
Problem Solving From Zero18
Sieves, greatest common divisors, modular arithmetic and inverses. Five tools, each about ten lines, that cover almost every number theory problem you will meet.
Problem Solving From Zero17
Two players, perfect information, no luck. Who wins? The answer comes from labelling positions, and one theorem collapses any such game into a single number.
Problem Solving From Zero16
Twelve lines of code, two operations, and a running time so close to constant that nobody bothers with the difference. Then minimum spanning trees for free.
Problem Solving From Zero15
Three algorithms, three different jobs. Which one to reach for depends on negative edges, on how many sources you have, and on nothing else.
Problem Solving From Zero14
BFS goes wide, DFS goes deep, and the difference is not stylistic. DFS answers questions about structure that a queue simply cannot see.
Problem Solving From Zero13
Half of all algorithm problems are graph problems in disguise. Here is how to represent a graph, and the search that finds shortest paths for free.
Problem Solving From Zero12
Knapsack is one recurrence with a dozen disguises. Learn the family, then learn to put a set of items in the state with a bitmask when n is small.
Problem Solving From Zero11
Four questions turn a problem into a dynamic program: what is the state, what is the answer for a state, what is the base, and in what order do you fill it.
Problem Solving From Zero10
The cheapest optimisation in programming: remember what you already worked out. One dictionary turns an exponential recursion into a linear one.
Problem Solving From Zero09
Recursion is hard because everyone traces it. The habit that makes it mechanical: write the contract, trust the smaller call, never trace the stack.
Problem Solving From Zero08
A greedy rule that passes the samples and fails the tests is the most common way to lose a contest. Here is how to tell a correct greedy rule from a plausible one.
Problem Solving From Zero07
Searching a sorted array is the easy half. The useful half is guessing the answer and asking a monotone yes-or-no question, with no array in sight.
Problem Solving From Zero06
A pointer is the address of a box, not the box. Once that clicks, dynamic memory, references and the linked list all fall out of the same idea. In C and C++.
Problem Solving From Zero05
You will almost never write a sort. You will constantly decide what to sort by, and that decision is where the problems are actually solved.
Problem Solving From Zero04
Two techniques that turn a quadratic loop into a linear one, on the humblest data structure there is. Range sums in constant time, and the sliding window.
Problem Solving From Zero03
Big-O is not a speed and not a stopwatch. It is a claim about the shape of a curve. Six shapes, where each one comes from, and the four rules for reading them.
Problem Solving From Zero02
Before any algorithm makes sense you need one habit: counting how many times a line runs. Here is that habit, built from four small C++ programs and a stopwatch.
Problem Solving From Zero01