Competitive Programming

A contest problem reads its input from stdin. A snippet here runs under WASI in a browser tab, and the tab has no stdin. Thus each chapter puts its input in the source as text, and parses the text in the same way as a file. The last chapter, the contest template, reads real stdin, and it takes the same reader. The algorithm does not change, and in exchange every program prints the steps that it took. The trace in the chapter is the trace that CI diffed against the compiler that the footer names.

Binary search is a window that gets smaller, not a clever midpoint. Every index that can be the answer stays inside items[lo..hi]. The loop ends when no index is left to examine.
The classic off-by-one does not return a wrong index. The search never returns, because a window of one has a middle equal to its own start.
(lo + hi) / 2 adds two valid indices, but their sum is not always valid. lo + (hi - lo) / 2 costs nothing and cannot overflow.
Two bounds give more information than one search. The start and the end of a value give a count, and you need no scan to get the count.
When two pointers converge on sorted data, they never have a choice about the next move. One index leaves the range at each step, so a walk that looks like a search costs one pass.
A sliding window adds the value that enters and subtracts the value that leaves. Every index enters once and leaves once, so a loop inside a loop is still linear. The shrink rule fails when a value can be negative.
std.sort.lowerBound passes the key first and the element second. If you write a comparator in the opposite order, it compiles and returns a wrong index that looks correct.

Which pattern fits

The problem says	Read
The array is sorted. Find a value, or where it would go.	Binary Search
The answer is a number, and "can it be done with x?" changes from no to yes exactly once.	Binary Search on the Answer
The array is sorted. Find a pair that adds up to a target.	Two Pointers
Best sum over every contiguous run of length k.	Sliding Window
Shortest contiguous run that reaches a target, and no value is negative.	Sliding Window
Sum of a range, asked many times.	Prefix Sums and Difference Arrays
Add to a range, many times, then read every value once.	Prefix Sums and Difference Arrays
For every position, the next value that is larger or smaller.	The Monotonic Stack
The largest or smallest value in every window.	The Monotonic Deque
Fewest steps across a grid, where every step costs the same.	Breadth-First Search on a Grid
Ranges that overlap. Merge them, or measure what they cover.	Merge Intervals
Connections arrive one at a time. Are these two linked yet?	Union-Find (Disjoint Set Union)
Choose items under a limit, each one at most once.	Take or Skip: The 0/1 Knapsack
Always take the smallest or largest item that is left.	PriorityQueue
Did this value occur before, and how many times?	Hash Maps
Brackets that must match, or steps that must be undone in reverse.	Stacks

12 chapters.

Binary SearchThe half-open window, the invariant that keeps the window correct, and the two bounds that std already has.
Two PointersTwo indices that start at opposite ends, and the argument that tells which index must move.
Sliding WindowOne addition and one subtraction instead of a new sum, the window that grows and shrinks, and the count that shows the total stays linear.
Prefix Sums and Difference ArraysOne subtraction instead of a loop, an extra cell for index 0, and the same method in reverse for range updates.
The Monotonic StackA stack of the indices that still wait for an answer, and the two counters that show the inner loop keeps the total linear.
Binary Search on the AnswerSearch a range of possible answers instead of an array, with a greedy pack as the predicate and a full scan to check the boundary.
Breadth-First Search on a GridThe distance field as the frontier grows, and the one line with a position that decides if a cell can enter the queue two times.
Merge IntervalsA sort by start for one pass, the nested interval that shortens a run without @max, and a sweep that counts open intervals.
The Monotonic DequeThe largest value in each window, from a deque with two ends that remove indices for two different reasons.
Union-Find (Disjoint Set Union)Groups that merge when edges arrive. A merge moves one root in a parent array, and a find follows links to the root.
Take or Skip: The 0/1 KnapsackAll subsets, the take-or-skip recursion, the table that stops repeats, the walk back to the items, and the one-row version with its loop direction.
A Contest TemplateThe one program in the section that reads real stdin, and three problems that a judge finds and a browser never shows.