Towards Algorithms and Competitive Programming

This repository contains my notes on common algorithms in competitive programming. The explainations are by no means complete and also very consise. Mainly, it concentrates on the implementation side, to use as a quick look-up. If you find something is missing in a specific section or have a question, please reach out to me! Note this readme is work in progress.

Table of Contents

1. Maths
   1. Number Theory
   2. Combinatorics
      1. Binomial Coefficient
      2. Multinomial Coefficient
      3. Permutations
      4. Catalan Numbers
      5. Fibonacci Numbers
   3. Probability Theory
   4. Game Theory
   5. Fast Matrix Power
   6. Cycle Detetection
2. Graphs
   1. Bicoloring
   2. Cycle-Check on Directed Graphs
   3. Topological Sort
   4. Eulerian Paths
   5. Tree Graphs
      1. Master-Theorem
      2. Diameter/Radius/Center
      3. LCA and Binary Lifting
   6. Minimum Spanning Tree
   7. Shortest Paths
      1. Unweighted SSSP - BFS
      2. Weigthed SSSP - Dijkstra
      3. Weigthed SSSP with negative Cycle - Bellmann-Ford
      4. APSP - Floyd-Warshall
   8. Strongly Connected Components
   9. Articulation Points/Bridges
   10. Maxflow and Mincut
   11. Basic Augmenting
3. Dynammic Data-Structures
   1. Fenwick Tree or Binary Index Tree
   2. Order Statistic Tree
   3. Segment Tree
4. Dynammic Programming
5. String Processing
   1. KMP
   2. Suffix-Trie
6. Else
   1. Convolution
   2. Bit Manipulation

<a name="maths"/>

1 Maths

<a name="nt"/>

1.1 Number Theory

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla laoreet diam egestas libero luctus, id malesuada ex ultrices. Suspendisse vestibulum hendrerit mi, rhoncus imperdiet nisl sodales in. Morbi sit amet lobortis tellus. Duis cursus nunc et velit rhoncus porta. Pellentesque felis orci, viverra et porttitor eget, dignissim sed mi. Donec ac sagittis est. Donec at nibh sem. Suspendisse at pulvinar ligula, ut mollis mauris. Cras ultricies maximus viverra. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos.

</br> </br> </br> </br> </br> <a name="ct"/>

1.2 Combinatorics

<a name="binCof"/>

Binomial Coefficient

When calculating it wihout modulo, use Pascal's Formula to prevent unneccesary overflow when calculating the binomial coefficent.

Pascal's Formula for <img src="https://render.githubusercontent.com/render/math?math=\binom{n}{m}">:

<img src="https://render.githubusercontent.com/render/math?math=\binom{n}{m}=\begin{cases}1, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \text{if } m=0\\1 , \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \text{if } n=m\\\binom{n-1}{m} %2B\binom{n-1}{m-1} , \:\: \text{else}\end{cases}">

Pascal's formula In code (long long overflows for n>66):

vector<vector<ll>>bincoefs(66, vector<ll>(66, 1));
for(int n = 1; n<66; ++n){
    for(int m = 1; m< n; ++m){
        bincoefs[n][m] = bincoefs[n-1][m] + bincoefs[n-1][m-1];
    }
}

With Modulo (precalculate factorials and use modulo arithmetic) - use normal Formula <img src="https://render.githubusercontent.com/render/math?math=\binom{n}{m} = \frac{n!}{(n-m)! \cdot m!}">:

// out of main:
long long C(long long n, long long k, long long m, long long fact[]){
    // binomial coeffiecents with modulo m
    // n! / ((n-k)! k!) 
    // to use the modular arithmetic, we need to finde the inverse of (n-k)! and k! 
    // factorials need to be precalculated and taken modulo
    if(n < k) return 0;
    return (((fact[n] * invEea(fact[k], m)) % m) * invEea(fact[n-k], m)) % m;
}
// in main:
long long fact[100001];
// precalcualte factorials
fact[0]=1;
for(int i=1; i<100001;++i){
    fact[i] = (fact[i-1]*i)%MOD;
}
// 100000 C 5000:
long long ret = C(100000, 50000, MOD, fact);  // (100000 choose 50000)%1000000007 = 149033233

Note:

• Growth for fixed m, approx: <img src="https://render.githubusercontent.com/render/math?math=O(n^m)">
• <img src="https://render.githubusercontent.com/render/math?math=\binom{n}{p}"> is even iff you can find in the binary representation of n a zero where in p is a 1 at the same position.
• To find odd Coeficients: print pascals-triangle
• Difference to Permutations: Order doesn't matter, thus there are fewer combinations than permutations.

When to use

