<commit_before>ACM-ICPC 
===============

List of algorithms and data structures for algorithmic programming competitions (International Olympiad in Informatics (IOI),  ACM International Collegiate Programming Competition (ICPC), Google Code Jam, Facebook Hacker Cup, etc.).

In the past, this list has been quite useful for solving algorithmic programming challenges on online judges like the Sphere Online Judge (SPOJ) and competitions.

Most of this has been coded during high-school (2008-2010) while preparing for the IOI. Consider this a disclaimer about the coding style. I will try to improve the code whenever I have some free time. If you see any errors, please feel free to set an issue, or even better, make a pull request.

The code is licensed under the MIT License, free to use, have fun!

### Algebra

* **Bignum** (addition, subtraction, multiplication, division)
* **Prime Factorization** *O(sqrt(n))*
* **Prime Number Generator** (Sieve of Eratosthenes)
* **GCD** (Greatest Common Divisor)
* **LCD** (Lowest Common Multiple)
* **Linear Congruence** (Extended GCD)

### Combinatorics

* **All Permutations**
* **All Subsets**
* **Next Permutation** (alphabetically higher) 

### Graph Theory

* **DFS** (Depth-First Search)
* **BFS** (Breadth-First Search)
* **Connected Components**
* **Dijkstra's Algorithm** (One Way Shortest Path)
* **Bellman Ford** (for negative weights)
* **Prim's Algorithm** (Minimum Spanning Tree)
* **Kruskal's Algorithm** (Minimum Spanning Tree)
* **Floyd-Warshall** (All Way Shortest Path)
* **Toposort** (Topological Sort)
* **ArticFind** (Find all Articulation Points), *O(E)*
* **Bipartite Matching**
* **Ford-Fulkerson's Algorithm** (Maxflow/Mincut)
* **Ford-Fulkerson's Algorithm  with Capacity Scaling** (Maxflow/Mincut)
* **Dinic's Algorithm** (Maxflow/Mincut)
* **Edmonds-Karp's Algorithm** (Maxflow/Mincut)
* **Hierholzer's Algorithm** (Euler Cycle detection)

### Computational Geometry

* **Line-Line Intersection**
* **Segment-Segment Intersection**
* **Area of Polygon**
* **Line-Point Distance**
* **Point-Segment Distance**
* **Circle from Three Points**
* **Reflection**
* **Rotation**
* **Graham's Scan Algorithm** (Convex Hull)
* **Area of a Triangle** (three points)
* **Bentley-Ottman's Algorithm** (Sweep Line, finding all intersections of multiple line segments)
* **Shamos-Hoey Algorithm** (checking if there is an intersection given multiple line segments)
* **Crossing Number** (resp. Winding Number, method to check whether a point is inside a simple polygon (resp. non-simple polygon))

### Data Structures

* **Queue**
* **Stack**
* **Linked List**
* **Doubly Linked List**
* **Vectors**
* **Binary Tree**
* **Trie**
* **Hash Table**
* **Priority-Queue**
* **Heap**
* **Binary Indexed Tree** (BIT)
* **2D Binary Indexed Tree** (2D BIT)
* **Segment Tree**
* **Suffix Array** (resp. Suffix Sorting, determine if string was a subseq. of another string)
* **Suffix Tree**
* **Disjoint-Set Data Structure** (Union-Find)

### Dynamic Programming

A selection of solutions to fairly standard DP problems.

* **Edit Distance**
* **Longest Common Subsequence** (LCS)
* **Longest Increasing Subsequence** (LIS), *O(nlogn)*
* **Matrix Chain Multiplication** (MCM)
* **Maximum Empty Rectangle** (MER)
* **Stable Marriage Problem**
* **Binomial Coefficient Solver**

### String Manipulation

* **String Handling** (in general)
* **<NAME>** (String Search)

### Misc

* **Majority Vote**
* **Inclusion/Exclusion** (using bit tricks)<commit_msg>Changed subtitles formatting.<commit_after>ACM-ICPC 
===============

List of algorithms and data structures for algorithmic programming competitions (International Olympiad in Informatics (IOI),  ACM International Collegiate Programming Competition (ICPC), Google Code Jam, Facebook Hacker Cup, etc.).

