luchobazz / cpp-algorithm-snippets Goto Github PK

🚀 In this repository there is a collection of useful algorithms to use in competitive programming.

License: MIT License

C++ 98.56% Shell 0.38% Python 1.06%

algorithms classical-algorithms data-structures competitive-programming graph geometry string query-range misc

cpp-algorithm-snippets's Issues

Add floordiv and ceildiv for positives and negatives

// Reference: https://codeforces.com/contest/1782/submission/230743928
int floordiv(int a, int b) {
  return a > 0 ? a / b : -((-a + b - 1) / b);
}
 
int ceildiv(int a, int b) {
  return a > 0 ? (a + b - 1) / b : -(-a / b);
}

issue: is_prime is wrong for 1, is_prime(1) give true

Add GCD Properties

Properties of GCD (Greatest Common Divisor)

Blueprint of Numbers: The GCD of a set of numbers can be thought of as a blueprint of those numbers. If you keep adding the GCD, you can make all numbers that belong to that set.
Common Divisors: Every common divisor of $a$ and $b$ is a divisor of $\gcd(a,b)$ .
Linear Combination: $\gcd(a,b)$ , where both $a$ and $b$ are non-zero, can also be defined as the smallest positive integer $d$ which can be expressed as a linear combination of $a$ and $b$ in the form

$d = a \cdot p + b \cdot q$

where both $p$ and $q$ are integers.
GCD with Zero:

$\gcd(a, 0) = |a|, \text{ for } a \neq 0$

since any number is a divisor of 0, and the greatest divisor of $a$ is $|a|$ .
Division Property: If $a$ divides $b \cdot c$ and $\gcd(a,b) = d$ , then

$\frac{a}{d} \text{ divides } c$
Scaling Property: If $m$ is a non-negative integer, then

$\gcd(m \cdot a, m \cdot b) = m \cdot \gcd(a, b)$

It also follows from this property that if $\gcd(a,b) = g$ , then

$\frac{a}{g} \text{ and } \frac{b}{g} \text{ should be coprime.}$
Translation Property: If $m$ is any integer,

$\gcd(a,b) = \gcd(a + m \cdot b, b)$
Euclidean Algorithm: The GCD can be found using the Euclidean algorithm:

$\gcd(a, b) = \gcd(b, a \mod b)$
Common Divisor Scaling: If $m$ is a positive common divisor of $a$ and $b$ , then

$\gcd\left(\frac{a}{m}, \frac{b}{m}\right) = \frac{\gcd(a, b)}{m}$
Multiplicative Function: The GCD is a multiplicative function. That is, if $a_1$ and $a_2$ are coprime,

$\gcd(a_1 \cdot a_2, b) = \gcd(a_1, b) \cdot \gcd(a_2, b)$

In particular, recalling that GCD is a positive integer-valued function, we obtain that

$\gcd(a, b \cdot c) = 1 \text{ if and only if } \gcd(a, b) = 1 \text{ and } \gcd(a, c) = 1.$

If the GCD is one, then they need not be coprime to distribute the GCD; moreover, each GCD individually should also be 1.
Commutative Property: The GCD is a commutative function:

$\gcd(a, b) = \gcd(b, a)$
Associative Property: The GCD is an associative function:

$\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$

Thus,

$\gcd(a, b, c, \ldots)$

can be used to denote the GCD of multiple arguments.
Relation with LCM: $\gcd(a, b)$ is closely related to the least common multiple $\operatorname{lcm}(a, b)$ : we have

$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |a \cdot b|$
Distributivity Versions: The following versions of distributivity hold true:

$\gcd(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(a, c))$

$\operatorname{lcm}(a, \gcd(b, c)) = \gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(a, c))$
Prime Factorization: If we have the unique prime factorizations of $a = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$ and $b = p_1^{f_1} p_2^{f_2} \cdots p_m^{f_m}$ , where $e_i \geq 0$ and $f_i \geq 0$ , then the GCD of $a$ and $b$ is:

$\gcd(a,b) = p_1^{\min(e_1,f_1)} p_2^{\min(e_2,f_2)} \cdots p_m^{\min(e_m,f_m)}$
Cartesian Coordinate System Interpretation: In a Cartesian coordinate system, $\gcd(a, b)$ can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points $(0, 0)$ and $(a, b)$ .
Euclidean Algorithm in Base $n$ : For non-negative integers $a$ and $b$ , where $a$ and $b$ are not both zero, provable by considering the Euclidean algorithm in base $n$ , it simply states that:

$\gcd(n^a - 1, n^b - 1) = n^{\gcd(a, b)} - 1$

If you want an informal proof, think of numbers in base 2. We are calculating GCDs of numbers which contain all continuous 1s in their binary representations. For example: 001111 and 000011; their GCD can be the greatest common length, which in this case is 2. Thus, the GCD becomes 000011. Think of numbers in terms of length; maybe you get the idea.
Euler's Totient Function Identity: An identity involving Euler's totient function:

$\gcd(a,b) = \sum \phi(k)$

where $k$ are all common divisors of $a$ and $b$ .

Reference

Add Math Formulas

feat: Add AhoCorasick Online

Codeforces reference

Add Argsort

template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

Add Geometric progression Implementation

Reference

Codeforces LuchoBazz Implementation

Add the infinite and unreachable loop macros in the template

#define infinity while(1)
#define unreachable assert(false && "Unreachable");

Add Disjoint Sparse Table

tourist reference

References

https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf

Reference PersistentSimpleSegmentTree

PersistentSimpleSegmentTree - Tourist Implementation

Problems:

issue: file `generate_vscode_snippets.py` for Windows don't work

Windows Path
C:/Users/USER/AppData/Roaming/Code/User/snippets/cpp.json

feat: Add Optimizations Pragmas

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

Counting Paths
Test using Merge trick on trees

Codeforces Reference

Add Formatter

clang-format -style='{IndentWidth: 4, ColumnLimit: 80}' -i A.cpp

file: .clang-format

BasedOnStyle: LLVM
IndentWidth: 4
ColumnLimit: 80

.github/workflows/clang-format.yml

name: Clang-Format Check

on:
  pull_request:
    branches:
      - main
      - master
  push:
    branches:
      - main
      - master

jobs:
  clang-format:
    runs-on: ubuntu-latest

    steps:
    - name: Checkout repository
      uses: actions/checkout@v2

    - name: Set up clang-format
      run: sudo apt-get install -y clang-format

    - name: Run clang-format
      run: |
        # Find all C++ source files and check if they comply with the format
        FILES=$(find . -name '*.cpp' -o -name '*.hpp' -o -name '*.h' -o -name '*.c')
        for file in $FILES; do
          clang-format --style=file $file | diff -u $file -
        done

    - name: Fail if format is incorrect
      run: |
        FILES=$(find . -name '*.cpp' -o -name '*.hpp' -o -name '*.h' -o -name '*.c')
        for file in $FILES; do
          if ! clang-format --style=file $file | diff -u $file -; then
            echo "Formatting error in $file"
            exit 1
          fi
        done

Update Template

const string ALPHA = "abcdefghijklmnopqrstuvwxyz";

Powerfull FenwickTree

https://codeforces.com/contest/159/submission/213953589

template <typename Monoid>
struct FenwickTree {
  using G = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;
  E total;
 
  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }
 
  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }
 
  E prod_all() { return total; }
  E sum_all() { return total; }
  E sum(int k) { return prefix_sum(k); }
  E prod(int k) { return prefix_prod(k); }
  E prefix_sum(int k) { return prefix_prod(k); }
  E prefix_prod(int k) {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) { return prod(L, R); }
  E prod(int L, int R) {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
    while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
    return G::op(pos, G::inverse(neg));
  }
 
  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }
 
  template <class F>
  int max_right(const F check) {
    assert(check(G::unit()));
    int i = 0;
    E s = G::unit();
    int k = 1;
    while (2 * k <= n) k *= 2;
    while (k) {
      if (i + k - 1 < len(dat)) {
        E t = G::op(s, dat[i + k - 1]);
        if (check(t)) { i += k, s = t; }
      }
      k >>= 1;
    }
    return i;
  }
 
  int kth(E k) {
    return max_right([&k](E x) -> bool { return x <= k; });
  }
};

