Competitive programming cheat sheet (Advanced)

1. 1C++ for contestsThe language features, STL containers and habits that make C++ the default contest language, plus the table that turns a constraint into the complexity you can afford.11 concepts

   1. 1Complexity vs n tableA rule of thumb that maps the input limit n to the slowest complexity that fits a typical one or two second time limit, assuming a judge runs very roughly 10^8…
   2. 2Contest templateThe short file you start every problem from: one header that pulls in the whole standard library, a long long alias, fast input and output, and a loop over…
   3. 3Fast input and outputTwo lines that stop cin and cout synchronising with C input and output and flushing each other, plus printing a newline character instead of endl, which…
   4. 4Compiler flags and sanitizersCompile with warnings on for normal runs, and with sanitizers and the debug STL while hunting a bug, so out-of-range indexes and overflow stop the program with…
   5. 5vector, pair and tupleA vector is a resizable array with O(1) index access and amortised O(1) push_back.
   6. 6Sorting with a comparatorPassing a function to sort that returns true when the first element must come before the second, usually written as a lambda.
   7. 7set, map and multisetSorted containers built on a balanced binary search tree, with O(log n) insert, erase and search, and lower_bound to find the first element not below a value.
   8. 8priority_queueA heap that always gives the largest element in O(1) and inserts or removes in O(log n).
   9. 9STL algorithms toolkitReady-made functions in the standard library for sorting, removing duplicates, summing, finding extremes and walking through permutations.
   10. 10Integer overflow and long longAn int holds values up to about 2.1 * 10^9, and a long long up to about 9.2 * 10^18.
   11. 11unordered_map and anti-hash testsA hash map with average O(1) operations.

   11 in this chapterOpen this chapter
2. 2Maths basicsModular arithmetic, primes, divisors, fast powers and counting under a modulus: the number theory that appears from the easiest rounds upwards.8 concepts

   1. 1Modular arithmeticWorking with remainders after division by a fixed number, usually 10^9 + 7 or 998244353.
   2. 2Binary exponentiationComputing a^e in O(log e) multiplications by squaring the base and multiplying it in whenever the current bit of e is set.
   3. 3GCD and LCMThe greatest common divisor is the largest number dividing both values, found by Euclid's algorithm in O(log n).
   4. 4Sieve of EratosthenesMarks every multiple of each prime as composite, finding all primes up to n in O(n log log n).
   5. 5Trial division and divisorsDivide x by every candidate p while p * p <= x.
   6. 6Parity and invariantsAn invariant is a quantity an allowed operation never changes, such as the parity of a sum or the gcd of an array.
   7. 7Modular inverseThe number b^-1 such that b * b^-1 leaves remainder 1.
   8. 8Binomial coefficients mod pPrecompute factorials and inverse factorials up to the largest n once, then each n choose r is three multiplications.

   8 in this chapterOpen this chapter
3. Greedy and sortingMaking the locally best choice, proving it is safe, and the sorting orders that turn messy problems into one pass.7 conceptsOpens with credits
4. Binary searchSearching sorted data with the STL, and the bigger idea: binary searching over the answer whenever a yes or no check is monotone.7 conceptsOpens with credits
5. Prefix sums and two pointersAnswering range sums in O(1), applying range updates in O(1), and walking two indexes through an array to count or find subarrays in linear time.6 conceptsOpens with credits
6. GraphsStoring graphs, BFS and DFS, grids as graphs, trees, shortest paths with Dijkstra, and at higher ratings topological order and lowest common ancestors.8 conceptsOpens with credits
7. Dynamic programmingDefining a state, writing the transition and filling a table: from one-dimensional DP and knapsack to LIS, bitmask DP and DP on trees.8 conceptsOpens with credits
8. Data structuresDisjoint set union, Fenwick trees and segment trees for fast merges and range queries, and at higher ratings sparse tables, lazy propagation and ordered sets.8 conceptsOpens with credits
9. Contest strategy and upsolvingHow to spend a contest, what the verdicts mean, how to learn from problems you could not solve, and the topics that usually appear at each rating band.8 conceptsOpens with credits
10. Team play and ICPCHow the ICPC works: teams of three, one computer, five hours, penalty time and a frozen scoreboard, plus how to split roles, triage problems and prepare a team notebook.8 conceptsOpens with credits
11. 11Glossary, A to ZEvery concept in the sheet and the smaller terms it uses, in one list.135 terms

Codeforces, AtCoder, ICPC.