Catalog - Codeforces

→ History

2 weeks ago User valeriu updated blog post [Tutorial] Li Chao Tree Extended 2 by tibinyte: updated field position 10900.

2 weeks ago User valeriu updated blog post using merging segment tree to solve problems about sorted list by TLE: updated field position 91000.

2 weeks ago User valeriu updated blog post [Tutorial] Li Chao Tree Extended 2 by tibinyte: updated field position 11000.

2 weeks ago User valeriu updated blog post [Tutorial] XOR Segment Tree by PurpleCrayon: updated field position 10100.

2 weeks ago User valeriu updated blog post Li Chao Tree Extended 2 [Tutorial] Li Chao Tree Extended 2 by tibinyte: updated field englishName ~~Li Chao Tree Extended 2~~.

2 weeks ago User valeriu updated blog post Li Chao Tree Extended 2 [Tutorial] Li Chao Tree Extended 2 by tibinyte: updated field position 12100.

2 weeks ago User valeriu updated blog post Push-Free Segment Tree by nikgaevoy: updated field position 11200.

2 weeks ago User valeriu updated blog post Li Chao Tree Extended 2 [Tutorial] Li Chao Tree Extended 2 by tibinyte: updated field position 13200.

2 weeks ago User valeriu updated blog post A Slight Generalization of Push-Free Segment Trees by WLZ: updated field position 12300.

2 weeks ago User valeriu inserted blog post Li Chao Tree Extended 2 [Tutorial] Li Chao Tree Extended 2 by tibinyte: inserted field blogEntryId 130766, inserted field catalogFolder Segment Tree, inserted field creationTime Jul 12, 2024, 6:58:04 PM, inserted field deleted false, inserted field englishName Li Chao Tree Extended 2, inserted field hidden false, inserted field position 1300.

2 weeks ago User Tom66 inserted blog post Montgomery/Barret reduction and NTT [Performance optimization] by alexvim: inserted field blogEntryId 129600, inserted field catalogFolder FFT and Similar Transformations, inserted field creationTime Jul 12, 2024, 12:44:47 PM, inserted field deleted false, inserted field hidden false, inserted field position 2000.

2 weeks ago User Tom66 inserted blog post A tool for hacking rolling hashes with fixed modulos and bases by Sugar_fan: inserted field blogEntryId 129538, inserted field catalogFolder Hashing, inserted field creationTime Jul 10, 2024, 3:26:39 PM, inserted field deleted false, inserted field hidden false, inserted field position 800.

2 weeks ago User Tom66 updated folder Testing and Polygon: updated field englishName Test~~ing~~lib and Polygon.

2 weeks ago User Tom66 updated blog post [Tutorial] Boruvka's Algorithm by RockyB: updated field position 4300.

2 weeks ago User Tom66 updated blog post Algorithm Gym :: Graph Algorithms by PrinceOfPersia: updated field position 3400.

2 weeks ago User Tom66 updated blog post Codeforces Updates (April-May, 2015) by kuviman: updated field hidden ~~fals~~true.

2 weeks ago User Tom66 inserted blog post Codeforces Updates (April-May, 2015) by kuviman: inserted field blogEntryId 18327, inserted field catalogFolder Testlib and Polygon, inserted field creationTime Jul 10, 2024, 3:13:54 PM, inserted field deleted false, inserted field hidden false, inserted field position 650.

2 months ago User -is-this-fft- inserted blog post C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures by Chilli: inserted field blogEntryId 60737, inserted field catalogFolder C++, inserted field creationTime May 23, 2024, 2:30:54 AM, inserted field deleted false, inserted field hidden false, inserted field position 2300.

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

2 months ago User -is-this-fft- inserted blog post [Bugged] Dynamic Bitsets in GCC by bitset: inserted field blogEntryId 129454, inserted field catalogFolder C++, inserted field creationTime May 14, 2024, 6:16:29 PM, inserted field deleted false, inserted field hidden false, inserted field position 2200.

3 months ago User -is-this-fft- inserted blog post [Tutorial] The sparse set data structure by Redpo: inserted field blogEntryId 127472, inserted field catalogFolder Data Structures, inserted field creationTime Apr 26, 2024, 2:41:27 AM, inserted field deleted false, inserted field hidden false, inserted field position 1800.

3 months ago User -is-this-fft- inserted blog post [Tutorial] Hungarian algorithm in Õ(mn) or O(n^3) by -is-this-fft-: inserted field blogEntryId 128703, inserted field catalogFolder Matchings, inserted field creationTime Apr 26, 2024, 2:40:04 AM, inserted field deleted false, inserted field hidden false, inserted field position 400.