Enhancement: Add `<< ' ' <<` to misc

#define _ << ' ' <<

// usage: 
cout << x _ y << endl;
// cout << x << ' ' << y << endl;

Add Shortest Sparce Table

Reference: Codeforces by Franchesco_virgoliniiii

struct RMQ {
  vector<vector<int>> table;
  RMQ(vector<int> &v) : table(20, vector<int>(v.size())) {
    int n = v.size();
    for (int i = 0; i < n; i++) table[0][i] = v[i];
    for (int j = 1; (1<<j) <= n; j++)
      for (int i = 0; i + (1<<j-1) < n; i++)
        table[j][i] = max(table[j-1][i], table[j-1][i + (1<<j-1)]);
  }
  int query(int a, int b) {
    int j = 31 - __builtin_clz(b-a+1);
    return max(table[j][a], table[j][b-(1<<j)+1]);
  }
};

Time Testing

https://codeforces.com/contest/1/submission/246338459

feat: Add Minimum Expression algorithm

enhancement: add integer of 128 bit in c++ for codeforces c++20

Reference - jiangly Implementation i128

For GNU G++20 11.2.0 (64 bit, winlibs) >=

// Input: 1267650600228229401496703205376
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;
const i128 ONE_128 = i128(1);
const i128 ZERO_128 = i128(0);


std::istream &operator>>(std::istream &is, i128 &n) {
    n = 0;
    std::string s;
    is >> s;
    
    for (auto c : s) {
        n = 10 * n + c - '0';
    }
    return is;
}
 
std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}


int main() {
    
    i128 number; cin >> number;
    
    for(int i = 128-1; i >= 0; i--) {
        cout << bool(number & (ONE_128 << i));
    }
    cout << endl;
    
    cout << number << endl;
    
    return 0;   
}

Add Formatter

clang-format -style='{IndentWidth: 4, ColumnLimit: 80}' -i A.cpp

Naming Collection (Backup)

Variables Naming

Prefix

do_
has_
can_
compute_
build_
make_

Verbs

 best
item
quantity
unknown_process
works
have
need
previous
nxt
current
buckets
turn
half
split
was
edge
ask
missing
extra
total
res
skip
at
base

range_query/range_query_dynamic_segment_tree.cpp don't work

input: vector<int> data{3, 2, 4, 5, 1, 1, 5, 3};
query: st.query(0, 3).sum
answer: 0 Wrong Answer

See: CSES

feat: Add diameter of a tree

Tree Diameter

Segment Tree Compress

Tourist Code

struct SegmTree {
  vector<int> T; int n;
  SegmTree(int n) : T(2 * n, (int)-2e9), n(n) {}
  
  void Update(int pos, int val) {
    for (T[pos += n] = val; pos > 1; pos /= 2)
      T[pos / 2] = max(T[pos], T[pos ^ 1]);
  }
  
  int Query(int b, int e) {
    int res = -2e9;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) res = max(res, T[b++]);
      if (e % 2) res = max(res, T[--e]);
    }
    return res;
  }
};

reference: Add reference of two pointers technique

Pluralsight - Two Pointer

issue: range_query_sum_immutable.cpp give Compiler Error

Change

PrefixSum() n(-1) {}

PrefixSum(): n(-1) {}

docs: add docs about usage `range_query/range_query_segment_tree_lazy_full.cpp`

add usage examples
add string in assets to identify them when errors occur - example
assert(0 <= left && left <= right && right <= n - 1 && "query");

Test and Add Huffman Code

const char SPECIAL_CH = '$';
const string FIRST_ALPHA = "0";
const string SECOND_ALPHA = "1";
struct HffTreeNode {
    // One of the input characters
    char ch;
    // Frequency of the character
    uint32_t freq;
    // Left and right child
    HffTreeNode *left, *right;
    HffTreeNode(char ch, uint32_t freq) {
        left = right = NULL;
        this->ch = ch;
        this->freq = freq;
    }
};

