krofna / snippets Goto Github PK

This is a collection of algorithms and data structures I use in programming contests.

The goal of every snippet is to be short, simple, performant, and easy to copy-paste into other programs whenever needed.

Note that the code is not necessarily pedantic nor easy to understand. Common good programming practices are intentionally violated. Global variables, misuse of namespaces, inconsistent variable names, weird hacks, etc. are all over the place, and that's OK.

Strings:

• Aho-Corasick (string searching)
• Knuth-Morris-Pratt (string searching)
• Manacher's algorithm (finding palindromes)
• Minimum lexicographic rotation
• Palindromic tree (trie of all substring palindromes)
• Suffix array and LCP
• Z algorithm (matching all suffixes with longest prefix)

Graphs:

• Articulation points
• Circulation (a variant of network flow)
• Dinic's algorithm (maximum flow)
• Directed minimum spanning tree (arborescence)
• Heavy-light decomposition of a tree
• Min-cost max-flow using DFS
• Min-cost max-flow using Dijkstra
• Common tree algorithms

Math:

• Convex hull of 2D points
• Counting primes up to N
• Euclidean algorithm (GCD, Diophantine equations)
• Rounded integer division
• Gaussian elimination
• Modular Gaussian elimination
• Fast Fourier transform
• Matrix multiplication and exponentiation
• Sieve of Eratosthenes

Other:

• Monotone queue (can tell maximum element in O(1))

All snippets assume that you have the following predefined:

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long llint;

Just copy-paste any snippet in your code and follow instructions in comments.

Yes, they're very likely to be.

All snippets were tested in solutions to multiple programming problems, and used as a reference in two ACM-ICPC world finals.

Yes, I don't mind.

Just make sure you understand the rules of competitions you participate in. Sometimes they require solutions to be fully written by yourself.