Programming Knowledge

ICPC Templates

Printable ICPC C++ templates ordered by priority, with the minimum notes needed to recall each one.

Network Flow Problem

maximum flow problem, minimum-cost flow problem

Fast Fourier Transform (FFT)

FFT is an efficient algorithm for computing the Discrete Fourier Transform (DFT) and its inverse, which has applications in polynomial multiplication, signal processing, and more.

Knapsack DP

DP for the knapsack problem, including 0-1, complete, and multiple knapsack variations.

Longest Common Subsequence/Substring (LCS)

Longest Increasing Subsequence (LIS)

C++ STL Containers Cheat Sheet

Hash Table

Data structure for efficient key-value mapping.

Sorting Algorithms

An overview of various sorting algorithms, their time and space complexities, and stability.

Disjoint Set Union / Union-Find

stores a partition of a set into disjoint subsets.

Minimum Spanning Tree (MST)

a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Shortest Path Problem

finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Connected Components and Strongly Connected Components

Finding connected components and strongly connected components in graphs.

Divide and Conquer

recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

2-SAT

Satisfiability of boolean formulas with 2 literals per clause

Graph Traversal

Depth First Search (DFS) and Breadth First Search (BFS) algorithms for graph traversal, including their applications and edge classifications.

Topological Sorting

DAG and Topological Order

Catalan Number

Interesting equations and findings about Catalan Number

Congruence Equation

Congruence equation problems solutions

Linear Sieve Algorithms

Linear sieve algorithms that optimized number sieving problems

Number Theory

Basic algorithms associated with number theory problems

Interval DP

DP for merging intervals with a cost function.

Shortest Path DP

Aho–Corasick Algorithm

dictionary-matching algorithm that locates elements of a finite set of strings

Basic C++ Syntax

An overview of basic syntax in C++ programming

Basis of a Vector Space

Balanced Binary Search Tree

AVL trees and red-black trees; Splay trees and treaps

Arbitrary-Precision Arithmetic (Bignum)

Calculations are not limited to digits of the maximum of languages and computers

Binary / Ternary Search on Answer

Monotonicity Problem and Extreme Value Problem

Binary Tree

binary tree, binary search tree, and heap.

Bipartite Graph

a graph whose vertices can be divided into two disjoint and independent sets

Binary Indexed Tree (BIT)

efficiently compute prefix sums of the values and update the values.

Cantor Expansion

Cartesian Tree

It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

Centroid Decomposition

点分治

Combinatorics

Complex Numbers

Heavy-light Decomposition

effectively solve many problems that come down to queries on a tree

Discretization

transform continuous numbers to discrete numbers

Encapsulation

Several encapsulation struct methods implemented

Fast Input and Output (Fast I/O)

use string buffer read to accelerate read and write

Gaussian Elimination

Hashing

Hash string into numbers for quick query.

K-D Tree (k-dimensional tree)

a space-partitioning data structure for organizing points in a k-dimensional space.

Knuth–Morris–Pratt (KMP) Algorithm

string-searching algorithm that searches for occurrences of a 'word' within a main 'text string'

Binary Lifting and Lowest Common Ancestor (LCA)

query in O(log(n))

Longest Palindromic Substring

finding a maximum-length contiguous substring of a given string that is a palindrome

Matrix Multiplication

C++ code of matrix multiplication implementation.

Maximum Sum Subarray

a contiguous subarray with the largest sum

Möbius

Introduces Mobius function and mobius inversion formula

Hill Climbing and Simulated Annealing Algorithms

爬山算法和模拟退火

Segment Tree

storing information about intervals or segments.

Square Root Decomposition and Mo's Algorithm

devides a sequence into sqrt(n) blocks and solve by blocks

C++ Code Start Template

Stress Testing Harness

automates the execution of tests, confirm if the results are correct, test extreme data limits

Tarjan's Algorithm

strongly connected components

Trie Tree

prefix tree used to store and retrieve strings from a dictionary or set.

Virtual/Auxiliary Trees

虚树