Part 6: Codeforces patterns

This part covers the techniques that short Codeforces problems keep using: fast input and output, counting steps, two pointers, prefix sums, binary search, number theory, sliding windows, and a first set of problems worked through in full. Work through the lessons in order, because each one uses the ideas of the lessons before it.

1. Fast input and output template: Read all input at once, split it into tokens, and write the answer in one call. ~15 min
2. Counting steps and choosing a Python interpreter: Count loop iterations as formulas, estimate whether they fit a time limit, and learn what PyPy is. ~15 min
3. Two pointers on sorted data: Move two indices through a sorted list, and show that the scan takes at most n - 1 steps. ~20 min
4. Prefix sums and difference arrays: Answer range sums in constant time and apply many range updates in one pass. ~20 min
5. Binary search and the bisect module: Find positions with bisect, and search for the smallest or largest answer that passes a test. ~20 min
6. Number theory: gcd, divisors, sieve, and modular powers: Compute gcd and lcm, list divisors, sieve primes, and use pow with a modulus. ~25 min
7. Sliding window over a list: Keep a moving window of a list, and learn when the shrink rule is valid. ~20 min
8. Ten first problems, worked through: Solve ten short problems in the 800 to 1200 range, with pitfalls and tested solutions. ~45 min