• combinations of n elements taken r: <img src="https://render.githubusercontent.com/render/math?math=\binom{n}{r}">
• Binomial Theorem <img src="https://render.githubusercontent.com/render/math?math=(a %2B b)^k = x_0 a^k %2B x_1 a^{k-1}b^1 %2B \ldots %2B x_{k}b^k">, where <img src="https://render.githubusercontent.com/render/math?math=x_i = \binom{k}{i}">.
• To get all subsets of size k from a set of size n (<img src="https://render.githubusercontent.com/render/math?math=\binom{n}{k}"> many), use backtracking: comb1 and comb2
• Combinations to put r elements in k bins: <img src="https://render.githubusercontent.com/render/math?math=\binom{r %2B k-1}{r}">. To see that, create bijection: separate bins with k-1 stripes "|" (here k=4) and now calculate how many possibiliters there are, to put r dots: <img width="126" alt="Screenshot 2021-05-04 at 03 10 23" src="https://user-images.githubusercontent.com/44442845/126899072-42140c0b-4880-4b5b-bcdb-2934fd517969.png">
• The Power-set. The number of subsets of set with k elements (including the empty set): <img src="https://render.githubusercontent.com/render/math?math=2^k">
• The number of subsets with only even elements of a set with k elements is <img src="https://render.githubusercontent.com/render/math?math=2^{k-1}">. Intuition: Half of the subsets have eben number of elements, the other half odds number of elements. </br> Proof with Pascal's Formula: </br> Number of Subsets with even number of elements: <img src="https://render.githubusercontent.com/render/math?math=\sum_{k=0}^{n/2}\binom{n}{2k} = \sum_{k=0}^{n/2} (\binom{n-1}{2k-1} %2B \binom{n-1}{2k}) = \sum_{k=0}^{n-1} (\binom{n-1}{k}">. </br> You get the same result when only considering subsets with odd elements. Thus they divide perfectly.
• The sum of XOR of all possible subsets of a set with n elemnts:</br> Lets consider only the ith bit, and how the ith bit will contribute to the total sum. Therefore, lets define k as the number of numbers, with the ith bit set.</br> Case 1 k>0:</br> Then we need to take an even number of these. From the set of this k numbers, the number of subsets with an even amount is <img src="https://render.githubusercontent.com/render/math?math=2^{k-1}">, like described above. Now, the amount of other subsequences without ith bit set is <img src="https://render.githubusercontent.com/render/math?math=2^{n-k}">. Multiplied together is the total amount of subsequences with even number of numbers with ith bit set, thus <img src="https://render.githubusercontent.com/render/math?math=2^{n-1}">. Therefore, the total contribution of the ith bit is <img src="https://render.githubusercontent.com/render/math?math=2^{n-1 %2B i}">. Note this does not depend on k, but rather if the bit is set or not in any of these given numbers.</br> Case 2 k==0:</br> Then it does not contribute to the total sum.

int xorSum(vector<int> v){
    int bits = 0;
    for (int i=0; i < v.size(); ++i)
        bits |= v[i];
    return bits * pow(2, v.size()-1);
}

</br> <a name="mulCof"/>

Multinomial Coefficient

Let <img src="https://render.githubusercontent.com/render/math?math=n = b_1 %2B b_2 %2B \ldots %2B b_k"> the multinomial coefficient <img src="https://render.githubusercontent.com/render/math?math=\binom{n}{b_1, b_2, \ldots, b_k}"> is given by:

<img src="https://render.githubusercontent.com/render/math?math=\binom{n}{b_1, b_2, \ldots, b_k} = \binom{n}{b_1} \cdot \binom{n-b_1}{b_2} \cdot \binom{n-b_1-b_2}{b_3} \cdot \ldots \cdot \binom{b_k}{b_k} = \frac{n!}{b_1! \cdot b_2! \cdot \ldots \cdot b_k!} ">

Interpretations:

1. Number of ways to put n interchangeable objets into k boxes, s.t. in box i are <img src="https://render.githubusercontent.com/render/math?math=b_i"> elements
2. Number of unique permutations of a word with n letters and k distinct letters, s.t. i-th letter occurs <img src="https://render.githubusercontent.com/render/math?math=b_i"> times. E.g. permutating a mask vector [1, 1, 1, 1, 0, 0, 0], leads to <img src="https://render.githubusercontent.com/render/math?math=\frac{7!}{4! 3!}">.

</br> <a name="perms"/>

Permutations

Difference to Binomial-Coefficients: Now the Order matters. Total Permutations of sequence of length n: <img src="https://render.githubusercontent.com/render/math?math=n!">.

Implementation via backtracking. In c++, sortable container can be permutated lexicographically (already adjusted for same elements) via in-build prev_permutation and next_permutation:

vector<int> test = {1,2,3};
while (next_permutation(test.begin(), test.end())){
    // do sth
}

When to use

• permutations of n elements taken only r: <img src="https://render.githubusercontent.com/render/math?math=\frac{n!}{(n-r)!}">, meaning the permutatins of the remaining (n-r) are not included
• Derangement count: Count all permutations in