Compile: g++ -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2 -fsanitize=address,undefined -std=c++17
My Programming Template
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define tm ((tl+tr)>>1)
#define INF (1<<62)
#define endl "\n"
#define mem(v,w) memset(v,w,sizeof(v))
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ub upper_bound
#define lb lower_bound
#define vi vector<int>
#define si stack<int>
#define vvi vector<vector<int>>
#define setbits(v) __builtin_popcount(v)
#define setbitsll(v) __builtin_popcountll(v)
#define nth_element(s,n) *(s.find_by_order(n-1))
#define count_smaller(s,n) s.order_of_key(n)
#define raffle_draw(l,r) uniform_int_distribution<int>(l,r)(prng)
#define log(...) cerr << __LINE__ << ": "; logger(#__VA_ARGS__,__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //pbds
template <class T,class U> bool chmin(T &x, U y){ if(x>y){ x=y; return true; } return false; }
template <class T,class U> bool chmax(T &x, U y){ if(x<y){ x=y; return true; } return false; }
mt19937 prng(chrono::steady_clock::now().time_since_epoch().count()); // mersenne twister
const long double pi = acos(-1.0);
const int mod = 1e9+7;
/* logging utitlies */
template<typename ...Args>
void logger(string vars, Args&&... values){
cerr << "[";
cerr << vars << "] = ";
string delimeter = "";
cerr << "[";
(..., (cerr << delimeter << values, delimeter=","));
cerr << "]\n";
}
/* i/o stream utilities */
ostream& operator <<(ostream& out, pair<int,int> const& v){
out << v.fi << "," << v.se;
return out;
}
template<typename T>
ostream& operator <<(ostream& out, const vector<T>& v){
for (const T& x: v) out << x << " ";
return out;
}
template<typename T, typename S>
ostream& operator <<(ostream& out, const map<T,S>& v){
for (auto& x: v) out << x.fi << "-->" << x.se;
return out;
}
template<typename T>
ostream& operator <<(ostream& out, const set<T>& v){
for (auto& x: v) cout << x << " ";
return out;
}
template<typename T>
ostream& operator <<(ostream& out, const multiset<T>& v){
for (auto& x: v) cout << x << " ";
return out;
}
/* adhoc utilities */
inline ll ceil_divide(ll a,ll b){ return (a+b-1)/b; }
template <class T>
void remove_duplicates(vector<T> &v){ sort(all(v)); v.erase(unique(all(v)),v.end());}
string to_binary(ll v){
if(!v) return "0";
string s="";
while (v>0){
s += static_cast<char>(v%2 + '0');
v/=2;
}
reverse(all(s));
return s;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}Stress Test PY Template
import filecmp
import os
import random
import sys
import subprocess
my_solution = sys.argv[1]
test_solution = sys.argv[2]
my_solution_exe = my_solution.split(".cpp")[0]
test_solution_exe = test_solution.split(".cpp")[0]
input_file = "in.txt"
my_solution_out = "out1.txt"
test_solution_out = "out2.txt"
def generate_input_file():
'''
Write code here to generate the input file
Tips:
1. Use random.randint(l,r) : to generate random number between l...r
2. Perm = list(range(1,n)) random.shuffle(Perm) : to generate a randome permutation
'''
def test_case(i):
generate_input_file()
os.system(f"./{my_solution_exe} < {input_file} > {my_solution_out}")
os.system(f"./{test_solution_exe} < {input_file} > {test_solution_out}")
with open(my_solution_out, "r") as f:
a = f.readline()
a.rstrip()
with open(test_solution_out, "r") as f:
b = f.readline()
b.rstrip()
if a == b:
print(f"Test {i} passed.")
else:
print("ERROR, match out1.txt and out2.txt.")
sys.exit(0)
def run_commands(cmd):
print(cmd)
try:
cmd = cmd.split(" ")
subprocess.run(cmd, check=True)
except subprocess.CalledProcessError as e:
print ("Error:", e)
def compile_command(cpp_file):
compilation_flags = "-Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2 -fsanitize=address,undefined -std=c++17"
exe_name = cpp_file.split(".cpp")[0]
return f"g++ {compilation_flags} {exe_name} {cpp_file}"
if __name__ == '__main__':
run_commands(compile_command(my_solution))
run_commands(compile_command(test_solution))
for i in range(1,10000):
test_case(i)
Combinatorics Template
inline int mul(int x,int y){ ll z = 1ll; z=z*x*y; z%=mod; return (int)z; }
inline int add(int x,int y){ ll z = 0ll; z=z+x+y; z%=mod; return (int)z; }
inline int sub(int x,int y){ ll z=0ll; z=x+mod-y; z%=mod; return (int)z; }
inline int binpow(int x,int y){
ll z = 1ll;
while(y){
if(y&1) z=mul(z,x);
x = mul(x,x);
y>>=1;
}
return (int)z;
}
inline int inv(int x){ return binpow(x,mod-2); }
const int N = 400004;
int fac[N], rfac[N];
void fasetup(){
fac[0] = rfac[0] = 1;
for(int i=1;i<N;i++) fac[i] = mul(fac[i-1],i);
rfac[N-1] = inv(fac[N-1]);
for(int i=N-2;i>0;i--) rfac[i] = mul(rfac[i+1], i+1);
}
int choose(int n,int r){
assert(n>=r);
return mul(fac[n], mul(rfac[r],rfac[n-r]));
}Number Theory Template
// Use Wheel factorization for large PMax
const int PMax = 1e5+5;
int lp[PMax];
void sieve(){
vector<int> prime;
for(int i=2;i<=PMax;i++){
if(!lp[i]){
lp[i]=i;
prime.eb(i);
}
for(int j=0;j<(int)sz(prime) && prime[j]<=lp[i] && i*prime[j]<=PMax;j++){
lp[i*prime[j]] = prime[j];
}
}
}
vector<int> factor(int num){
vector<int> f;
while(num!=1){
f.eb(lp[num]);
int tmp = lp[num];
while(num>0 && num % tmp==0) num /= tmp;
}
return f;
}
vector<int> divisors(int num,const vector<int> lp){
vector<int> d={1};
while(num>1){
int spf=lp[num];
int m=0;
while(num%spf==0) num/=spf,m++;
int dz = (int)sz(d);
int pw = spf;
for(int i=0;i<m;i++){
for(int k=0;k<dz;k++){
d.eb(d[k]*pw);
}
pw*=spf;
}
}
return d;
}Disjoint Set Template
// DSU with Rank Compression + Path Compression
int par[UFMAX],rnk[UFMAX];
int compsize[UFMAX];
int max_comp_size=0;
// SET UFMAX
void initdsu(int n){
for(int i=1;i<=n;i++){
par[i] = i;
rnk[i] = 1;
compsize[i]=1;
}
max_comp_size=0;
}
int root(int u){
if(par[u]==u) return u;
return par[u]=root(par[u]);
}
void unite(int u,int v){
int r1 = root(u), r2 = root(v);
if(r1==r2) return;
if(rnk[r1]>rnk[r2]){
par[r2] = r1;
compsize[r1]+=compsize[r2];
compsize[r2]=0;
chmax(max_comp_size,compsize[r1]);
}
else if(rnk[r1]<rnk[r2]){
par[r1] = r2;
compsize[r2]+=compsize[r1];
compsize[r1]=0;
chmax(max_comp_size,compsize[r2]);
}
else{
par[r2] = r1, rnk[r1]++;
compsize[r1]+=compsize[r2];
compsize[r2]=0;
chmax(max_comp_size,compsize[r1]);
}
}// DSU w/o Rank Compression and using randomized Union + Path Compression
const int MAXN = 1005;
int par[MAXN], members[MAXN];
void init(){
for (int i=1;i<=n;i++){
par[i] = i;
members[i] = 1;
}
}
int root(int u){
if(par[u]==u) return u;
return par[u] = root(par[u]);
}
void unite(int u,int v){
if(root(u)==root(v)) return;
if(rand()&1) swap(u,v);
members[root(v)] += members[root(u)];
par[root(u)] = v;
}Segment Tree Template
/* 1-based segment tree template */
// $set : infinite, ST_MAX, Node constructor, combine code
const int ST_MAX = <>;
int _array[ST_MAX];
const int infinite = <>;
struct Node{
// 0. add node variables and constructors
// int node_variables;
int val;
Node () {
val = infinite;
}
Node (int val) : val (val) {}
};
int _n; // $ set _n
class SegmentTree {
public:
Node *_t;
public:
SegmentTree (int n) {
_n = n;
_t = new Node[_n*6];
}
Node combine (Node lc, Node rc){
Node res;
/* 1. add your combine code along with empty node */
if (lc.val == infinite) return rc;
else if (rc.val == infinite) return lc;
int va = max (lc.val, rc.val);
return Node (va);
}
Node query (const int& l, const int& r, int v=1, int tl=1, int tr=_n){
if (r<tl||l>tr) return Node ();
if (tl>=l && tr<=r) return _t[v];
return combine (query(l, r, v<<1, tl, tm),
query(l, r, v<<1|1, tm+1, tr));
}
void build (int v=1, int tl=1, int tr=_n){
if (tl==tr) _t[v] = Node(_array[tl]);
else {
build (v<<1, tl, tm);
build (v<<1|1, tm+1, tr);
_t[v] = combine (_t[v<<1], _t[v<<1|1]);
}
}
// point update
void update (const int& pos, const int& val, int v=1, int tl=1, int tr=_n){
if (tl==tr) _t[v] = Node(val);
else {
if (pos <= tm) update (pos, val, v<<1, tl, tm);
else update (pos, val, v<<1|1, tm+1, tr);
_t[v] = combine (_t[v<<1], _t[v<<1|1]);
}
}
};
/* Segment Tree tested*/Trees and Graphs (27)
1. Cyclicity in undirected graph
2. Cyclicity in directed graph, coloring technique
3. All simple cycles in a undirected graph, w/o composite cycles
4. All tricks using union-find algorithm
5. Small to Large Trick, Merger Sets, a DSU trick
6. Tarjan's algorithm to find articulation points, bridges
7. Finding transitive closure of a graph using Floyd Warshall
8. BFS on complement graph aka Pie for a Pie trick
10. Kahn's algorithm for topological ordering
11. Maximal/Minimal Topological ordering
12. Floyd Warshall for finding shortest paths
13. Minimum Spanning Tree, Prim vs Kruskal
14. Dijkstra's shortest path algoritm for non-negative edges
15. Kth shortest path and ghostness in dikjstra's algorithm
16. Use Bellman Ford for negative edge weights
17. Detect negative cycle using Bellman Ford
18. Shortest Cycle in undirected graph using BFS
20. Strongly connected component aka SCC
21. Kosaraju's algorithm for condensed SCC
22. Finding centeroid a tree, subtree, cut tree
23. Euler Tour, relation between vertices, propagating tree
Mathematical Techniques (27)
12. Complexity of Euclid's dvision Lemma
13. Subsequence to Subarray Transformation Trick
14. Some properties of sum of absolute differences aka SAD
15. How to solve diophantine equations
16. Gaussian Elimination in GF(2), Max XOR Subsequence
17. Euclid extended division algorithm for LCM/GCD
19. Inclusion Exclusion Principle
20. Prime Factorization, Sieve, Divisors of Large numbers
23. Meet in the Middle aka MiTM
Greedy Techniques (16)
1. Minimum Increment Decrement to make array equal
2. Largest Area in a Histogram using NGE
3. Intermediate Value Property Trick
6. Find frequency of element in a given range using upperbound, lowerbound
7. All techniques using exchange arguments, powerful proving technique
8. Invariance and Extremal Ideas
9. Generic sliding window algorithm
10. Comparing a subarray with a sliding window technique
11. Find closest pair, minimum euclidean distance
12. Klee's algorithm for union of intersecting segments
Dynamic Programming (17)
1. Max Subarray Sum, Kadane's algorithm
3. All variants of buy-sell share problems
4. Bitmasking: Assigment Problem
5. Bitmasking: Held Karp for TSP like problem
8. Profile DP, DP on broken pipes
9. All tricks in digit DP problems, including LCM trick, pair of numbers
10. Divisibility problems using DP
11. Everything about IN-OUT dp on tree aka Rerooting technique, Tree Distances, Tree Matching
12. Inclusion and Exclusion DP
13. Solving any structural dp problems using kadane's approach
14. Subsequence & Substring comparison of two strings type problems
15. Everything about Sieve of Eratosthenes, Prime Factorization, Harmonic Lemma
16. Next Element Array technique used in various AND, OR, bitwise problems
Game Theory (6)
4. Converting games to NIM forms using MEX
Range Queries (15)
1. Binary Lifting, LCA of trees
2. Fenwick Tree, 1D, 2D, difference array trick
4. Segment Tree 1D, 2D, Lazy Propagation
7. Counting Inversions using Fenwick Tree
8. Order Statistics using Fenwick Tree
9. Classical Fenwick Tree application in DP, Coordinate Compression
10. Segment Tree, Bit manipulation and Lazy propagation
11. Get the nearest element from a given element in a range
12. Ordered Statistics using PBDS
13. Interesting RMQ problems from SPOJ
String Algorithms (8)
5. KMP function, Z algorithm, periodicity of strings
6. Polynomial Hashing aka Rolling Hash
7. Rabin Karp, Lexicographically minimal shift, double hashing
Miscellaneous Stuff (10)
1. K-Majority Voting algorithm aka Boyer-Moore
2. Some useful bit hacks, bitsets
3. Bitset Magic and DP optimizations
4. Minimum, Maximum XOR values of pair of numbers
6. Ternary Search for unimodal data
7. Some non-trivial tricks used in DP and Graphs
8. Some variants of Knapsack problem