Competitive Programming

A contest problem reads its input from stdin. Nothing on this site has one, because a snippet here runs under WASI in a browser tab, so each chapter embeds its input as text and parses it the way it would parse a file. The algorithm is unaffected. What the browser buys in exchange is that every program prints the steps it took, and the trace quoted in the chapter is the trace CI diffed against the compiler the footer names.

1. Binary search is a shrinking window, not a clever midpoint. Every index that could be the answer stays inside items[lo..hi], and the loop ends when nothing is left to look at.
2. The classic off-by-one does not return a wrong index. It stops returning, because a window of one has a middle equal to its own start.
3. (lo + hi) / 2 adds two indices that are each valid and whose sum need not be. lo + (hi - lo) / 2 costs nothing and cannot overflow.
4. Two bounds answer more than one search does. Where a value starts and where it ends is a count, and getting it needs no scan.
5. Two pointers converging on sorted data never get a choice about the next move. One index retires per step, so a walk that reads like a search costs one pass.
6. A sliding window adds the value entering and subtracts the value leaving. Every index enters once and leaves once, so a loop inside a loop is still linear, and the shrink rule stops holding the moment a value can be negative.
7. std.sort.lowerBound passes the key first and the element second. A comparator written the other way round compiles and returns a plausible wrong index.

7 chapters.

• Binary SearchThe half-open window, the invariant that keeps it correct, and the two bounds std already ships.
• Two PointersTwo indices starting at opposite ends, and the argument that says which one of them has to move.
• Sliding WindowOne addition and one subtraction instead of a fresh sum, the window that grows and shrinks, and the count that shows the inner loop is free.
• Prefix Sums and Difference ArraysOne subtraction instead of a loop, the spare cell that removes the special case at index 0, and the same trick run backwards for range updates.
• The Monotonic StackA stack of the indices still waiting for an answer, and the two counters that show the inner loop is free.
• Binary Search on the AnswerSearching a range of possible answers instead of an array, with a greedy pack as the predicate and a brute-force scan checking the boundary.
• Breadth-First Search on a GridThe distance field printed as the frontier expands, and the one line whose position decides whether a cell can enter the queue twice.