Code

This repo contains various bits of code that can be used for competitive programming. Some relatively difficult problems can only be solved using these data structures or algorithms. Readability is a concern, but reducing lines of code is prioritized for use in cheat sheets / team notebooks.

C++ is the default language used here. This choice here is that C++ is usually the fastest language in common use for competitive programming, and that usually C++ can be translated into other languages while the opposite is not necessarily true. Sometimes unique features of C++ is used, but generally it can be converted to other languages without much hassle.

Included is an ICPC style team notebook using the snippets, as well as some benchmarks and test cases for the snippets.

How to Contribute

• create new snippets
• improve existing snippets
• write tests for existing snippets
• add links to problems solvable by snippets
• benchmark snippets against other methods

Information

Algorithms

• Binary Search - Find the position of a target value within a sorted array.
• Golden Section Search - Find the minima or maxima of a function inside an interval.
• Min/Max Subarray - Find the maximum subarray given an array of integers. Same with minimum subarray.
• QuickSelect - Search for an element in an unsorted array, similar to a binary search but without the sorted restriction. Effectively performs quicksort, but only on the relevant subsections of the array. This does swap elements within the array and will alter the array's ordering.
• Saddleback Search - Given a 2D array sorted on both axis, find if a value exists and return its location.
• Ternary Search - Given a function, search for the minimum or maximum (or any other unimodal function) of a range. Will do so in O(log3 n) where n is the range being used.

Data Structures

• Fenwick Tree - efficient structure for keeping track of and updating cumulative sums. Updates sums in O(log n)
• Hash Table - faster version of std::unordered_map
• Ordered Set - version of std::set with array-like access methods, including map variant
• Rope - version of string, optimized for insertions/deletions at arbitrary points within the string.
• Segment Tree - A tree for storing intervals, and allows for quick queries to find which interval contains a given point.
• Sparse Table - Fast lookups for range min/max queries.
• Trie - prefix tree, or a tree that stores strings based on common prefixes.
• Wavelet Tree - Store strings or suffix arrays in a compressed way

Graph

• Dijkstra's Algorithm - Find the shortest path between two nodes in a graph.
• Eulerian Path - Find a path that visits each node exactly once, if it exists.
• Floyd Warshall - all-pairs shortest path / transitive closure / negative cycle detection.
• Grid Shortcuts - utilities to make grid problems easier to tackle
• Minimum Spanning Tree - Primm's algorithm for generating the minimum spanning tree of a given graph and its weight
• Union Find - determine subsets that nodes belong to

Math

• Catalan - generate the catalan numbers under a modulus
• Combinatorics - functions related to combinatorics
• • nCr - number of combinations, either whole or under a modulo
• • nPr - number of permutations, either whole or under a modulo
• Chinese Remainder Theorem - extended chinese remainder theorem
• Discrete Logarithm - logarithm based on modulus
• Euler Phi - positive integers up to n that are relatively prime to n
• Factorials - Quick methods for calculating factorials
• • Kamenetsky's Formula - approximate number of digits of a factorial
• • Stirling's Approximation - approximation of a factorial
• • Log Factorial - natural log of a factorial computed very quickly
• Prime Factorization - quickly find the prime factorization of a number using Pollard Rho
• Farey Sequence - generate a list of increasing fractions from 0/1 to 1/1
• Fast Fourier Transform - calculate the Discrete Fourier transform of a polynomial quickly
• • Polynomial Multiplication - quickly calculate the multiplication of two polynomials using the fft
• Extended Greatest Common Denominator - Extended Euclidean algorithm, given a and b calculates x, y, gcd(a, b) in ax + by = gcd(a, b)
• Josephus Problem - last remaining spot in a circle, where each spot removes another spot a certain distance from it. Both supports arbitrary distance, and a fast case if distance is 2 (the traditional Josephus problem).
• Lowest Common Multiple - calculated the lcm of two numbers
• Modulo Math - modular addition, multiplication, division, subtraction, powers, factorials, and inverses
• Miller-Rabin Primality Test - quick probabilistic test whether a number is prime or not
• Sieve of Eratosthenes - generate a prime sieve to allow for very fast lookups whether a number is prime or not
• Simpson's Rule - approximation of an integral of a function
• Equation Solver - solve quadratic and cubic functions

String

• Number Converter - convert an integer into its english equivalent
• Find Substrings - algorithms for finding occurences of a substring within a larger string
• • Aho-Corasick - search for multiple patterns/keywords at once, using automata
• • Boyer-Moore - suited for larger sets like english text, slightly less common than kmp
• • Knuth-Morris-Pratt - suited for small sets like numbers / DNA, common and popular substring search algorithm for competitive programming
• Longest Common Prefix - sort-based method of determining the longest prefix shared among all elements in an array
• Longest Common Subsequence - dynamic programming solution for finding the longest subsequence shared between two strings
• Longest Palindrome Substring - Manacher's algorithm for finding the palindrome length of every substring of a given string
• Subsequence Count - dynamic programming solution for counting the number of times a string appears as a subsequence in a larger string

2D Geometry

• Basics - basic declarations of various shapes and methods
• Intersections - various intersection calculations
• Convex Hull - get the convex_polygon from a simple polygon
• Counting Colinear Points - counting the maximum number of colinear points

3D Geometry

• Basics - basic declarations of various shapes and methods