3 months ago User -is-this-fft- inserted blog post Division-less Euclid's algorithm by orz: inserted field blogEntryId 124218, inserted field catalogFolder Number Theory, inserted field creationTime Apr 26, 2024, 2:39:44 AM, inserted field deleted false, inserted field hidden false, inserted field position 1900.

3 months ago User -is-this-fft- inserted blog post “Log Decomposition”, a technique to insert random elements into sorted data structures by ismail-but-noob: inserted field blogEntryId 124766, inserted field catalogFolder Data Structures, inserted field creationTime Apr 26, 2024, 2:36:19 AM, inserted field deleted false, inserted field hidden false, inserted field position 1700.

3 months ago User -is-this-fft- inserted blog post On implementing O(nlog(n)^2) algorithm of FPS composition by hly1204: inserted field blogEntryId 127674, inserted field catalogFolder FFT and Similar Transformations, inserted field creationTime Apr 26, 2024, 2:34:41 AM, inserted field deleted false, inserted field hidden false, inserted field position 1900.

3 months ago User -is-this-fft- inserted blog post [Tutorial] An elementary way of solving recurrences by nor: inserted field blogEntryId 124438, inserted field catalogFolder Linear Recurrences, inserted field creationTime Apr 26, 2024, 2:33:30 AM, inserted field deleted false, inserted field hidden false, inserted field position 1000.

3 months ago User -is-this-fft- updated blog post [Tutorial] Online Dynamic Connectivity by ko_osaga: updated field catalogFolder ~~Disjoint Set Union~~Link-Cut Trees, updated field position 3700.

3 months ago User -is-this-fft- updated blog post Link Cut Tree implementation by bicsi: updated field catalogFolder BLin~~ary Search~~k-Cut Trees.

3 months ago User -is-this-fft- updated blog post [Tutorial] Subtree lazy propagation on the link-cut tree by QCFium: updated field catalogFolder BLin~~ary Search~~k-Cut Trees.

3 months ago User -is-this-fft- updated blog post Maintain subtree information using link/cut trees by ouuan: updated field catalogFolder BLin~~ary Search~~k-Cut Trees.

3 months ago User -is-this-fft- updated blog post Link-cut tree tutorial by ramchandra: updated field catalogFolder BLin~~ary Search~~k-Cut Trees.

3 months ago User -is-this-fft- inserted folder Link-Cut Trees: inserted field creationTime Apr 26, 2024, 2:31:01 AM, inserted field deleted false, inserted field englishName Link-Cut Trees, inserted field hidden false, inserted field parentCatalogFolder Connectivity Queries, inserted field position 500.

3 months ago User -is-this-fft- updated folder Connectivity Queries: updated field position 6500.

3 months ago User -is-this-fft- updated folder Persistence: updated field position 5600.

3 months ago User -is-this-fft- updated folder Disjoint Set Union: updated field parentCatalogFolder ~~Data Structur~~Connectivity Queries.

3 months ago User -is-this-fft- updated folder Persistence: updated field position 4500.

3 months ago User -is-this-fft- updated folder Disjoint Set Union: updated field position 5400.

3 months ago User -is-this-fft- updated folder Persistence: updated field position 5400.

3 months ago User -is-this-fft- updated folder Disjoint Set Union: updated field position 4500.

3 months ago User -is-this-fft- inserted folder Connectivity Queries: inserted field creationTime Apr 26, 2024, 2:29:55 AM, inserted field deleted false, inserted field englishName Connectivity Queries, inserted field hidden false, inserted field parentCatalogFolder Data Structures, inserted field position 600.

3 months ago User -is-this-fft- inserted blog post [Tutorial] Online Dynamic Connectivity by ko_osaga: inserted field blogEntryId 128556, inserted field catalogFolder Disjoint Set Union, inserted field creationTime Apr 26, 2024, 2:28:54 AM, inserted field deleted false, inserted field hidden false, inserted field position 300.

3 months ago User -is-this-fft- inserted blog post A Slight Generalization of Push-Free Segment Trees by WLZ: inserted field blogEntryId 125275, inserted field catalogFolder Segment Tree, inserted field creationTime Apr 26, 2024, 2:28:21 AM, inserted field deleted false, inserted field hidden false, inserted field position 1200.

3 months ago User -is-this-fft- inserted blog post [Tutorial] XOR Convolution without math by k1r1t0: inserted field blogEntryId 127823, inserted field catalogFolder Bitwise Convolutions, inserted field creationTime Apr 26, 2024, 2:14:52 AM, inserted field deleted false, inserted field hidden false, inserted field position 1900.

