A "hackpack" is a compilation of implementations of various algorithms, data structures, and niche problems that have a good chance of showing up in contests; it functions as a safety net during the implementation stage of developing a solution. As I gain more experience through mocking past contests, upsolving problems, and competing in live competitions, the code in the hackpack that I bring to each contest will change.
The algorithm and special technique implementations I currently bring to competitions are listed below.
- Finding Articulation Points and 2VCCs
- Classic Backtracking
- Bellman–Ford with Check for Negative Weight Cycles
- General BFS Technique
- 0-1 BFS
- Finding Bridges and 2ECCs
- Centroid Decomposition of a Tree
- Chinese Remainder Theorem
- Static 2D Convex Hull
- Incremental 2D Convex Hull
- Offline Convex Hull Trick
- Online Convex Hull Trick
- General DFS Technique
- Dijkstra's Single Source Shortest Path
- Eulerian Path
- Dinic's Max Flow (Slower to Implement, Faster to Run) in Maximum Matching Problem
- Edmonds–Karp Max Flow (Faster to Implement, Slower to Run) in Minimum Cut Problem
- Min Cost Flow
- Floyd-Warshall All Pairs Shortest Path with Check for Negative Weight Cycles
- Gaussian Elimination
- Hashing Technique
- Heavy Light Decomposition
- Knuth DP Optimization
- Knuth–Morris–Pratt String-Searching
- Kruskal's MST
- Fast Longest Increasing Subsequence
- Fast Lowest Common Ancestor
- Markov Chain
- Fast Matrix Exponentiation
- Meet-in-the-Middle
- Miller–Rabin Primality Test
- Euclidean Modular Inverse
- Mo's Algorithm
- Prime Sieve
- Prim's MST
- Square Root Decomposition
- Finding Strongly Connected Components
- Ternary Search
- Traveling Salesman Problem
- Two-Satisfiability Problem
The data structure implementations I currently bring to competitions are listed below.
- Disjoint Set
- Classic Fenwick Tree (a.k.a. Binary Indexed Tree or BIT)
- 2D Fenwick Tree
- Max Queue
- Merge Sort Tree
- Point Update Segment Tree
- Lazy Propagation Segment Tree
- BIT of Dynamic Segment Trees
- Sparse Table
- Suffix Automaton
- Trie
The niche problem implementations I currently bring to competitions are listed below.
- Finding Intersections of Line Segments
- Counting the Number of Intersections Between Horizontal and Vertical Line Segments
- Checking if a Point is Inside a Polygon
- Number of Permutations of a String Lexicographically Less Than Another String
- Finding the Max Clique
- Maximizing the Number of Disjoint Pairs of Connected Edges
- Count the Number of Unit Squares Fully Inside a Polygon
- Classic Cutcake Game
- Escaping a Circular Perimeter (Classic Game Theory)
- Check if a Binary Matrix With Given Row and Column Sums Exists
- Number of Permutations With No Two Adjacent Equal Elements
- Minimum Weight of a Complete Graph Given a Unique Spanning Tree
- Rearrange Elements in a Matrix to Make All Rows and Columns Palindromes
- Number of Ways to Tile a 3 by N Grid With 2 by 1 Dominoes
- Number of Ways to Tile Any Grid With 2 by 1 Dominoes
- Moves Left in Tower of Hanoi Puzzle
- Querying the Farthest Node From Any Node on a Tree
- Finding the Kth Largest Element With a Fenwick Tree
- Finding the Length and Number of Diameters in a Tree
- Finding the Dominating Set of a Tree
- Counting the Number of Topological Sorts
- Generating the Nth Lexicographically Smallest Subset
- Counting Derangements of Pairings
- Maximum Sum Rectangle in a Matrix
- Efficient Submask Generation
- Longest Increasing Subsequence for Pairs
- Counting the Number of Minimum Spanning Trees
- Calculating Bell Numbers
- Manhattan MST
- Maximum Number of Circles Intersected by a Single Line
- Maximum Size of a Rectangle in a Grid with Obstacles
- Assignment Problem with Hungarian Algorithm
- Tree Isomorphism
Other useful implementations that do not fall under any of the three categories above are listed below.