struct Code {
    char ch;
    string bin;
};

// For comparison of
// two heap nodes (needed in min heap)
struct Compare {
    bool operator()(HffTreeNode* l, HffTreeNode* r) {
        return l->freq > r->freq;
    }
};
 
// Prints huffman codes from
// the root of Huffman Tree.
void buildCodes(vector<Code> &codes, struct HffTreeNode* root, string str) {
    if (!root) return;
    if (root->ch != SPECIAL_CH) codes.push_back(Code{root->ch, str});
    buildCodes(codes, root->left, str + FIRST_ALPHA);
    buildCodes(codes, root->right, str + SECOND_ALPHA);
}
 
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
HffTreeNode* HuffmanCodes(vector<char> alpha, vector<int> freq) {
    int size = (int) alpha.size();
    struct HffTreeNode *left, *right, *top;
    // Create a min heap & inserts all characters of alpha[]
    priority_queue<HffTreeNode*, vector<HffTreeNode*>, Compare> minHeap;
    
    for (int i = 0; i < size; ++i) {
        minHeap.push(new HffTreeNode(alpha[i], freq[i]));
    }
    #define pop_heap(heap) heap.top(); heap.pop();
    
    // Iterate while size of heap doesn't become 1
    while (minHeap.size() != 1) {
        // Extract the two minimum
        // freq items from min heap
        left = pop_heap(minHeap);
        right = pop_heap(minHeap);
        // Create a new internal node with frequency equal to the sum of the
        // two nodes frequencies. Make the two extracted node as left and right
        // children of this new node. Add this node to the min heap '$'
        // is a special value for internal nodes, not used
        top = new HffTreeNode(SPECIAL_CH, left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    return minHeap.top();
}

// Usage:
// vector<char> alpha = { 'a', 'b', 'c', 'd', 'e', 'f' };
// vector<int> freq = { 5, 9, 12, 13, 16, 45 };
// HffTreeNode* root = HuffmanCodes(alpha, freq);
// vector<Code> codes;
// buildCodes(codes, root, "");
// for(auto &code: codes) cout << code.ch << ": " << code.bin << endl;

Assembly in Codeforces

Diego Reference - Codeforces

docs: Add example of y_combinator

auto go = y_combinator([&](auto Go, int idx) -> int64 {
    // Go(idx-1);
});

int ans = go(0);

Things to Keep in Mind

English 🇺🇸

int overflow, time and memory limits
Special case (n = 1?)
Do something instead of nothing and stay organized
Don't get stuck in one approach
For some special cases, are there many, could you hard code them in the code? Example 1-Example 2

Spanish 🇪🇸

int overflow, Limites en Tiempo y Memoria
Caso especial (n = 1?)
Haz algo en lugar de nada y organízate
No se estanque en un único enfoque
Para algunos casos especiales, ¿son muchos?, ¿podría hard codearlos en el código? Ejemplo 1-Ejemplo 2

Add Shortest Modular Number

Codeforces Reference: osWAr_s73

proposal: XOR basis Technique

feat: Add StableSum for floating point values

Handbook of geometry for competitive programmers Page: 20

issue: possible overflow in Bellman Ford algorithm

change:

if(dist[e.from] + e.cost < dist[e.to] && dist[e.from] != inf)

to:

if(dist[e.from] != inf && dist[e.from] + e.cost < dist[e.to])

issue: graph/graph_dijkstra_std.cpp give TLE in Shortest Routes I problem cses.fi

Problem: Shortest Routes I

luchobazz / cpp-algorithm-snippets Goto Github PK

cpp-algorithm-snippets's Issues

Properties of GCD (Greatest Common Divisor)

Reference

Variables Naming

Prefix

Verbs

English 🇺🇸

Spanish 🇪🇸

Recommend Projects

Recommend Topics

Recommend Org