In the past, this list has been quite useful for solving algorithmic programming challenges on online judges like the Sphere Online Judge (SPOJ) and competitions.

Most of this has been coded during high-school (2008-2010) while preparing for the IOI. Consider this a disclaimer about the coding style. I will try to improve the code whenever I have some free time. If you see any errors, please feel free to set an issue, or even better, make a pull request.

The code is licensed under the MIT License, free to use, have fun!

Algebra
--------------------------


* **Bignum** (addition, subtraction, multiplication, division)
* **Prime Factorization** *O(sqrt(n))*
* **Prime Number Generator** (Sieve of Eratosthenes)
* **GCD** (Greatest Common Divisor)
* **LCD** (Lowest Common Multiple)
* **Linear Congruence** (Extended GCD)

Combinatorics
--------------------------

* **All Permutations**
* **All Subsets**
* **Next Permutation** (alphabetically higher) 

Graph Theory
--------------------------

* **DFS** (Depth-First Search)
* **BFS** (Breadth-First Search)
* **Connected Components**
* **Dijkstra's Algorithm** (One Way Shortest Path)
* **Bellman Ford** (for negative weights)
* **Prim's Algorithm** (Minimum Spanning Tree)
* **Kruskal's Algorithm** (Minimum Spanning Tree)
* **Floyd-Warshall** (All Way Shortest Path)
* **Toposort** (Topological Sort)
* **ArticFind** (Find all Articulation Points), *O(E)*
* **Bipartite Matching**
* **Ford-Fulkerson's Algorithm** (Maxflow/Mincut)
* **Ford-Fulkerson's Algorithm  with Capacity Scaling** (Maxflow/Mincut)
* **Dinic's Algorithm** (Maxflow/Mincut)
* **Edmonds-Karp's Algorithm** (Maxflow/Mincut)
* **Hierholzer's Algorithm** (Euler Cycle detection)

Computational Geometry
--------------------------

* **Line-Line Intersection**
* **Segment-Segment Intersection**
* **Area of Polygon**
* **Line-Point Distance**
* **Point-Segment Distance**
* **Circle from Three Points**
* **Reflection**
* **Rotation**
* **Graham's Scan Algorithm** (Convex Hull)
* **Area of a Triangle** (three points)
* **Bentley-Ottman's Algorithm** (Sweep Line, finding all intersections of multiple line segments)
* **Shamos-Hoey Algorithm** (checking if there is an intersection given multiple line segments)
* **Crossing Number** (resp. Winding Number, method to check whether a point is inside a simple polygon (resp. non-simple polygon))

Data Structures
--------------------------

* **Queue**
* **Stack**
* **Linked List**
* **Doubly Linked List**
* **Vectors**
* **Binary Tree**
* **Trie**
* **Hash Table**
* **Priority-Queue**
* **Heap**
* **Binary Indexed Tree** (BIT)
* **2D Binary Indexed Tree** (2D BIT)
* **Segment Tree**
* **Suffix Array** (resp. Suffix Sorting, determine if string was a subseq. of another string)
* **Suffix Tree**
* **Disjoint-Set Data Structure** (Union-Find)

Dynamic Programming
--------------------------

A selection of solutions to fairly standard DP problems.

* **Edit Distance**
* **Longest Common Subsequence** (LCS)
* **Longest Increasing Subsequence** (LIS), *O(nlogn)*
* **Matrix Chain Multiplication** (MCM)
* **Maximum Empty Rectangle** (MER)
* **Stable Marriage Problem**
* **Binomial Coefficient Solver**

String Manipulation
--------------------------

* **String Handling** (in general)
* **<NAME>** (String Search)

Misc
--------------------------

* **Majority Vote**
* **Inclusion/Exclusion** (using bit tricks)
{'fraction_non_alphanumeric': 0.17320759950076273, 'fraction_numerical': 0.002773540424351685, 'mean_word_length': 4.656470588235294, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2666812', 'n_tokens_mistral': 2276, 'n_tokens_neox': 2106, 'n_words': 795}