Catalog - Codeforces

Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Catalog

General Advice

How to come up with solutions?
- How to read problem statements – Um_nik – 8 years ago Collection of problems with solutions, with an emphasis on reading the problem statement
- How to come up with the solutions: techniques – MikeMirzayanov – 11 years ago
- Characteristics of the optimal solution, a technique for finding observations in a problem – Proofy – 5 years ago
- On "is this greedy or DP", forcing and rubber bands – -is-this-fft- – 4 years ago
- How to prove your solutions in Competitive Programming – Everule – 4 years ago
- The Reason You are Bad at Codeforces — You are Not Russian Enough – Zhtluo – 3 years ago
- All You Need is Randomly Guessing — How to Improve at Codeforces – Zhtluo – 3 years ago
- How to Solve Questions [Dominater Version] – Dominater069 – 2 years ago
How to practice?
- F.A.Q. (in PM) – Um_nik – 10 years ago
- My opinion on how to practice competitive programming – Radewoosh – 5 years ago
- Self-deception: maybe why you're still grey after practicing every day – -is-this-fft- – 5 years ago
- How to practice Competitive Programming [Um_nik version] – Um_nik – 5 years ago
- [Tutorial] A way to Practice Competitive Programming : From Rating 1000 to 2400+ – E869120 – 8 years ago
- Pro Tips - get them while they are free – Um_nik – 4 years ago
- How to Effectively Practice CP + Problem Solving Guide – SuperJ6 – 3 years ago A detailed guide on how to practice with reasoning behind methodology. Also includes advice on approaching and reflecting on problems.
How to ask for help?
- How to ask for help in PM – -is-this-fft- – 6 years ago
- Asking for help FAQ – Errichto – 8 years ago
- What not to say when you are accused of cheating – ACGN – 4 years ago
How to use Codeforces [GUIDE] – SlavicG – 5 years ago
[Tutorial] The command line: how to read input from file without #ifdef and much more – -is-this-fft- – 5 years ago
After a Round FAQ – djm03178 – 4 years ago

Algorithms

