luchobazz / cpp-algorithm-snippets Goto Github PK
View Code? Open in Web Editor NEW🚀 In this repository there is a collection of useful algorithms to use in competitive programming.
License: MIT License
🚀 In this repository there is a collection of useful algorithms to use in competitive programming.
License: MIT License
// 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);
}
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 and
is a divisor of
.
Linear Combination: , where both
and
are non-zero, can also be defined as the smallest positive integer
which can be expressed as a linear combination of
and
in the form
GCD with Zero:
since any number is a divisor of 0, and the greatest divisor of is
.
Scaling Property: If is a non-negative integer, then
Euclidean Algorithm: The GCD can be found using the Euclidean algorithm:
Common Divisor Scaling: If is a positive common divisor of
and
, then
Multiplicative Function: The GCD is a multiplicative function. That is, if and
are coprime,
In particular, recalling that GCD is a positive integer-valued function, we obtain that
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:
Associative Property: The GCD is an associative function:
Thus,
can be used to denote the GCD of multiple arguments.
Relation with LCM: is closely related to the least common multiple
: we have
Distributivity Versions: The following versions of distributivity hold true:
Prime Factorization: If we have the unique prime factorizations of and
, where
and
, then the GCD of
and
is:
Cartesian Coordinate System Interpretation: In a Cartesian coordinate system, can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points
and
.
Euclidean Algorithm in Base : For non-negative integers
and
, where
and
are not both zero, provable by considering the Euclidean algorithm in base
, it simply states that:
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:
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;
}
#define infinity while(1)
#define unreachable assert(false && "Unreachable");
PersistentSimpleSegmentTree - Tourist Implementation
Problems:
Windows Path
C:/Users/USER/AppData/Roaming/Code/User/snippets/cpp.json
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
Counting Paths
Test using Merge trick on trees
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
const string ALPHA = "abcdefghijklmnopqrstuvwxyz";
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; });
}
};
#define _ << ' ' <<
// usage:
cout << x _ y << endl;
// cout << x << ' ' << y << endl;
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]);
}
};
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;
}
clang-format -style='{IndentWidth: 4, ColumnLimit: 80}' -i A.cpp
do_
has_
can_
compute_
build_
make_
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
input: vector<int> data{3, 2, 4, 5, 1, 1, 5, 3};
query: st.query(0, 3).sum
answer: 0
Wrong Answer
See: CSES
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;
}
};
Change
PrefixSum() n(-1) {}
To
PrefixSum(): n(-1) {}
assert(0 <= left && left <= right && right <= n - 1 && "query");
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;
auto go = y_combinator([&](auto Go, int idx) -> int64 {
// Go(idx-1);
});
int ans = go(0);
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
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
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])
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.