The Playbook: A Process for Problems You Have Not Seen

By now you can write BFS, Dijkstra, a segment tree, KMP and a bitmask DP, and test each against a brute force. Yet a new problem rarely says "use Dijkstra". It describes drones, ticket prices or warehouse logs, and the algorithm is hidden behind the story. The typical failure in a contest or an interview is not forgetting an algorithm. It is one of these:

• Starting to code the first idea that comes to mind, then discovering twenty minutes later that it is O(n^2) with n = 2·10^5, or that it answers a slightly different question.
• Matching a keyword to a technique ("subarray" means two pointers) without checking the condition that makes the technique work.
• Trusting a solution because it passes the sample, then losing time to a wrong answer whose cause you cannot see.

This lesson turns the course into a process. First a checklist you can run in your head. Then a table from the signals in a problem statement to the techniques of lessons 1 to 11. Then four original problems, each solved the way you would solve it under time pressure: restate, brute force, dead ends, insight, code, stress test, complexity. The dead ends are part of the content: they show which checks prevented a wrong solution.

1. Restate the problem in one sentence, in terms of the data, not the story. "Count pairs of prefix sums with equal remainders, at least L apart" is something you can solve; "count good stretches of the conveyor log" is not yet. In an interview, say it out loud and ask whether you understood it.
2. Read the constraints and set a budget. Use the table from Complexity in Practice: n up to 2·10^5 means about O(n log n), n up to 20 invites O(2^n · n). Note the value ranges: do sums or counts need long long? Can values be negative or zero? Is the input possibly empty?
3. Write down a brute force and its complexity, even if it is hopeless at the limits. It proves you understand the question, and it becomes the reference for the stress test.
4. Find the bottleneck. What does the brute force repeat? Which quantity is recomputed for every candidate? The fast solution usually removes exactly that repetition.
5. Look up the signals in the table below. Each technique comes with a condition (monotone predicate, non-negative weights, values without negatives). Check the condition before you commit.
6. Code the solution in the solve(std::istream&, std::ostream&) form, with the types decided in step 2.
7. Test: the samples first, then a few cases by hand (empty, one element, all equal, the maximum values), then a stress test against the brute force from step 3, as in Fast I/O, Contest Templates and Stress Testing.
8. State the complexity in time and memory, worst case or expected, and check it against step 2.

The order matters more than it seems. Steps 2 and 3 come before any clever idea because they make the clever idea checkable: you know what it must beat, and you have something to compare it with.

The table maps phrases and constraint patterns to the technique that usually fits and the lesson that teaches it. It is a list of first guesses, not a decision procedure: the second column always has a condition you must verify.

Two rows share the same signal on purpose. "Route whose worst edge is as small as possible" points to two techniques, and the second worked problem below shows a small change to the statement that rules one of them out. That is the general lesson of the table: a signal narrows the search, the conditions decide.

A conveyor belt logs n weight changes a[0..n-1], each between -10^9 and 10^9. A stretch is a run of consecutive entries. Count the stretches of length at least L whose total is a multiple of k. Constraints: 1 <= n <= 2·10^5, 1 <= k <= 10^9, 1 <= L <= n.

Restate and budget. Count pairs (i, j) with j - i >= L and a[i] + ... + a[j-1] divisible by k. With n = 2·10^5 the budget is about O(n log n). The answer can reach n(n+1)/2, about 2·10^10, so it needs long long; so do the sums (up to 2·10^14 in absolute value).

Brute force. Fix the start, extend the end, keep a running sum: O(n^2), about 2·10^10 steps at the limit. Correct and short, so it becomes the reference.

A dead end. "Consecutive entries" and "length at least L" suggest a sliding window. But two pointers rely on the window's property changing monotonically as it grows, and with negative values a longer stretch can have a smaller or a larger total. Divisibility is not monotone even for positive values. The window idea fails its condition, so we drop it before writing it.

The insight. Write P[i] for the sum of the first i entries. The stretch [i, j) has total P[j] - P[i], and that is divisible by k exactly when P[i] and P[j] leave the same remainder modulo k. So the question becomes: for each j, how many earlier i with i <= j - L have the same remainder? Walk j upwards, add P[j - L] to a table of remainder counts as it becomes far enough away, and look up P[j].

The typical bug is the one from Number Theory and Bit Tricks: with negative entries, P[j] % k can be negative, and -1 and k - 1 land in different table entries although they are the same remainder. The stress test runs both versions.

Input: n k L, then the entries.

Check the sample by hand. The prefix sums are 0, 4, 3, 5, 10, 7, 10, with remainders 0, 1, 0, 2, 1, 1, 1 modulo 3. Pairs at least 2 apart with equal remainders: (0, 2) for remainder 0, and (1, 4), (1, 5), (1, 6), (4, 6) for remainder 1. That makes 5. The buggy version fails on a two-element input: the prefix sums 0, -1, 1 have remainders 0, -1, 1 modulo 2 instead of 0, 1, 1, so the stretch [2] is missed.

Complexity. O(n log n) time with std::map, O(n) memory. A std::unordered_map gives O(n) expected time, with the caveat about adversarial inputs from lesson 1. When k is small (say up to 10^6), a plain std::vector of counts indexed by remainder is simpler and faster still.

Charging pads 1..n are joined by m two-way flight corridors with lengths. A drone with range R can fly a corridor only if its length is at most R, and it recharges fully at every pad. Find the smallest R that lets it fly from pad 1 to pad n using at most K corridors, or print -1. Constraints: n up to 10^5, m up to 2·10^5, lengths up to 10^9.

Restate and budget. Minimize the largest corridor length on a route from 1 to n, subject to the route having at most K edges. The budget is about O((n + m) log m).

Dead ends first. Without the K limit this is the minimum bottleneck path from Union-Find and Minimum Spanning Trees: add corridors in order of length until 1 and n are connected. With the limit, that answer can be too small, because the route it finds may use many short corridors. A Dijkstra variant that minimizes the maximum edge has the same blind spot. Both techniques match the signal "minimize the worst edge" and both fail the condition, which here is "no other constraint on the route".

Brute force. The answer is always one of the m corridor lengths. For each length r, keep only corridors of length at most r and run BFS from pad 1 to get the fewest corridors to pad n; accept r if that number is at most K. That is O(m · (n + m)), about 6·10^10 at the limit.

The insight. The check "can the drone make it with range r?" is monotone: a larger range keeps every corridor a smaller range allowed, so the fewest-corridor count can only drop. Monotone checks over a sorted set of candidates are what binary search on the answer is for. Sort the lengths and find the first one that passes with std::ranges::partition_point.

The sample has a cheap route 1-2-3-4-5 with four corridors of length 3, a direct pair 1-3 (length 9) and 3-5 (length 7). The program answers the same network for K = 2, 3, 4.

With four corridors allowed, the answer is 3, which is what the bottleneck method returns regardless of K. With three, the route 1-2-3-5 needs range 7; with two, only 1-3-5 is short enough, and it needs 9. The random graphs include self-loops, parallel corridors, a single pad and disconnected networks, none of which the sample covers.

Complexity. Sorting is O(m log m). The binary search makes about log2(m) checks, about 18 for m = 2·10^5, and each check is a BFS in O(n + m). That is a few million steps, well inside the budget.

An access badge carries a code of n digits (leading zeros allowed). A code is valid if no two neighboring digits are equal and its digit sum is divisible by 3. How many valid codes are there, modulo 10^9 + 7? Constraint: n up to 10^5.

Restate and brute force. Count digit strings of length n with two local and global conditions. The brute force tries all 10^n codes: fine for n up to 6, hopeless beyond.

The signal. "How many, modulo 10^9 + 7" with n up to 10^5 points to a counting DP from Dynamic Programming I: Patterns. The question that defines the state: when we append the next digit, what do we need to know about the prefix so far? Only two things: its last digit (for the neighbor rule) and its digit sum modulo 3 (for the final check). In the five steps of that lesson: the state ways[d][r] is the number of valid prefixes of the current length that end in digit d and have digit sum r modulo 3; the transition appends any digit other than d; the order is by increasing length; the base case is length 1, one code per digit; the answer sums ways[d][0] over all d. That gives 10 · 3 = 30 states per length, and each state tries 10 next digits. The same "keep only what the future needs" idea drove the digit DP in Dynamic Programming II; here the length is fixed and neighbors interact.

A dead end. A closed formula is tempting: count codes without equal neighbors (10 · 9^(n-1)), then take about a third of them. The "about a third" is not exact, and making it exact requires exactly the bookkeeping the DP does. Under time pressure, the DP is the safer route to a correct answer.

The program prints the answers for n = 1, 2, 3 and 10^5, then compares the DP with the brute force for every n up to 6.

n = 2 can be checked by hand. The digits fall into three remainder classes: {0, 3, 6, 9}, {1, 4, 7} and {2, 5, 8}. A pair sums to a multiple of 3 if both are in the first class (4 · 4 - 4 = 12 pairs once equal neighbors are removed) or one is in each of the other two (3 · 3 · 2 = 18 pairs). Total 30.

Complexity. O(n · 10 · 3 · 10), about 3·10^7 simple steps for n = 10^5, and O(1) memory because only the previous length is kept. Every addition is reduced modulo kMod; without the reduction, the counts grow by a factor of about 9 per digit, and the total no longer fits in long long from n = 21 on. Grouping digits by remainder class would cut the state to 3 · 3 and the time by about a factor of 10, but the plain version already fits, and the plain version is the one you can write correctly in five minutes.

A shop sells bundles of one item from list A (n prices) and one from list B (m prices). There are n · m bundles. What is the price of the k-th cheapest bundle, counting bundles with equal prices separately? Constraints: n, m up to 2·10^5, prices from 1 to 10^9, 1 <= k <= n · m.

Restate and budget. Find the k-th smallest value of A[i] + B[j]. Note the types now: n · m reaches 4·10^10, so k overflows int, and the sums reach 2·10^9, just below the int limit of 2147483647. Use long long for both rather than rely on that margin.

Brute force. Generate all sums and sort them: O(nm log(nm)), with 4·10^10 sums at the limit. Not even the memory exists.

A dead end. A heap that pops the cheapest bundle k times, pushing its neighbors, is a well-known technique when k is small. Here k can be 4·10^10, so O(k log k) is out.

The insight. "The k-th smallest" can be turned into a yes/no question: is the answer at most x? It is exactly when at least k bundles cost at most x. That count is monotone in x, so we can binary search on x. Counting the bundles that cost at most x is a two-pointer pass over the sorted lists: as A[i] grows, the usable part of B only shrinks. The smallest x whose count reaches k is always the price of an actual bundle, because the count only changes at bundle prices.

The sorted bundle prices of the sample begin 11, 14, 17, 21, 24, so the fifth is 24. The stress test uses values from -20 to 20 although real prices are positive: a wider input space than the statement needs costs nothing and catches more, and many duplicates exercise the "count equal prices separately" rule.

Complexity. Sorting is O(n log n + m log m). The binary search runs over a value range of at most 2·10^9, so about 31 iterations, each O(n + m): roughly 1.2·10^7 steps at the limit.