praveenkulkarni1996/average-competitive-programming

The best competitive programming tutorials on codeforces for those who are not awesome yet.

Average Competitive Programming

Please also take a look at the Problems.md file, which has grouped some moderately difficult problems by their problem categories.

• My Implementations
• Implementations
• Blogs
• Joke Threads

My Implementations

• Fenwick Tree
• Gaussian XOR-field
• Disjoint Set Union
• Lazy Segment Tree
• Iterative Segment Tree
• Fast Fourier Transform
• Convex Hull of Linear Functions
• Bipartite Matching
• Two Sat and Tarjan SCC
• Tree diameter
• Modular Arithmetic

tourist's Implementations

• Fenwick Tree with template usage.
• Sparse Table
• Topological Sort
• Mincost Maxflow: Uses non-standard GCC extensions.
• Hadamard, and matrices: I don't understand this, refer to editorial.
• NTT: Number Theoretic Transform or this.
• Prime Sieves
• (tourist) Primality Algorithms.
• (tourist) Shortest Path Algorithms: includes Dijkstra and Dominators
• (tourist) Flow Algorithms: includes Gomory Hu
• (tourist) Graph Algorithms: includes DFS forests, Heavy-Light Decomposition and Fenwick Trees (bonus!) or this, or this.
• (tourist) Bipartite Matching.
• (tourist) Euler Paths
• (tourist) Splay Trees
• (tourist) Hungarian Algorithm
• (tourist) Segment Trees or this or this.
• (tourist) Debugging and FFT
• (tourist) Number Theory Primitives
• (tourist) Manachar's Algorithm
• (tourist) Graph Cycles
• (tourist) Treaps or this or this. These implementations are probably very similar.
• (tourist) Ukkonnen
• (tourist) Suffix Array with LCP
• (tourist) Mincost Maxflow
• (tourist) KMP Algorithm
• (tourist) Z-function
• (tourist) Points and Polar comparison
• (tourist) Hash Functions
• (tourist) Radix Sort

Other Implementations

Neal:

• Bipartite Check
• Bipartite Union Find
• Cartesian Tree
• Tree algorithms – LCA, RMQ, Heavy-Light decompositions.
• Monotonic Hull DP
• Binary Trie and array trie.

Others:

• (rama_pang) Network Simplex
• (mnbvmar) Geometry Suite
• (mnbvmar) Geometry Suite and Dinic
• (Benq) Mincost Maxflow
• (O...O) Number Theory Suite
• (tourist) Sieves for Euler Phi
• (rajat1603) Convex Hull Trick
• (darooha) Link Cut Trees (from the inventor himself).
• (neal) RMQ and LCA and more!.
• (neal) Prime factorization algorithms.
• (neal) Dinic, and dinic matching with bonus hashing.

Blogs

This is a joke/pun/homage to the awesome series. I will add the awesome blogs that I usually find on codeforces there.

• Efficient and Easy Segment Trees
  Contains brilliant analysis and implementation of segment trees.

• Geometry: 2D points and lines
  Introduction to geometry algorithms + high quality code. Part 1 of a 2 part series.

• Geometry: Polygon Algorithms
  Implementations of all polygon algorithms.

• Heavy Light Decomposition Algorithm
  Clean and Efficient Implmenetation of HLD.

• A little bit of classics: dynamic programming over subsets and paths in graphs
  Exactly what the title says.

• Z Algorithm
  For string algorithms specialists.

• Partially Ordered Sets
  Mathematical definitions and Dilworth's theorems.

• Nim: Algorithmic Game
  I think the wiki is better, and contains more variations.

• Mo's Algorithm on Trees
  Magic on paper. For subtree/path/range queries on trees.

• Tutorial on FFT/NTT (part 1) and part 2
  Unusually high effort post on codeforces.

• Dynamic Programming Optimizations
  Short and dense content. Knuth, DnC and Convex Hulls.

• Incredibly beautiful DP optimization ...
  Describes the Knuth DP optimization on a problem. (but applies a second one on top of that).

• Non-trivial DP Tricks and Techniques
  Exactly what the title says.

• Staircase Nim
  A clever variant of the nim game.

• Linear Sieve
  Sieve of Erathosthenes concepts.

• Invariants and Monovariants
  Discussion includes IMO problems.

• Random number generators
  Why we shouldn't use rand().

• Burnside's Lemma
  Burnside's Lemma explained with one problem. No proof.

• 0-1 BFS
  Shortest path algorithm for weighted graphs where weights are either 0 or 1.

• Tof on Ternary Search
  Hack to improve convexity for ternary search (by spitting on it).

• A multiple binary search optimization
  A randomized algorithm with very good average case runtime but very bad worst case runtime, which can be applied while trying to optimize multiple binary searches.

• Segment Tree Beats
  Super-clever tricks for segment trees. Relevant code

• DSU on Trees
  DSU on trees, with interesting discussion of alternate methods.

• Bitmask DP: Sum over subsets
  Treatment of bitmask dp optimization from O(3^n) to O(n 2^n).

• Rotating Calipers
  Look at SuperDewd's comment.

• Crazy DP optimization. Blogewoosh #4
  Radewoosh's fourth blog on a dp-recursion memory optimization that is absolutely crazy.

• Linear Recurrence and Berlekamp-Massey Algorithm
  Exactly what the title says.

• Convex Hull Trick — Geometry being useful
  Yet another convex hull trick blog. But this has the best pictures.

• Gaussian Elimination
  For XOR Spaces.

• Persistence
  Very good explanation of functional persistence.

• General Ideas
  Excellent collection of non-trivial ideas by adamant.

• Nearest Neighbour Search
  Locality-Sensitive Hashing, K-Dimensional Tree, Vantage-Point Tree

• How to read problem statements Read the title.

• Deque and Multi-dimensional Subarray Minimas
  Why use RMQ when DQ does trick?

• Chinese Remainder Theorem
  Explained in a crisp and practical manner.

• Geometry Book
  Blog introducing a free and open source handbook/textbook on geometry for competitive programming.

Joke Threads

• Top 10 optimizations 2017 - (collectors edition)
  The greatest codeforces blog of all time.

Problem Collection Blogs

• Segment Tree Problems
• Matrix Exponentiation Problems

Errichto's Streams

Kamil deserves a subheading on his own.

Lecture 1: TODO
Lecture 2: TODO
Lecture 3: Dynamic programming Notes

Curated Ideas:

• Mo's Algorithm
  • Hilbert Order