The ACM ICPC competition is an annual competitive programming competition among universities of the world. Teams compete in regional contests to qualify for the World Finals. During that contests between 8 and 15 problems have to be solved in a time period usually around 5 hours. The problems covers a large range of topics in computer science.

During my studies of computer science I participated three times for the German team of the Karlsruher Institute of Technology on regional contests. In this repository you will find solved problems from various competitive programming resources and several basic algorithms. In contrast to other ICPC repositories on github I focus on readibility and understanding of the algorithms, while simultanously ensure that the implementations are short and easy to integrate into solutions of problems.

Algorithms

In this Section, I list several algorithms you can find in this repository with its links to the source code.

Graph

1. Single Source Shortest Path (Dijkstra's Algorithm)
2. Maximum Flow (Edmond-Karps Algorithm)
3. Minimum Spanning Tree (Kruskal's and Jarnik-Prims Algorithm)
4. Strongly Connected Components (Tarjan's Algorithm)

Data Structures

1. Range Minimum Query
2. Lowest Common Ancestor
3. Generic Segment Tree
   You can use this segment tree to implement all kinds of applications, which can be solved with this data structure without changing the implementation. In the source code I provide detailed examples how to implement e.g.:
   a. Range Minimum Query
   b. Range Maximum Query
   c. Range Minmax Query
   d. Interval Sum
   e. Interval Product
4. 2D Range Search
   Given a rectangle the data structure returns all points inside the rectangle.
5. 2D Range Maximum Query (K2Treap)
   Given a rectangle the data structure returns the point with maximum weight inside the rectangle.
6. Fenwick Tree
   Implements interval sum in O(1) with update functionallity in O(log(n))

String

1. Suffix Array
2. Trie
3. Wavelet Tree

Primes

1. Sieve of Eratosthenes and Factorization

Sequences

1. Longest Common Subsequence
   Special Implementation which runs on random inputs in O(n*log(n)) time.
2. Longest Increasing Subsequence
   Implementation returns longest increasing subsequence in O(n*log(n)) time.

Others

1. Bit Vector
2. Centered Interval Tree
3. x-Fast-Trie