3 months ago User -is-this-fft- inserted blog post A (Somehow) Simple (Randomized) Algorithm for Frobenius Form of a Matrix by MyBotDear: inserted field blogEntryId 124815, inserted field catalogFolder Linear Algebra, inserted field creationTime Apr 26, 2024, 2:14:08 AM, inserted field deleted false, inserted field hidden false, inserted field position 400.

3 months ago User -is-this-fft- inserted blog post How to composite (some) polynomials faster? by Elegia: inserted field blogEntryId 126124, inserted field catalogFolder FFT and Similar Transformations, inserted field creationTime Apr 26, 2024, 2:13:39 AM, inserted field deleted false, inserted field hidden false, inserted field position 1800.

3 months ago User -is-this-fft- inserted blog post [Tutorial] The residual graph and working with the set of all minimum cuts by -is-this-fft-: inserted field blogEntryId 128552, inserted field catalogFolder Flows, inserted field creationTime Apr 16, 2024, 5:30:51 PM, inserted field deleted false, inserted field hidden false, inserted field position 1200.

3 months ago User -is-this-fft- inserted blog post Pro Tips - get them while they are free by Um_nik: inserted field blogEntryId 113785, inserted field catalogFolder How to practice?, inserted field creationTime Apr 16, 2024, 4:04:56 PM, inserted field deleted false, inserted field hidden false, inserted field position 900.

5 months ago User Zhtluo inserted blog post All You Need is Randomly Guessing — How to Improve at Codeforces by Zhtluo: inserted field blogEntryId 126875, inserted field catalogFolder How to come up with solutions?, inserted field creationTime Mar 11, 2024, 12:26:54 AM, inserted field deleted false, inserted field hidden false, inserted field position 1100.

5 months ago User Zhtluo inserted blog post The Reason You are Bad at Codeforces — You are Not Russian Enough by Zhtluo: inserted field blogEntryId 126310, inserted field catalogFolder How to come up with solutions?, inserted field creationTime Mar 6, 2024, 2:50:20 AM, inserted field deleted false, inserted field hidden false, inserted field position 1000.

6 months ago User pajenegod inserted blog post Shallowest Decomposition Tree by pajenegod: inserted field blogEntryId 125018, inserted field catalogFolder Trees, inserted field creationTime Jan 23, 2024, 5:09:43 PM, inserted field deleted false, inserted field hidden false, inserted field position 2200.

7 months ago User pajenegod updated blog post The Ultimate Reroot Template by pajenegod: updated field englishDescription For C++ and Python.

7 months ago User pajenegod updated blog post The Ultimate Reroot Template The Ultimate Reroot Template by pajenegod: updated field englishDescription ~~Gives a general and simple to use template for reroot DP on trees, implmented both in Python and C++.~~, updated field englishName ~~The Ultimate Reroot Template~~.

7 months ago User pajenegod inserted blog post The Ultimate Reroot Template The Ultimate Reroot Template by pajenegod: inserted field blogEntryId 124286, inserted field catalogFolder Trees, inserted field creationTime Jan 4, 2024, 7:09:57 PM, inserted field deleted false, inserted field englishDescription Gives a general and simple to use template for reroot DP on trees, implmented both in Python and C++., inserted field englishName The Ultimate Reroot Template, inserted field hidden false, inserted field position 2100.

7 months ago User Kaban-5 updated blog post Some SOS DP Insights Some SOS DP Insights by maxwellzen: updated field englishDescription An interesting interpretation of SOS DP (also known as "zeta transform" and a few other names) a multidimensional instance of prefix sums., updated field russianDescription Интересная интерпретация задачи суммирования по подмножествам (также известной как <<zeta-преобразование>> и под ещё несколькими именами) в терминах многомерных префиксных сумм..

7 months ago User Kaban-5 inserted blog post Some SOS DP Insights Some SOS DP Insights by maxwellzen: inserted field blogEntryId 105247, inserted field catalogFolder Bitwise Convolutions, inserted field creationTime Jan 2, 2024, 11:35:40 PM, inserted field deleted false, inserted field englishDescription An interesting interpretation of SOS DP (also known as "zeta transform" and a few other names) a multidimensional instance of prefix sums., inserted field englishName Some SOS DP Insights, inserted field hidden false, inserted field position 1800, inserted field russianDescription Интересная интерпретация задачи суммирования по подмножествам (также известной как <<zeta-преобразование>> и под ещё несколькими именами) в терминах многомерных префиксных сумм., inserted field russianName Some SOS DP Insights.