General General discussions that cannot be attributed to a specific topic
- The Ultimate Topic List (with Resources, Problems and Templates) – YouKn0wWho – 5 years ago
- General ideas – adamant – 10 years ago
- A bit more of general ideas – adamant – 4 years ago
- [Tutorial] Collection of little techniques – -is-this-fft- – 5 years ago
Binary and Ternary Searches
- EDU: Binary Search – pashka – 6 years ago
- Bin search and relative error – Um_nik – 10 years ago
- Multi-dimensional ternary search – adamant – 5 years ago
- Parallel Binary Search [tutorial] – himanshujaju – 10 years ago
- An alternative and very interesting approach on binary search – Pankin – 7 years ago
- Binary Lifting, No Memory Wasted – Urbanowicz – 7 years ago Binary lifting with O(n) memory
Constructive Algorithms
- Tips on Constructive Algorithms – vmaksimovski – 6 years ago
Data Structures
- Fenwick Tree BIT
  
  [Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting – sdnr1 – 8 years ago
  
  [Tutorial] Path sum queries on a tree using a Fenwick tree – dolphingarlic – 6 years ago
  
  [Tutorial] A Bit of Math, Historic Sum, and Range Add Range Sum Binary Indexed Tree (Fenwick Tree) – FHVirus – 5 years ago
- Segment Tree
  
  EDU: Segment Tree, part 1 – pashka – 6 years ago
  
  Algorithm Gym :: Everything About Segment Trees – PrinceOfPersia – 12 years ago
  
  Efficient and easy segment trees – Al.Cash – 11 years ago
  
  crazySegmentTree: Segment Tree implementation with 5x faster queries than bottom-up tree – purplesyringa – 6 years ago
  
  Compressed segment trees and merging sets in O(N logU) – bicsi – 6 years ago
  
  A simple introduction to "Segment tree beats" – jiry_2 – 9 years ago
  
  Video: Segment Tree Beats – peltorator – 6 years ago
  
  The Time Complexity Lower Bound for Segment Tree Beats is log^2 – Tony2_CF – 10 months ago
  
  [Tutorial] Li Chao Tree Extended – rama_pang – 6 years ago
  
  [Tutorial] Li Chao Tree Extended 2 – tibinyte2006 – 2 years ago
  
  using merging segment tree to solve problems about sorted list – TLE – 10 years ago
  
  [Tutorial] XOR Segment Tree – PurpleCrayon – 4 years ago
  
  Push-Free Segment Tree – nikgaevoy – 4 years ago
  
  A Slight Generalization of Push-Free Segment Trees – WLZ – 3 years ago
- Binary Search Trees Cartesian trees, AVL-trees, etc
  
  Algorithms Thread 9: Treaps (+ Gym Contest!) – SecondThread – 6 years ago
  
  [Tutorial] Splay Tree: One Tree to Rule Them All – Zhtluo – 4 years ago
  
  "Merging treaps" -- or how to merge sorted sets in good complexity... – bicsi – 4 years ago
  
  [Tutorial] Cartesian tree and some related problems – tibinyte2006 – 4 years ago
- Connectivity Queries
  
  Disjoint Set Union DSU
  
  EDU: DSU – Aksenov239 – 6 years ago
  
  [Tutorial] Proving the inverse Ackermann complexity of Union-Find – -is-this-fft- – 5 years ago
  
  Maintaining mst with online edge insertions — no LCT needed (Maintaining mst with online edge insertions — no LCT needed) – not_amir – 2 years ago
  
  Link-Cut Trees
  
  Link-cut tree tutorial – ramchandra – 6 years ago
  
  Maintain subtree information using link/cut trees – ouuan – 7 years ago
  
  [Tutorial] Subtree lazy propagation on the link-cut tree – QCFium – 6 years ago
  
  Link Cut Tree implementation – bicsi – 7 years ago
  
  [Tutorial] Online Dynamic Connectivity – ko_osaga – 3 years ago
- Persistence
  
  AlgorithmsThread 5: Persistent Data Structures – SecondThread – 6 years ago
- Algorithm Gym :: Data structures – PrinceOfPersia – 12 years ago
- [Tutorial] Supporting Queue-like Undoing on DS – Noam527 – 6 years ago
- Video about Disjoint Sparse Table or how to answer all queries in constant time – peltorator – 6 years ago
- On Multidimensional Range Queries – Laakeri – 7 years ago Proof (assuming ETH) of the nonexistence of certain data structures
- [Tutorial] A powerful representation of integer sets – brunomont – 6 years ago
- [Tutorial] Kinetic Tournament (Used in FBHC Round 2) – ekzhang – 6 years ago
- Tutorial on Permutation Tree (析合树） – errorgorn – 6 years ago
- Introduction to New Data Structure: Wavelet Trees – rachitiitr – 9 years ago
- [Tutorial] Sparse table – AlexLuchianov – 5 years ago
- Submask range queries – adamant – 4 years ago O(2^{n/2}) for masks of length n
- A slightly alternative approach for implementation of optimal LCA – monsoon – 7 years ago
- [Tutorial] Supporting Priority-Queue-like Undoing on DS – Monogon – 4 years ago
- [Tutorial] On Range LIS Queries, Part 1 – ko_osaga – 4 years ago
- [Tutorial] On Range LIS Queries, Part 2 – ko_osaga – 4 years ago
- [Tutorial] Minimum Deque – k1r1t0 – 3 years ago
- “Log Decomposition”, a technique to insert random elements into sorted data structures – ismailfateen – 3 years ago
- [Tutorial] The sparse set data structure – Redpo – 3 years ago
Divide-and-conquer
- Dynamic connectivity problem – adamant – 12 years ago
- Divide and conquer. Dynamic connectivity offline and DP optimization. Divide and conquer by queries. – Wind_Eagle – 4 years ago
- [Tutorial] Divide and Conquer Offline Query — A Niche Way to solve Static Range Query – steveonalex – 3 years ago
Dynamic Programming DP
- [Tutorial] Non-trivial DP Tricks and Techniques – zscoder – 10 years ago
- Slope trick explained – Kuroni – 6 years ago
- An Introduction to Plug DP – 4fecta – 5 years ago DP on Broken Profile
- Dynamic Programming Optimizations – indy256 – 13 years ago
- SOS Dynamic Programming [Tutorial] – usaxena95 – 10 years ago
- Incredibly beautiful DP optimization from N^3 to N log^2 N – linkret – 10 years ago
- Theoretical grounds of lambda optimization – adamant – 5 years ago Aliens Trick
- [Tutorial] Knapsack, Subset Sum and the (max,+) Convolution – errorgorn – 5 years ago
- [Tutorial]Using Segment Trees to solve Dynamic Programming problems – AlexLuchianov – 5 years ago
- 1D1D-optimization (1D1D-optimization) – seiko.iwasawa – 5 years ago
- An interesting way to solve 739E – krismaz – 10 years ago random-shuffle sqrt dp optimization
- SMAWK algorithm as an alternative for D&C optimization – ko_osaga – 4 years ago
- Dp On Trees – AghaTizi – 8 years ago Solving certain tree dp's in O(nk) by smart amortization.
Geometry
- [Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm – Monogon – 6 years ago
- O(n) algorithm for finding largest triangle in a convex is wrong? – u0qyz1234 – 9 years ago
- Efficient 3D Convex Hull Tutorial – Monogon – 6 years ago
- Dynamic convex hull implementation – dragonslayerintraining – 7 years ago
- Geometry: Polygon algorithms – Al.Cash – 10 years ago
- Half-plane intersection (Blogewoosh #5 (with images from now)) – Radewoosh – 8 years ago
- Quaternion algebra and geometry – adamant – 10 years ago
- Easy geometry using std::complex – Hikari9 – 11 years ago
- Geometry: 2D points and lines [Tutorial] – Al.Cash – 10 years ago
- [Tutorial] Solving Interval Problems with Geometry – Monogon – 5 years ago
- AlgorithmsThread Episode 6: Convex Hull Tricks – SecondThread – 6 years ago
- Visualization tool for 2D problems (C++) – kalinov – 7 years ago
- Some rotational invariants in geometry – adamant – 5 years ago
- Easy online point location algorithm – qwerty787788 – 4 years ago
- Tiny Dynamic Convex Hull Implementation – brunomont – 4 years ago
- Pythagorean triples and Pell's equations – adamant – 4 years ago
- [Tutorial] Rotating calipers technique and its applications – asdasdqwer – 2 years ago
Games
- A blog on the Sprague-Grundy Theorem – sirknightingfail – 8 years ago
- The Intuition Behind NIM and Grundy Numbers in Combinatorial Game Theory – Shisuko – 8 years ago
- [Tutorial] Slight Generalization of Grundy Numbers – emorgan – 6 years ago Transfinite Grundy numbers
- Nimbers and Sprague-Grundy theorem – adamant – 4 years ago
Graphs
- Depth-first Search DFS
  
  [Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges – -is-this-fft- – 7 years ago
  
  My own algorithm — offline incremental strongly connected components in O(m*log(m)) – Radewoosh – 5 years ago
  
  [Tutorial] Directed DFS trees (and the Tarjan algorithm for Strongly Connected Components) – de_sousa – 2 years ago
- Shortest Paths
  
  0-1 BFS [Tutorial] – himanshujaju – 11 years ago
  
  [Tutorial] k shortest paths and Eppstein's algorithm – meooow – 5 years ago
  
  Rethink the Dijkstra algorithm -- Let's go deeper – CristianoPenaldo – 4 years ago
- Trees
  
  Algorithms Thread 8: Tree Basics (+ Gym Contest) – SecondThread – 6 years ago Finding diameters, binary lifting and flattening
  
  A list of important concepts in Tree-based Problems – dvdg6566 – 6 years ago
  
  Hybrid Tutorial #-1: Heavy-Light Decomposition – galen_colin – 6 years ago
  
  Heavy-light decompositon — it can be simple! – Vladyslav – 12 years ago
  
  Easiest HLD with subtree queries – adamant – 9 years ago
  
  [Tutorial] Sack (dsu on tree) – Arpa – 11 years ago Small-to-large merging
  
  Hybrid Tutorial #-2: Centroid Decomposition – galen_colin – 6 years ago
  
  Heavy-light decomposition implementation – Al.Cash – 11 years ago
  
  [Tutorial] Path sum queries on a tree using a Fenwick tree – dolphingarlic – 6 years ago
  
  Bridge Trees [Tutorial] – aryan12 – 5 years ago
  
  Line tree (Path max queries on a tree in O(1)) – neal – 7 years ago Description is in Kaban-5 comment
  
  [Tutorial] Binary lifting – AlexLuchianov – 5 years ago
  
  [Tutorial] Tree Isomorphism CSES – Olympia – 5 years ago
  
  [Tutorial] Diameter of a tree and its applications – TheScrasse – 5 years ago
  
  [Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates – smax – 4 years ago
  
  [Tutorial] Theoretically Faster HLD and Centroid Decomposition – errorgorn – 4 years ago
  
  [Insight] Number of Topological Orderings of a Directed Tree – Osama_Alkhodairy – 7 years ago
  
  [Idea] Using HLD to reduce memory – maomao90 – 4 years ago
  
  Optimal 2/3 halving in interactive tree problems – maomao90 – 3 years ago
  
  The Ultimate Reroot Template – pajenegod – 3 years ago For C++ and Python
  
  Shallowest Decomposition Tree – pajenegod – 3 years ago
  
  Centroids Pro Max (Niche technique with centroids) – makrav – 5 months ago
  
  Binary Lifting, No Memory Wasted – Urbanowicz – 7 years ago
- Matchings
  
  [Tutorial] Blossom Algorithm for General Matching in O(n^3) – Monogon – 5 years ago
  
  Randomized general matching with Tutte matrix – adamant – 5 years ago
  
  [Tutorial] Hungarian algorithm in Õ(mn) or O(n^3) – -is-this-fft- – 3 years ago
- Flows
  
  [Tutorial, Flows] Project Selection Problem – AlexLuchianov – 5 years ago
  
  [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm – -is-this-fft- – 4 years ago
  
  [Tutorial] Minimum cost (maximum) flow – -is-this-fft- – 4 years ago
  
  [Tutorial] More about minimum cost flows: potentials and Dinitz – -is-this-fft- – 4 years ago
  
  [Tutorial] Network simplex – brunovsky – 5 years ago
  
  Kőnig's and Hall's theorems through minimum cut in bipartite graphs – adamant – 4 years ago
  
  [Tutorial] Simulating Cost Flow – smax – 3 years ago
  
  Implementing Dinitz on bipartite graphs – adamant – 3 years ago
  
  [Tutorial] The residual graph and working with the set of all minimum cuts – -is-this-fft- – 3 years ago
  
  [Tutorial] A Compilation of Network Flow Graphs: from Beginner to Master – Zhtluo – 19 months ago
  
  Worst-Case Graphs for Maximum Flow Algorithms – lotusblume – 15 months ago
  
  maths for mincut problem:Do we really need to use Dinic to get mincut? – OtterZ – 13 months ago
- Heuristic algorithm for Hamiltonian path in directed graphs – heuristica – 5 years ago
- [Tutorial] Graph Potentials, Johnson's Algorithm, and Min Cost Max Flow – Monogon – 5 years ago
- [Tutorial] Boruvka's Algorithm – RockyB – 6 years ago
- Algorithm Gym :: Graph Algorithms – PrinceOfPersia – 12 years ago
- Story about edge coloring of graph – ko_osaga – 7 years ago Vizing's Theorem
- Merging Queries Trick – SlavicG – 5 years ago
- A Brief Inquiry into Online Connectivity – ko_osaga – 3 years ago
Greedy Algorithms
- [Tutorial] Matroid intersection in simple words – ATSTNG – 7 years ago
Hashing
- Blowing up unordered_map, and how to stop getting hacked on it – neal – 8 years ago
- [Tutorial] Rolling hash and 8 interesting problems [Editorial] – dmkozyrev – 8 years ago
- On the mathematics behind rolling hashes and anti-hash tests – dacin21 – 8 years ago
- Analysis of polynomial hashing – purplesyringa – 5 years ago
- Anti-hash test. – Zlobober – 14 years ago
- Kapun's algorithm – purplesyringa – 5 years ago
- [Tutorial] Hacking a weak hash – TheScrasse – 4 years ago
- A tool for hacking rolling hashes with fixed modulos and bases – Sugar_fan – 2 years ago
Mathematics
- Bitwise Operations
  
  Bitwise operations for beginners – Errichto – 7 years ago
  
  Bitwise operations 2 — popcount & bitsets – Errichto – 7 years ago
  
  A Beautiful Technique for Some XOR Related Problems – DrSwad – 7 years ago Gaussian elimination, a.k.a xor basis
  
  XOR basis without linear algebra – Everule – 5 years ago
- Number Theory
  
  [Tutorial] Catalan Numbers and Catalan Convolution – Dardy – 6 years ago
  
  Short modular inverse – _h_ – 11 years ago
  
  Counting Divisors of a Number in $O(N^{\frac{1}{3}})$ [tutorial] – himanshujaju – 11 years ago
  
  Counting primes in $\tilde{{\cal O}}(n^{2/3}\,\,)$ – Maksim1744 – 5 years ago
  
  Finding minimum residue of a linear function in O(log M) time – mango_lassi – 5 years ago
  
  On the Min25 sieve and extensions / SPOJ ASSIEVE – box – 5 years ago
  
  [Tutorial] Math note — Möbius inversion – Nisiyama_Suzune – 9 years ago
  
  [Tutorial] Math note — Dirichlet convolution – Nisiyama_Suzune – 9 years ago
  
  Dirichlet convolution. Part 1: Fast prefix sum computations – adamant – 3 years ago
  
  Dirichlet convolution. Part 2: Dirichlet series and prime counting – adamant – 3 years ago
  
  Essential Elementary Number Theory (Essentials of Elementary Number Theory) – Everule – 5 years ago GCD, Bezout's Theorem, Extended CRT, Mobius and other multiplicative functions, Primitive roots and Probabilistic prime tests
  
  A slightly faster algorithm for finding square root modulo an odd prime – hly1204 – 5 years ago
  
  On continued fractions. Part 3: In competitive programming – adamant – 5 years ago
  
  p-adic exponent or why there is a primitive root modulo powers of prime numbers (except 2) – adamant – 4 years ago
  
  [Tutorial] Berlakamp's Algorithm for Polynomial Factorization in a Field (1698G buffed) – errorgorn – 4 years ago
  
  [Tutorial] Euler's phi function, its properties, and how to compute it – kamilszymczak1 – 4 years ago
  
  Implicit Prime Factorisation – Everule – 4 years ago
  
  Lucas Theorem (Lucas Theorem is not an equation, it's an operation!) – Everule – 3 years ago
  
  Integer solutions to x² + y² = z – adamant – 3 years ago
  
  Division-less Euclid's algorithm – orz – 3 years ago
  
  Some useful conclutions for some naive algorithms to solve number theory problem – OtterZ – 2 years ago
  
  [Tutorial] Investigating the Harmonic Numbers – Proofy – 3 years ago
  
  Discrete square root modulo – wilcot – 3 years ago
  
  Sqrt Heuristic for Floor Sums – RP-1 – 19 months ago
- Probability Theory
  
  Sums and Expected Value — part 1 – Errichto – 8 years ago
  
  Sums and Expected Value — part 2 – Errichto – 8 years ago
  
  [Tutorial] Expected number of coin flips required to achieve a given string – gabrielwu – 5 years ago
- Сombinatorics
  
  [Tutorial] Inclusion-Exclusion Principle – Roundgod – 8 years ago
  
  Young Tableaus and the Hook Length Formula – mango_lassi – 5 years ago
  
  [Tutorial] Burnside's lemma (with example) – TwoFx – 8 years ago
  
  [Tutorial] Invariants and Monovariants – TooNewbie – 9 years ago
  
  Catalan Numbers and Generating Uniform Balanced Bracket Sequences – errorgorn – 4 years ago
  
  An intuition and simpler proof for Kirchoff's tree theorem – Everule – 4 years ago
  
  Lattice paths and Lindström–Gessel–Viennot lemma – miaowtin – 4 years ago
  
  [Tutorial] From Burnside to Polya: A Short Introduction to Group Theory ([Tutorial] From Burnside to Polya: A Short Introduction to Group Theory) – Zhtluo – 3 years ago
  
  MacMahon's master theorem – adamant – 3 years ago
- Linear Algebra
  
  A Beautiful Technique for Some XOR Related Problems – DrSwad – 7 years ago Gaussian elimination
  
  Linear Basis (Xor Basis Extended) – errorgorn – 5 years ago Generalization of Gaussian elimination to integers modulo a composite number (and beyond).
  
  2 Special cases of Gaussian [Tutorial] – MazzForces – 8 years ago Markov Chains (for Cyclic Expected Values) and the "XOR basis" technique
  
  A (Somehow) Simple (Randomized) Algorithm for Frobenius Form of a Matrix – LorentzianExpanders – 3 years ago
- Permutations
  
  Tutorial on Permutation Tree (析合树） – errorgorn – 6 years ago
  
  Permutation group basis construction (Schreier–Sims algorithm) – adamant – 4 years ago
- Polynomials, Series and Recurrences
  
  Generating Functions General theory; algorithms are under FFT
  
  [Tutorial] Generating Functions in Competitive Programming (Part 1) – zscoder – 6 years ago
  
  [Tutorial] Generating Functions in Competitive Programming (Part 2) – zscoder – 6 years ago
  
  A problem collection of ODE and differential technique – EvenImage – 7 years ago
  
  Prefix Sum Polynomial – Lain – 5 years ago
  
  Combinatorial species: An intuition behind generating functions – adamant – 4 years ago Simple way to construct generating functions and interpret operations on them.
  
  Unlabeling combinatorial species (cycle index series) – adamant – 4 years ago Finding OGFs for unlabeled species composition
  
  Moment-generating functions, inversions and q-analogs – adamant – 5 years ago
  
  OGFs, EGFs, differentiation and Taylor shifts – adamant – 5 years ago
  
  Fast polynomial composition – adamant – 5 years ago Given A(x) and B(x), compute first n coefficients of A(B(x)).
  
  Lagrange inversion theorem – adamant – 4 years ago Given x = f(y), find coefficients of g(x) such that y = g(x).
  
  Partitions and pentagonal number theorem – adamant – 4 years ago Explicit formula for (1-x)(1-x^2)(1-x^3)... and applications
  
  Arrow product: How to enumerate directed graphs – adamant – 4 years ago
  
  Shift of polynomial sampling points – adamant – 4 years ago
  
  Unexpected application of cosines – adamant – 4 years ago
  
  Solving the "simple math problem" with generating functions – adamant – 3 years ago
  
  Shift of polynomial sampling points – adamant – 4 years ago
  
  FFT and Similar Transformations Algorithms for operating on polynomials
  
  [Tutorial] FFT – -is-this-fft- – 4 years ago
  
  Tutorial on FFT/NTT — The tough made simple. ( Part 1 ) – sidhant – 11 years ago
  
  Notes on FFT / NTT, and the "ultimate" NTT with modulus > 9 * 10^18 – Spheniscine – 7 years ago
  
  On Fast Fourier Transform – adamant – 9 years ago
  
  Operations on Formal Power Series – rng_58 – 9 years ago
  
  Operations on polynomials (on cp-algorithms) – adamant – 8 years ago Fast polynomial division, evaluation, interpolation.
  
  [Tutorial] Generalized Chirp Z-Transform – box – 6 years ago
  
  Discrete Fourier Transform eigenvalues – adamant – 5 years ago
  
  A simple way to understand the transposed algo of multi-eval (A simple way to understand the transposed algo of multi-eval) – hly1204 – 5 years ago
  
  An unexpected D&C with FFT – Um_nik – 4 years ago
  
  Tutorial: A simple O(n log n) polynomial multiplication algorithm (Tutorial: A simple O(n log n) polynomial multiplication algorithm) – pajenegod – 3 years ago
  
  Introducing the imaginary cyclic convolution, speeding up convolution by a factor of 2 – pajenegod – 4 years ago
  
  Fast convolution for 64-bit integers – quasisphere – 10 years ago
  
  CDQ convolution (online FFT) generalization with Newton method – adamant – 4 years ago
  
  How to composite (some) polynomials faster? – Elegia – 3 years ago
  
  On implementing O(nlog(n)^2) algorithm of FPS composition – hly1204 – 3 years ago
  
  Montgomery/Barret reduction and NTT [Performance optimization] – alexvim – 2 years ago
  
  Bitwise Convolutions Xor-, or- and subset convolution, "set power series"
  
  Generalized FWHT: How I realized I did not understand FWHT – errorgorn – 5 years ago
  
  Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution – sidhant – 7 years ago
  
  Fast Walsh Hadamard Transforms and it's inner workings – upobir – 7 years ago
  
  Subset convolution interpretation – adamant – 5 years ago
  
  Optimal Algorithm on Polynomial Composite Set Power Series – Elegia – 5 years ago
  
  OR Convolution for Common People – ko_osaga – 4 years ago
  
  [Tutorial] GCD Convolution – szaranczuk – 4 years ago
  
  [Tutorial] Zeta, Mobius Transform to AND, OR, GCD Convolution – jinhan814 – 3 years ago
  
  Some SOS DP Insights (Some SOS DP Insights) – maxwellzen – 4 years ago An interesting interpretation of SOS DP (also known as zeta transform and under a few other names) as a multidimensional instance of prefix sums.
  
  [Tutorial] XOR Convolution without math – k1r1t0 – 3 years ago
  
  Linear Recurrences
  
  Matrix Exponentiation tutorial + training contest – Errichto – 6 years ago
  
  On linear recurrences and the math behind them – adamant – 5 years ago
  
  Recovering a linear recurrence with the extended Euclidean algorithm – adamant – 5 years ago
  
  Half-GCD algorithm – adamant – 5 years ago Compute polynomial GCD or recover minimum recurrence in O(n log^2 n)
  
  Linear Recurrence and Berlekamp-Massey Algorithm – TLE – 8 years ago
  
  [Tutorial] Berlekamp-Massey – smax – 5 years ago
  
  [Math note] On the relationship between gf and me – -is-this-fft- – 5 years ago Correspondence between generating function and matrix exponentiation for solving linear recurrences
  
  [Tutorial] Solving Linear Recurrences with various methods, Including O(N logN logK) using FFT – demoralizer – 5 years ago Computing f(k) where f(k) is a linear recurrence of N terms in O(N * log(N) * log(k))
  
  Hadamard product and binomial convolution of linear recurrences – adamant – 4 years ago
  
  Lagrange interpolation and partial fraction decomposition – adamant – 5 years ago
  
  Computing n! modulo pᵏ for small p – adamant – 3 years ago
  
  Calculating Series Sums with Binary Exponentiation – UnexpectedValue – 3 years ago
  
  Snapshot of finite calculus and using it to solve a 3000 rated problem – CelioPassos – 2 years ago
  
  The discrete derivative, falling factorials and polynomials – CelioPassos – 2 years ago
- Optimization Anything related to mathematical optimization
  
  Multi-dimensional ternary search – adamant – 5 years ago
  
  Theoretical grounds of lambda optimization – adamant – 5 years ago Aliens Trick
  
  Duality in linear programming. Part 1 — definition and construction – adamant – 4 years ago
  
  Duality in linear programming. Part 2 — in competitive programming – adamant – 4 years ago
- Abstract nonsense Abstract algebra and friends
  
  Permutation group basis construction (Schreier–Sims algorithm) – adamant – 4 years ago
  
  Associativity and general identity testing – adamant – 5 years ago
- [Tutorial] 2-SAT – arujbansal – 5 years ago
- 2-SAT Tutorial – HosseinYousefi – 12 years ago
- An interesting algebraic construction – box – 5 years ago
Non-exact and Randomized Algorithms
- [Tutorial] Simulated Annealing in Competitive Programming – PurpleCrayon – 5 years ago
- Randomized algorithms lecture, part 1 & 2 – Errichto – 7 years ago
- Blogewoosh #1 – Radewoosh – 8 years ago
- Blogewoosh #6 – Radewoosh – 8 years ago
- On the Number of Runs at the Monte-Carlo Method – rotavirus – 6 years ago
- Randomized general matching with Tutte matrix – adamant – 5 years ago
- How randomized solutions can be hacked, and how to make your solution unhackable – neal – 8 years ago
Sortings
- Lecture #3 — Exchange arguments (sorting with dp) – Errichto – 8 years ago
Square Root Techniques SQRT decomposition, Mo's algorithm, etc
- [Tutorial] Square Root Techniques – Errichto – 5 years ago
- An alternative sorting order for Mo's algorithm – gepardo – 8 years ago
- Mo's Algorithm on Trees [Tutorial] – animeshf – 11 years ago
- Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing. – gepardo – 9 years ago
- [Tutorial] Square root decomposition and applications – box – 6 years ago
- Unknown Data Structure — (Sqrt Fragmented Tree) – cjtoribio – 10 years ago
- [Tutorial] Subset Sum Square Root Optimisation – arujbansal – 5 years ago
Strings
- [Tutorial] Dynamic Suffix Arrays – brunomont – 5 years ago
- On suffix automaton (and tree) – adamant – 11 years ago
- Aho-Corasick algorithm. Construction – adamant – 12 years ago
- A short guide to suffix automata – quasisphere – 11 years ago
- Palindromic tree: behind the scenes – adamant – 12 years ago
- A bit more about palindromes – adamant – 11 years ago You're given a string, split it into the minimum number of palindromes.
- The history of some recurring problem – adamant – 8 years ago You're given a string s and queries: how many distinct substrings does sl...sr have?
- Suffix tree. Ukkonen's algorithm – adamant – 12 years ago
- [Tutorial] Expected number of coin flips required to achieve a given string – gabrielwu – 5 years ago
- [Tutorial] Dictionary of Basic Factors — O(1) String Matching – Leonardo16 – 5 years ago
- Z Algorithm – paladin8 – 15 years ago
- [Tutorial] On Variations of String Matching – brunomont – 4 years ago
- Random notes on Lyndon decomposition – ko_osaga – 4 years ago
- Border Theory:There's a fast approach to bruteforce on borders – OtterZ – 11 months ago
Sweeping Line
- How to sweep like a Sir – DanAlex – 11 years ago
- [Tutorial] Finding inclusion hierarchy among circles — An implementation of a sweep-line algorithm – Arpa – 5 years ago
Two Pointers
- EDU: Two Pointers Method – pashka – 6 years ago

Programming Languages

C++
- C++ Tricks – HosseinYousefi – 12 years ago
- Catching silly mistakes with GCC – andreyv – 12 years ago
- Don't use rand(): a guide to random number generators in C++ – neal – 8 years ago
- C++ tips and tricks – Golovanov399 – 7 years ago
- Performance tip : using std::deque as a memory cache – mouse_wireless – 8 years ago
- C++ STL: Policy based data structures – adamant – 13 years ago Like std::set, but with O(log n) methods to get k-th element and count elements that are less the given one.
- Implicit cartesian tree in GNU C++ STL. – Perlik – 13 years ago Like std::string, but can move substrings around in O(log n).
- A way to use C++ iostream for large input (gcc only) – yak_ex – 16 years ago
- Tutorial on SIMD vectorisation to speed up brute force – maomao90 – 5 years ago
- Generic data structure templates via C++ mixins – clam – 5 years ago
- Explanation to weird/strange floating point behaviour in C++ – pajenegod – 6 years ago Why you sometimes get WA with 64-bit but not 32-bit compiler
- How NOT to use macros – AlexLuchianov – 5 years ago
- How to get actual 64 bit bitsets on Codeforces [Not Recommended] [Don't do this at your job] – Chilli – 6 years ago
- Template Metaprogramming in C++ Part 1 / Infinity – Everule – 4 years ago
- [Tutorial] Quick start in solving problems on GPU + CPU – dmkozyrev – 3 years ago
- [Bugged] Dynamic Bitsets in GCC – bitset – 2 years ago
- C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures – Chilli – 8 years ago
- Different behavior between gcd and __gcd – djm03178 – 23 months ago
D
- The D programming language in competitive programming – Gassa – 8 years ago

Meta Posts that are important for competitive programming as a whole

Tools
- CF-Predictor — Know your rating changes! – WasylF – 10 years ago
- Multiple rating graph with other accounts – yak_ex – 16 years ago
- Have you already seen the history of ratings on clist? – aropan – 6 years ago Rating aggregation from different competitive programming sites.
- Codeforces Extensions – MohamedAboOkail – 6 years ago
- Gym Finder – NightRage – 5 years ago
- Userscript: table view in Catalog – -is-this-fft- – 5 years ago
- Finally, semantic search for competitive programming problems – TLE – 3 years ago
Libraries
- AtCoder Library – rng_58 – 6 years ago A professionally-developed competitive programming library.
- New online judge: Library-Checker! – yosupo – 7 years ago
- (The Ultimate) Code Library – YouKn0wWho – 5 years ago
Announcements Resources that help keeping track of upcoming contests.
- pe in 30 – Golovanov399 – 5 years ago Telegram channel with 30-minutes announcements for new problems at projecteuler.
- Resource clist.x10.mx moved to clist.by – aropan – 15 years ago Contest calendar and more

Problem and Contest Preparation

Testlib and Polygon
- Briefly about testlib.h – MikeMirzayanov – 11 years ago
- Generators with testlib.h – MikeMirzayanov – 11 years ago
- Validators with testlib.h – I_love_Hoang_Yen – 11 years ago
- Checkers with testlib.h – Zlobober – 11 years ago
- Interactors with testlib.h – PrinceOfPersia – 11 years ago
- Run-twice (aka communication) problems with Polygon and testlib.h – -is-this-fft- – 19 months ago
- 10 Reasons to Prepare Problems in Polygon – MikeMirzayanov – 12 years ago
- [Tutorial] Polygon.Codeforces Tutorial — A Guide to Problem Preparation [Part 1] – darkkcyan – 5 years ago
- Polygon Updates (Fall-Winter 2014) – Avalanche – 12 years ago
- Testlib and Polygon Updates (June, 2015) – fcspartakm – 11 years ago
- Testlib and Polygon Updates [July, 2018] – MikeMirzayanov – 8 years ago
- Polygon updates (June-October 2019) – geranazavr555 – 7 years ago
- Polygon Updates (June — August 2021) – unreal.eugene – 5 years ago
- Testlib: Opts — parsing command line options – MikeMirzayanov – 7 years ago
- Testlib: tests + CI – MikeMirzayanov – 4 years ago
Problemsetting Interviews with problemsetters, how to come up with problem ideas etc.
- How to come up with problem ideas – Lewin – 8 years ago
- On problemsetting – antontrygubO_o – 7 years ago
- On problemsetting 2 – antontrygubO_o – 7 years ago
- Way of problemsetter – Sammarize – 12 years ago
- What is it like to be a problem writer? – Nickolas – 15 years ago
- Problemsetter's Memoir – Nickolas – 12 years ago
- About Problemsetting (for AtCoder and Codeforces) – dario2994 – 6 years ago
- [Problemsetting] How to write editorials for a contest – okwedook – 4 years ago

Interviews

EPISODE 1: Interview with Um_nik – Agnimandur – 4 years ago
700 contests. ruban's interview – pani.natalia – 5 years ago
How to be red: Arpa – pani.natalia – 6 years ago
deltixlab’s interview: Deltix rounds back story – pani.natalia – 5 years ago
the Radewoosh interview — Competitive Programming Podcast – MladenP – 23 months ago
Interview with Pajaraja + great problemset – MladenP – 3 years ago
the E869120 & square1001 interview — Competitive Programming Podcast – MladenP – 22 months ago

→ History

2 months ago User KAN inserted blog post Binary Lifting, No Memory Wasted by Urbanowicz: inserted field blogEntryId 74847, inserted field catalogFolder Trees, inserted field creationTime Aug 29, 2026, 4:56:41 PM, inserted field deleted false, inserted field hidden false, inserted field position 2400.

3 months ago User jeroenodb inserted blog post Dp On Trees by AghaTizi: inserted field blogEntryId 63257, inserted field catalogFolder Dynamic Programming, inserted field creationTime Aug 14, 2026, 3:44:47 AM, inserted field deleted false, inserted field englishDescription Solving certain tree dp's in O(nk) by smart amortization. , inserted field hidden false, inserted field position 1300.

5 months ago User makrav inserted blog post Centroids Pro Max Niche technique with centroids by makrav: inserted field blogEntryId 154563, inserted field catalogFolder Trees, inserted field creationTime Jun 19, 2026, 8:53:32 PM, inserted field deleted false, inserted field englishName Centroids Pro Max, inserted field hidden false, inserted field position 2300, inserted field russianName Центроиды Про Макс.

9 months ago User Benq updated blog post Dirichlet convolution. Part 2: Dirichlet series and prime counting by adamant: updated field position ~~2500~~902.

9 months ago User Benq updated blog post Dirichlet convolution. Part 1: Fast prefix sum computations by adamant: updated field position ~~2400~~901.

9 months ago User Benq inserted blog post Dirichlet convolution. Part 2: Dirichlet series and prime counting by adamant: inserted field blogEntryId 117783, inserted field catalogFolder Number Theory, inserted field creationTime Feb 13, 2026, 2:01:45 AM, inserted field deleted false, inserted field hidden false, inserted field position 2500.

9 months ago User Benq inserted blog post Dirichlet convolution. Part 1: Fast prefix sum computations by adamant: inserted field blogEntryId 117635, inserted field catalogFolder Number Theory, inserted field creationTime Feb 13, 2026, 2:00:57 AM, inserted field deleted false, inserted field hidden false, inserted field position 2400.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 80750.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 9800.

10 months ago User Elegia updated blog post A simple introduction to "Segment tree beats" by Syloviaely: updated field position 8900.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 10900.

10 months ago User Elegia updated blog post [Tutorial] Li Chao Tree Extended 2 by tibinyte2006: updated field position 91000.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 11000.

10 months ago User Elegia updated blog post using merging segment tree to solve problems about sorted list by TLE: updated field position 10100.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 12100.

10 months ago User Elegia updated blog post [Tutorial] XOR Segment Tree by PurpleCrayon: updated field position 11200.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 13200.

10 months ago User Elegia updated blog post Push-Free Segment Tree by nikgaevoy: updated field position 12300.

10 months ago User Elegia updated blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: updated field position 14300.

10 months ago User Elegia updated blog post A Slight Generalization of Push-Free Segment Trees by WLZ: updated field position 13400.

10 months ago User Elegia inserted blog post The Time Complexity Lower Bound for Segment Tree Beats is log^2 by Tony2_CF: inserted field blogEntryId 149516, inserted field catalogFolder Segment Tree, inserted field creationTime Dec 28, 2025, 12:20:19 AM, inserted field deleted false, inserted field hidden false, inserted field position 1400.

10 months ago User LeoPro inserted blog post Border Theory:There's a fast approach to bruteforce on borders by OtterZ: inserted field blogEntryId 149314, inserted field catalogFolder Strings, inserted field creationTime Dec 23, 2025, 4:08:09 PM, inserted field deleted false, inserted field hidden false, inserted field position 1400.

10 months ago User LeoPro updated blog post Maths for mincut problem: do we really need Dinic to get mincut? maths for mincut problem:Do we really need to use Dinic to get mincut? by OtterZ: updated field englishName ~~Maths for mincut problem: do we really need Dinic to get mincut?~~.

10 months ago User LeoPro inserted blog post Maths for mincut problem: do we really need Dinic to get mincut? maths for mincut problem:Do we really need to use Dinic to get mincut? by OtterZ: inserted field blogEntryId 146966, inserted field catalogFolder Flows, inserted field creationTime Dec 22, 2025, 12:35:02 PM, inserted field deleted false, inserted field englishName Maths for mincut problem: do we really need Dinic to get mincut?, inserted field hidden false, inserted field position 1500.

12 months ago User MikeMirzayanov inserted blog post Worst-Case Graphs for Maximum Flow Algorithms by lotusblume: inserted field blogEntryId 145343, inserted field catalogFolder Flows, inserted field creationTime Nov 12, 2025, 7:43:17 AM, inserted field deleted false, inserted field hidden false, inserted field position 1400.

12 months ago User ko_osaga inserted blog post Maintaining mst with online edge insertions — no LCT needed Maintaining mst with online edge insertions — no LCT needed by not_amir: inserted field blogEntryId 130107, inserted field catalogFolder Disjoint Set Union, inserted field creationTime Nov 9, 2025, 1:57:16 AM, inserted field deleted false, inserted field englishName Maintaining mst with online edge insertions — no LCT needed, inserted field hidden false, inserted field position 300.

14 months ago User volcano_2025 updated blog post The Ultimate Topic List (with Resources, Problems and Templates) by YouKn0wWho: updated field position 5200.

14 months ago User volcano_2025 updated blog post General ideas by adamant: updated field position 2500.

14 months ago User volcano_2025 updated blog post The Ultimate Topic List (with Resources, Problems and Templates) by YouKn0wWho: updated field position 2500.

14 months ago User volcano_2025 updated blog post General ideas by adamant: updated field position 5200.

18 months ago User cadmiumky inserted blog post Sqrt Heuristic for Floor Sums by RP-1: inserted field blogEntryId 141889, inserted field catalogFolder Number Theory, inserted field creationTime May 1, 2025, 4:17:58 PM, inserted field deleted false, inserted field hidden false, inserted field position 2300.

19 months ago User -is-this-fft- updated blog post Run-twice (aka communication) problems with Polygon and testlib.h by -is-this-fft-: updated field position 55025.

19 months ago User -is-this-fft- updated blog post Run-twice (aka communication) problems with Polygon and testlib.h by -is-this-fft-: updated field position ~~140~~550.

19 months ago User -is-this-fft- inserted blog post Run-twice (aka communication) problems with Polygon and testlib.h by -is-this-fft-: inserted field blogEntryId 142052, inserted field catalogFolder Testlib and Polygon, inserted field creationTime Apr 19, 2025, 10:49:39 AM, inserted field deleted false, inserted field hidden false, inserted field position 1400.

19 months ago User Misuki updated blog post [Tutorial] Floors, ceilings and inequalities for beginners (with some programming tips) by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] An elementary way of solving recurrences by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] GCC Optimization Pragmas by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [C++] Avoiding temporaries — generalizing i++ using std::exchange by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] On lambdas, C++ and otherwise: the what, the why, and the how by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] Writing C++ like Python: tricks Python doesn't want you to know by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post Insights from testing and preparing contests, and why problemsetting trends need to change by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] A comprehensive guide to permutations for beginners by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post Intuition and application of Martingales Probability 101, the intuition behind martingales and solving problems with them by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] Generalized Möbius Inversion on Posets by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] Greedoids: a formal way to look at families of greedily-solvable problems by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post The Akra-Bazzi theorem — a generalization of the master theorem for recurrences by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post Traversing the complement graph in linear/near-linear time in multiple ways by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] Binary search and other "halving" methods by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] The Floyd-Warshall algorithm and its generalizations by nor: updated field hidden ~~fals~~true.

19 months ago User Misuki updated blog post [Tutorial] How to learn better, and what most people don't get about learning by nor: updated field hidden ~~fals~~true.

19 months ago User Zhtluo inserted blog post [Tutorial] A Compilation of Network Flow Graphs: from Beginner to Master by Zhtluo: inserted field blogEntryId 141680, inserted field catalogFolder Flows, inserted field creationTime Apr 10, 2025, 7:41:57 AM, inserted field deleted false, inserted field hidden false, inserted field position 1300.

21 month(s) ago User tch1cherin inserted blog post Discrete square root modulo by wilcot: inserted field blogEntryId 124745, inserted field catalogFolder Number Theory, inserted field creationTime Feb 4, 2025, 8:18:53 PM, inserted field deleted false, inserted field hidden false, inserted field position 2200.

22 months ago User NemanjaSo2005 updated blog post the E869120 & square1001 interview — Competitive Programming Podcast by MladenP: updated field hidden ~~fals~~true.

22 months ago User NemanjaSo2005 inserted blog post the E869120 & square1001 interview — Competitive Programming Podcast by MladenP: inserted field blogEntryId 138454, inserted field catalogFolder Interviews, inserted field creationTime Jan 17, 2025, 2:29:04 AM, inserted field deleted false, inserted field hidden false, inserted field position 700.

22 months ago User NemanjaSo2005 inserted blog post Interview with Pajaraja + great problemset by MladenP: inserted field blogEntryId 129156, inserted field catalogFolder Interviews, inserted field creationTime Jan 3, 2025, 9:13:22 PM, inserted field deleted false, inserted field hidden false, inserted field position 600.

The only programming contests Web 2.0 platform

Server time: Nov/06/2026 21:24:55 (g2).

Mobile version, switch to desktop version.

Supported by

English name:
	Or leave empty
Russian name:
	Or leave empty
English description:
	Or leave empty
Russian description:
	Or leave empty
Parent:
	Parent Folder
Position:
	Position
Hidden:

Blog Post:

English name:
	Or leave empty
Russian name:
	Or leave empty
English description:
	Or leave empty
Russian description:
	Or leave empty
Parent:
	Parent Folder
Position:
	Position
Hidden: