Sefism Competitive Programming Cheat Sheet

What it is

The Competitive programming cheat sheet is the quick-revision companion to Sefism's Competitive programming roadmap. It is written for students who treat contests as a sport: C++ for contests, the maths, greedy, search, graph, DP and data structure ideas that come up at each rating, and how to play a contest and an ICPC round well.

Every concept follows the same shape: what it is in plain words, why and when it matters, a short C++ snippet where code helps, and the mistake people usually make with it. That last line is the point of the sheet: most wrong answers in contests come from the same handful of traps, and seeing them listed next to the idea makes them easier to avoid.

Three editions, matched to your rating

The sheet comes in three editions, the same levels the roadmap uses:

• Beginner (rated under 1200 or just starting): 64 concepts. C++ and the STL for contests, reading constraints, maths basics, greedy, binary search, prefix sums, first graphs and first DP.
• Intermediate (around 1200 to 1600): 72 concepts, adding binary search on real numbers, two-dimensional prefix sums, modular inverses, topological order, LIS and anti-hash tests, plus the upsolving and stress testing habits that move a rating.
• Advanced (1600 and above, and ICPC teams): 79 concepts, from bitmask and tree DP to lazy segment trees, LCA, sparse tables, ternary search and ordered sets, with team roles, penalty maths, scoreboard reading and the team notebook.

All three share the same ten chapters, so you can move up an edition without relearning where things are.

Chapter by chapter

1. C++ for contests

The table that turns a constraint into the complexity you can afford, a contest template, fast input and output, compiler flags and sanitizers, vector, pair and tuple, sorting with a comparator, set, map and multiset, priority_queue, the STL algorithms toolkit and integer overflow with long long. Higher editions add unordered_map and anti-hash tests.

2. Maths basics

Modular arithmetic, binary exponentiation, GCD and LCM, the sieve of Eratosthenes, trial division and divisors, and parity and invariants. Intermediate and advanced add the modular inverse and binomial coefficients modulo a prime.

3. Greedy and sorting

The greedy choice, the exchange argument that proves it, interval scheduling, constructive problems, using a brute force as a checker, and sort then scan. Higher editions add coordinate compression.

4. Binary search

Binary search on a sorted array, lower_bound and upper_bound, the monotone predicate, binary search on the answer and loop invariants that prevent off-by-one bugs. Intermediate adds binary search on real numbers; advanced adds ternary search.

5. Prefix sums and two pointers

Prefix sums, difference arrays, two pointers, sliding windows and counting subarrays with a map, with two-dimensional prefix sums from intermediate upwards.

6. Graphs

Adjacency lists, BFS for shortest paths, DFS and connected components, grids as graphs, trees (parents, depths and subtree sizes) and Dijkstra with a priority queue. Topological order arrives at intermediate and LCA with binary lifting at advanced.

7. Dynamic programming

DP state and transition, memoisation against tabulation, one-dimensional DP, grid DP and 0/1 knapsack. Intermediate adds longest increasing subsequence; advanced adds bitmask DP and DP on trees.

8. Data structures

Disjoint set union, minimum spanning trees with Kruskal, Fenwick trees, segment trees and how to choose a range structure. The advanced edition adds sparse tables, lazy propagation and ordered sets with order statistics.

9. Contest strategy and upsolving

Reading the problem set, judge verdicts, upsolving, virtual contests, stress testing, AI tools and contest rules, and ratings and divisions, plus a short list of the topics that usually appear in your edition's rating band.

10. Team play and ICPC

The ICPC contest format, scoring and penalty time, the scoreboard freeze, one computer for three people, team roles, problem triage, the team notebook, and eligibility and registration.

Each chapter ends with up to three library links for going deeper, such as cppreference, cp-algorithms, the CSES Problem Set, the USACO Guide, AtCoder, KACTL and ICPC.

Rules of thumb

The sheet closes with ten rules of thumb. A few of them: read the constraints before the story, because n tells you which complexity to aim for; use long long for every sum and product unless you are sure it fits in int; test on n = 1, all equal values and the largest input before you submit; and upsolve at least one problem you could not solve after every contest. There is also a glossary of 56 short terms, from verdict names to contest jargon, and the sheet's search covers every concept by its common names.

How to use it with the roadmap

• After each stage: read the matching chapter without notes and check you could explain each pitfall line in your own words. If one surprises you, go back to that topic in the roadmap.
• Before a contest: skim the C++ chapter's complexity table and the chapter for whatever you practised that week. Ten minutes is enough.
• While upsolving: when an editorial names a technique you half know, look it up here first for the short version, then follow the chapter's links for depth.
• For ICPC: the team play chapter doubles as a checklist when you assemble your team notebook from tested code.

How it works on Sefism

Everything here is free to learn from. The public page shows every chapter title, with the first chapters open to read. Keeping the sheet uses credits, and new members get starting credits when they join. If you add the Competitive programming roadmap to your dashboard (your first roadmap is free), its cheat sheet opens with it. In the member area the sheet reads like a short book, one chapter at a time with a contents rail, and you can switch between the three editions.

Related on Sefism

• How to start competitive programming, and what to learn at each rating
• Is ICPC worth it if you will not reach the World Finals?
• Choosing a data structure is choosing what to make cheap
• The DSA cheat sheet for the same ideas aimed at coding rounds rather than contests
• Competitive Programmer's Handbook, the free book behind much of the roadmap

FAQ

Is this a replacement for practice? No. It is for revision. Rating comes from contests and upsolving; the sheet makes the revision between them faster.

Which edition should I pick? The one that matches your current rating. If you are under 1200, the beginner edition deliberately leaves out structures you will not need yet.

Are the snippets in C++ only? Yes. The roadmap and sheet use C++ because most editorials and team notebooks do.