7 months ago User average_frog_enjoyer inserted blog post [Tutorial] How to learn better, and what most people don't get about learning by nor: inserted field blogEntryId 111644, inserted field catalogFolder How to practice?, inserted field creationTime Dec 25, 2023, 1:26:35 PM, inserted field deleted false, inserted field hidden false, inserted field position 800.

7 months ago User -is-this-fft- inserted blog post The Akra-Bazzi theorem — a generalization of the master theorem for recurrences by nor: inserted field blogEntryId 123452, inserted field catalogFolder Divide-and-conquer, inserted field creationTime Dec 19, 2023, 8:48:24 AM, inserted field deleted false, inserted field hidden false, inserted field position 400.

Catalog

General Advice

How to come up with solutions?
- How to read problem statements – Um_nik – 6 years ago Collection of problems with solutions, with an emphasis on reading the problem statement
- How to come up with the solutions: techniques – MikeMirzayanov – 9 years ago
- Characteristics of the optimal solution, a technique for finding observations in a problem – Proofy – 3 years ago
- On "is this greedy or DP", forcing and rubber bands – -is-this-fft- – 23 months ago
- How to prove your solutions in Competitive Programming – Everule – 18 months ago
- The Reason You are Bad at Codeforces — You are Not Russian Enough – Zhtluo – 5 months ago
- All You Need is Randomly Guessing — How to Improve at Codeforces – Zhtluo – 5 months ago
How to practice?
- F.A.Q. (in PM) – Um_nik – 8 years ago
- My opinion on how to practice competitive programming – Radewoosh – 3 years ago
- Self-deception: maybe why you're still grey after practicing every day – -is-this-fft- – 3 years ago
- How to practice Competitive Programming [Um_nik version] – Um_nik – 3 years ago
- [Tutorial] A way to Practice Competitive Programming : From Rating 1000 to 2400+ – E869120 – 5 years ago
- [Tutorial] How to learn better, and what most people don't get about learning – nor – 18 months ago
- Pro Tips - get them while they are free – Um_nik – 17 months ago
How to ask for help?
- How to ask for help in PM – -is-this-fft- – 4 years ago
- Asking for help FAQ – Errichto – 5 years ago
- What not to say when you are accused of cheating – ACGN – 15 months ago
How to use Codeforces [GUIDE] – SlavicG – 2 years ago
[Tutorial] The command line: how to read input from file without #ifdef and much more – -is-this-fft- – 2 years ago
After a Round FAQ – djm03178 – 2 years ago

Algorithms

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

Programming Languages

C++
- C++ Tricks – HosseinYousefi – 10 years ago
- Catching silly mistakes with GCC – andreyv – 10 years ago
- Don't use rand(): a guide to random number generators in C++ – neal – 6 years ago
- [Tutorial] GCC Optimization Pragmas – nor – 3 years ago
- C++ tips and tricks – Golovanov399 – 4 years ago
- Performance tip : using std::deque as a memory cache – mouse_wireless – 6 years ago
- C++ STL: Policy based data structures – adamant – 10 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 – 11 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 – 14 years ago
- Tutorial on SIMD vectorisation to speed up brute force – maomao90 – 3 years ago
- Generic data structure templates via C++ mixins – clam – 3 years ago
- Explanation to weird/strange floating point behaviour in C++ – pajenegod – 4 years ago Why you sometimes get WA with 64-bit but not 32-bit compiler
- How NOT to use macros – AlexLuchianov – 2 years ago
- How to get actual 64 bit bitsets on Codeforces [Not Recommended] [Don't do this at your job] – Chilli – 4 years ago
- [Tutorial] Writing C++ like Python: tricks Python doesn't want you to know – nor – 19 months ago
- Template Metaprogramming in C++ Part 1 / Infinity – Everule – 17 months ago
- [Tutorial] Quick start in solving problems on GPU + CPU – dmkz – 14 months ago
- [Tutorial] On lambdas, C++ and otherwise: the what, the why, and the how – nor – 8 months ago
- [C++] Avoiding temporaries — generalizing i++ using std::exchange – nor – 8 months ago
- [Bugged] Dynamic Bitsets in GCC – bitset – 2 months ago
- C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures – Chilli – 6 years ago
D
- The D programming language in competitive programming – Gassa – 6 years ago

Meta Posts that are important for competitive programming as a whole

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

Problem and Contest Preparation

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

Interviews

EPISODE 1: Interview with Um_nik – Agnimandur – 17 months ago
700 contests. ruban's interview – pani.natalia – 3 years ago
How to be red: Arpa – pani.natalia – 3 years ago
deltixlab’s interview: Deltix rounds back story – pani.natalia – 3 years ago

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: