<|start_filename|>dynamic_programming/non_classical/codeforces/F1353F/Solution.cpp<|end_filename|>
// problem name: Decreasing Heights
// problem link: https://codeforces.com/contest/1353/problem/F
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: brute force
// difficulty_level: medium

// solution idea:
// observation-01: for any value greater than a[0][0], can not be used at a[0][0]
//                 (cause, only decrease operation is allowed)
// observation-02: if we find the minimum cost for x = a[0][0], then we may say that
//                 the path for the solution is as following:
//                 x, x + r_1, x + r_2, ...., x + r_k-1[note: k = n*m, i.e. (0..k-1) has n*m elements]
//                 now, we may say that, x + r_z >= x + z(where, z = 1...k-1)
//                 simply we want to say that, if a[i][j](0-based indexing) is in the solution,
//                 then, a[i][j] >= x + (i+j)[note: x + (i+j) is the value that should be found at
//                 index i, j if we set x as the base]
// observation-03: now, if we want to find a solution for y, where y < x, and the path that
//                 has given mincost for x would be like:
//                 y, y + r_1, y + r_2, ...., y + r_k-1
//                 and the cost would be (x - y) * k i.e. (x - y) * n  *m
//                 so, y should give us a good answer using the path those x used, so we don't need
//                 to see them again,
//                 but
//                 as y < x, y of course open up some new paths, those for x was not opened, cause
//                 a[i][j] >= x + (i+j) has to be satisfied
//                 and now, a[i][j] >= y + (i+j) has to be satisfied, where y < x
//                 now, as those a[i][j] does not satisfied a[i][j] >=  x + (i+j), but
//                 satsfied but satisfied a[i][j] >= y + (i+j) will open up new paths and try to find
//                 new mincost
// observation-04: the previous observation clearly states that we've to open up new paths to find the
//                 new mincost. So, rather than opening up new paths in a decreasing order i.e. at first x
//                 then y then y-p(p > 0)...etc..., we can just bruteforce for each a[i][j], take
//                 a[i][j] - (i+j) as base and find the mincost, cause a[i][j] - (i+j) will sure openup
//                 a[i][j].


#include <bits/stdc++.h>

using namespace std;

#define N 128

const long long inf = (long long)1e18;

long long a[N][N];
long long c[N][N];

int n, m;

long long getCost(long long base) {
	// initialize 0, 0
	c[0][0] = a[0][0] - base;
	// for first column
	for(int i=1; i<n; i++) {
		if(a[i][0] >= base + i) {
			c[i][0] = c[i-1][0] + a[i][0] - (base + i);
		} else {
			c[i][0] = inf;
		}
	}
	// for first row
	for(int i=1; i<m; i++) {
		if(a[0][i] >= base + i) {
			c[0][i] = c[0][i-1] + a[0][i] - (base + i);
		} else {
			c[0][i] = inf;
		}
	}
	// for row = (1...n-1)
	//   for col = (1...m-1)
	for(int i=1; i<n; i++) {
		for(int j=1; j<m; j++) {
			if(a[i][j] >= base + i + j) {
				c[i][j] = min(c[i-1][j], c[i][j-1]) + a[i][j] - (base + i + j);
			} else {
				c[i][j] = inf;
			}
		}
	}
	return c[n-1][m-1];
}

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		scanf("%d %d", &n, &m);
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				scanf("%lld", &a[i][j]);
			}
		}
		long long minCost = inf;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				long long base = a[i][j] - (i + j);
				// check if possible base if greater than a[0][0]
				// in that case, it's not possible to reach the last element of matrix
				// cause, only decrease height operation is
				//        possible(according to problem statement)
				if(a[0][0] < base) continue;
				long long cost = getCost(base);
				minCost = min(minCost, cost);
			}
		}
		assert(minCost != inf);
		printf("%lld\n", minCost);
	}
	return 0;
}


<|start_filename|>greedy/basic/codeforces/F1362D/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: https://codeforces.com/contest/1362/problem/D
// contest link: https://codeforces.com/contest/1362
// time: (?)
// author: reyad

// other_tags: graph, constructive algorithm, implementation, sorting
// difficulty_level: medium

// very bad problem statement

// in summary:
// let, blogs be nodes
// let, topics be colors
// let, references be edges
// the problem requires us to find a sequence of n nodes in the graph
// those satisfies the following conditions:
// (1) no two graph node has same color if they
//     have an edge between them
// (2) if a graph node x has neighbors where their colors
//     from a set S, and the all colors are of set
//     T(of course S is subset of T), then the color
//     of node x will be min({color | color is from set {T - S}})
// also, notice that, the problem tells us to when we visit the first node
// does not have any neighbors(cause, the neighbours have not visited yet, i.e.)
// they have been assigned with any color

// solution idea:
// the problems is greedy itself, requires/forces us to construct the node
// with the less color(means smaller integer value) first
// when construcing the sequence, we just need to check two things
// let the current node be x
// (1) colors of neighbours x != color of x
// (2) colors of neighbours x covers all color
//     less than x

#include <bits/stdc++.h>

using namespace std;

#define N 500050

vector<int> t;
vector<int> idx;
vector<int> adj[N];
vector<int> seq;

bool cmp(int i, int j) {
	return t[i] < t[j];
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u-1].push_back(v-1);
		adj[v-1].push_back(u-1);
	}
	for(int i=0; i<n; i++) {
		int topic;
		scanf("%d", &topic);
		t.push_back(topic);
		idx.push_back(i);
	}
	sort(idx.begin(), idx.end(), cmp);
	bool flag = true;
	set<int> unq;
	vector<int> seen(n, 0);
	for(int i=0; i<n; i++) {
		int u = idx[i];
		seen[u] = 1;
		set<int> vtop;
		for(int v: adj[u]) {
			if(seen[v]) {
				if(t[v] == t[u]) {
					flag = false;
					break;
				}
				vtop.insert(t[v]);
			}
		}
		if(vtop.size() != unq.size()) {
			flag = false;
		}
		if(!flag) {
			break;
		}
		if((i+1) < n && t[idx[i]] != t[idx[i+1]]) {
			unq.insert(t[u]);
		}
		seq.push_back(u+1); // cause we subtracted 1 when taking input
	}
	if(!flag) {
		printf("-1\n");
	} else {
		for(int i=0; i<n; i++) {
			printf("%d ", seq[i]);
		}
		printf("\n");
	}
	return 0;
}

<|start_filename|>hashing/string_hashing/codeforces/F126B/Solution.cpp<|end_filename|>
// problem name: Password
// problem link: https://codeforces.com/contest/126/problem/B
// contest link: https://codeforces.com/contest/126
// time: (?)
// author: reyad

// other_tags: binary search, dp, string suffix structures, substring searching
// difficulty_level: medium


// solution idea:
// let's assume k is the smallest length for
// which s[0...k-1] = s[n-k...n-1]
// let's denote this string as m_1(smallest string that both temporary buddies PREFIX and SUFFIX)
// so, we may say that, if there is a longer substring than m_1, let's denote as m_2
// then, m_2 must satisfy one of two forms written below:
// (form-01) m_2 = m_1 + m_1
// (form-02) m_2 = m_1 + some characters + m_1
// (cause, m_1 is the string that always has to be the suffix and prefix
//  as m_1 found both in prefix of 's[]' and suffix of 's[]')
// Now, if we think about m_3, then m_3 should follow the rules for m_2.
// i.e.: (form-01) m_3 = m_2 + m_2
//       (form-02) m_3 = m_2 + some characters + m_2
// so, that tells us: if a string contains m_3, then it must contain m_2 and of course m_1
// or, generally: if a string contains m_r, then it must contain m_(r-1), m_(r-2)...
// Now, if we somehow found out matching strings we can use binary search to determine to go which
// direction to find the maximum length

// implementation idea:
// To solve the problems of matching strings, we could use hashing, as hashing gives O(1) time
// to match two strings
// we would maintain two hashes, one from start and the other from end of 's[]'
// if hash matches, then we've found a match
// we'd be sucessively get m_1, m_2, ..., m_r
// then, we may use binary search based on length of matched strings and hashes to determine
// if 's[]' contains a substring or not
// for each selection of substring m_x we've to check inside 's[]' using a window of length
// so, the total complexity would be O(n * log(n))

#include <bits/stdc++.h>

using namespace std;

#define N 1000010

char s[N];
int n, l[N], mc = 0;
long long int m[N];
const long long int p = 47;

bool contains(long long int hs, int w) {
	long long int h = 0, eh = 0, pwm = 1;
	for(int i=0; i<w; i++) pwm = pwm * p;
	for(int i=1; i<n-1; i++) {
		h = h * p + (s[i] - 'a' + 1);
		if(i >= w+1) eh = eh * p + (s[i-w] - 'a' + 1) * pwm;
		if(i >= w && (eh + hs) == h) return true;
	}
	return false;
}

int main() {
	scanf("%s", s);
	n = strlen(s);
	long long int h = 0, rh = 0, pw = 1;
	for(int i=0, j=n-1; j>0; j--, i++) {
		h = h * p + (s[i] - 'a' + 1);
		rh = rh + (s[j] - 'a' + 1) * pw;
		pw *= p;
		if(h == rh) {
			m[mc] = h;
			l[mc++] = i+1;
		}
	}
	int start = 0, end = mc-1, x = -1;
	while(start <= end) {
		int mid = (start + end) / 2;
		if(contains(m[mid], l[mid])) {
			x = mid;
			start = mid + 1;
		} else {
			end = mid - 1;
		}
	}
	if(x == -1) printf("Just a legend\n");
	else {
		s[l[x]] = '\0';
		printf("%s\n", s);
	}
	return 0;
}

<|start_filename|>math/combinatorics/codeforces/F1475C/Solution.cpp<|end_filename|>
// problem name: Ball in Berland
// problem link: https://codeforces.com/contest/1475/problem/C
// contest link: https://codeforces.com/contest/1475/
// time: (?)
// author: reyad


// other_tags: graph, inclusion exclusion principle
// difficulty_level: beginner


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

#define N 200020

int aa[N], bb[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int a, b, k;
        map<int, int> boy;
        map<int, int> girl;
        cin >> a >> b >> k;
        for(int i=0; i<k; i++) {
            cin >> aa[i];
            boy[aa[i]]++;
        }
        for(int i=0; i<k; i++) {
            cin >> bb[i];
            girl[bb[i]]++;
        }
        long long ans = 0;
        for(int i=0; i<k; i++) {
            long long t = k - (boy[aa[i]] + girl[bb[i]] - 1);
            ans += t;
        }
        cout << (ans / 2) << "\n";
    }
    return 0;
}


<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1512D/Solution.cpp<|end_filename|>
// problem name: Corrupted Array
// problem link: https://codeforces.com/contest/1512/problem/D
// contest link: https://codeforces.com/contest/1512
// time: (?)
// author: reyad


// other_tags: data structure, greedy
// difficulty_level: beginner


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

#define N 200020


int lx[N], rx[N];
int b[N];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n;
        cin >> n;
        int m = n + 2;
        for(int i=0; i<m; i++) {
            cin >> b[i];
        }
        lx[0] = 0; rx[m-1] = m-1;
        long long sum = b[0];
        for(int i=1; i<m; i++) {
            lx[i] = lx[i-1];
            if(b[i] > b[lx[i]]) {
                lx[i] = i;
            }
            int j = m-i-1;
            rx[j] = rx[j+1];
            if(b[j] > b[rx[j]]) {
                rx[j] = j;
            }
            sum = sum + b[i];
        }
        int hasAns = 0;
        int n1 = -1, n2 = -1;
        for(int i=0; i<m; i++) {
            int mxi = ((i > 0) ? lx[i-1] : -1);
            if((mxi == -1) || ((i < m-1) && (b[rx[i+1]] > b[mxi]))) {
                mxi = rx[i+1];
            }
            assert(mxi != -1);
            if((long long)b[mxi] + b[mxi] == (sum - b[i])) {
                hasAns = 1;
                n1 = i; n2 = mxi;
                break;
            }
        }
        if(hasAns) {
            for(int i=0; i<m; i++) {
                if(i != n1 && i != n2) {
                    printf("%d ", b[i]);
                }
            }
        } else {
            printf("-1");
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>math/number_theory/codeforces/F1350C/Solution.cpp<|end_filename|>
// problem name: Orac and LCM
// problem link: https://codeforces.com/contest/1350/problem/C
// contest link: https://codeforces.com/contest/1350
// time: (?)
// author: reyad

// other_tags: (?)
// difficulty_level: medium


// solution hint:  gcd(lcm(u, v_1), lcm(u, v_2), ..., lcm(u, v_n)) = lcm(u, gcd(v_1, v_2, ..., v_n))


#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b) {
	while(b != 0) {
		long long c = a % b;
		a = b;
		b = c;
	}
	return a;
}

long long lcm(long long a, long long b) {
	return (long long)a * b / gcd(a, b);
}

int main() {
	int n;
	scanf("%d", &n);
	long long v = 0;
	long long gp = 0;
	for(int i=0; i<n; i++) {
		int u;
		scanf("%d", &u);
		gp = gcd(gp, lcm(u, v));
		v = gcd(u, v);
	}
	printf("%lld\n", gp);
	return 0;
}


<|start_filename|>ad_hoc/implementation/codeforces/F1362A/Solution.cpp<|end_filename|>
// problem name: Johnny and Ancient Computer
// problem link: https://codeforces.com/contest/1362/problem/A
// contest link: https://codeforces.com/contest/1362
// time: (?)
// author: reyad

// other_tags: (?)
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		long long a, b;
		scanf("%lld %lld", &a, &b);
		if(a == b) {
			printf("0\n");
		}
		else if(a < b) {
			int op = 0;
			while((a << 3LL) <= b) {
				a = (a << 3LL);
				op++;
			}
			while((a << 2LL) <= b) {
				a = (a << 2LL);
				op++;
			}
			while((a << 1LL) <= b) {
				a = (a << 1LL);
				op++;
			}
			if(a == b) {
				printf("%d\n", op);
			} else {
				printf("%d\n", -1);
			}
		} else {
			int op = 0;
			while((a&(0x7)) == 0 && (a >> 3LL) >= b) {
				a = (a >> 3LL);
				op++;
			}
			while((a&(0x3)) == 0 && (a >> 2LL) >= b) {
				a = (a >> 2LL);
				op++;
			}
			while((a&(0x1)) == 0 && (a >> 1LL) >= b) {
				a = (a >> 1LL);
				op++;
			}
			if(a == b) {
				printf("%d\n", op);
			} else {
				printf("-1\n");
			}
		}
	}
	return 0;
}

<|start_filename|>string/basic/loj/F1114/Solution.cpp<|end_filename|>
// problem name: Easily Readable
// problem link: http://lightoj.com/volume_showproblem.php?problem=1114
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: sorting, binary search, binary search tree
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


char word[10004];
char sent[10004];

map<string, int> mp;


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        mp.clear();
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%s", word);
            string w(word);
            int l = w.length();
            if(l > 3) {
                sort(w.begin()+1, w.begin()+l-1);
            }
            mp[w]++;
        }
        int m;
        scanf("%d", &m);
        printf("Case %d:\n", cc+1);
        for(int i=0; i<m; i++) {
            char ch;
            scanf("%c", &ch);
            scanf("%[^\n]", sent);
            int ans = 1;
            istringstream s(sent);
            string w;
            while(s >> w) {
                int l = w.length();
                if(l > 3) {
                    sort(w.begin()+1, w.begin()+l-1);
                }
                ans = ans * mp[w];
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

<|start_filename|>game/basic/codeforces/F1363C/Solution.cpp<|end_filename|>
// problem name: Game On Leaves
// problem link: https://codeforces.com/contest/1363/problem/C
// contest link: https://codeforces.com/contest/1363
// time: (?)
// author: reyad


// other_tags: trees
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

#define N 1024

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, x;
		scanf("%d %d", &n, &x);
		int dx = 0;
		for(int i=1; i<n; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			if(u == x || v == x) {
				dx++;
			}
		}
		if(dx <= 1) {
			printf("Ayush\n");
		} else {
			if(n&1) {
				printf("Ashish\n");
			} else {
				printf("Ayush\n");
			}
		}
	}
	return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1506E/Solution.cpp<|end_filename|>
// problem name: Restoring the Permutation
// problem link: https://codeforces.com/contest/1506/problem/E
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: implementation
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;


int mn[200020];
int mx[200020];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        priority_queue<int> mnpq;
        priority_queue<int> mxpq;
        int prev = 0;
        for(int i=0; i<n; i++) {
            int q;
            scanf("%d", &q);
            if(q == prev) {
                mn[i] = -1 * mnpq.top();
                mnpq.pop();
                mx[i] = mxpq.top();
                mxpq.pop();
            } else {
                for(int j=prev+1; j<q; j++) {
                    mnpq.push(-1 * j);
                    mxpq.push(j);
                }
                mn[i] = mx[i] = q;
            }
            prev = q;
        }
        for(int i=0; i<n; i++) {
            printf("%d ", mn[i]);
        }
        printf("\n");
        for(int i=0; i<n; i++) {
            printf("%d ", mx[i]);
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>greedy/basic/codeforces/F1362C/Solution.cpp<|end_filename|>
// problem name: Johnny and Another Rating Drop
// problem link: https://codeforces.com/contest/1362/problem/C
// contest link: https://codeforces.com/contest/1362
// time: (?)
// author: reyad

// other_tags: bitmask, math
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		long long n;
		scanf("%lld", &n);
		long long bit = 62;
		long long unfairness = 0;
		while(bit >= 0) {
			if(n >= (1LL << bit)) {
				n = n - (1LL << bit);
				unfairness = unfairness + (2LL << bit) - 1LL;
			}
			bit--;
		}
		printf("%lld\n", unfairness);
	}
	return 0;
}

<|start_filename|>graph/dfs/loj/F1108/Solution.cpp<|end_filename|>
// problem name: Instant View of Big Bang
// problem link: http://lightoj.com/volume_showproblem.php?problem=1108
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: data structure
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


vector<pair<int, int>> g[1024];
vector<int> rg[1024];
map<int, int> instack;
int seen[1024];
int stck[1024];
int top;
int marked[1024];


void dfs(int u, int cost) {
    if(seen[u]) {
        if(instack.count(u)) {
            if(cost - instack[u] < 0) {
                stck[top++] = u;
            }
        }
        return;
    }
    seen[u] = true;
    instack[u] = cost;
    for(auto e: g[u]) {
        dfs(e.first, cost + e.second);
    }
    instack.erase(u);
}


void mark(int u) {
    marked[u] = true;
    for(int v: rg[u]) {
        if(!marked[v]) {
            mark(v);
        }
    }
}


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; i++) {
            g[i].clear();
            rg[i].clear();
            marked[i] = 0;
        }
        for(int i=0; i<m; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            g[u].push_back(make_pair(v, w));
            rg[v].push_back(u);
        }
        for(int i=0; i<n; i++) {
            if(!marked[i]) {
                top = 0;
                memset(seen, 0, sizeof(seen));
                dfs(i, 0);
                for(int j=0; j<top; j++) {
                    if(!marked[stck[j]]) {
                        mark(stck[j]);
                    }
                }
            }
        }
        printf("Case %d:", cc+1);
        int c = 0;
        for(int i=0; i<n; i++) {
            if(marked[i]) {
                printf(" %d", i);
                c++;
            }
        }
        if(c == 0) {
            printf(" impossible");
        }
        printf("\n");
    }
    return 0;
}

<|start_filename|>math/basic/codeforces/F1353C/Solution.cpp<|end_filename|>
// problem name: Board Moves
// problem link: https://codeforces.com/contest/1353/problem/C
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: (?)
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

#define N 500000

long long a[N+10];

int main() {
	a[1] = 0LL;
	long long sq = 1LL;
	for(int i=3, j=1; i<=N; j++, i+=2) {
		a[i] = a[i-2] + (j * ((1LL * i * i) - sq));
		sq = 1LL * i * i;
	}
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		printf("%lld\n", a[n]);
	}
	return 0;
}

<|start_filename|>greedy/basic/codeforces/F1353E/Solution.cpp<|end_filename|>
// problem name: K-periodic Garland
// problem link: https://codeforces.com/contest/1353/problem/E
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: brute force, dp
// difficulty_level: easy


// solution hint:
// >> first count no of all '1's
// >> let's consider a start point u
// >> then, we've to check [u, u+k, u+2k, ..., u+rk]...(i)
// >> let, diff = 0, which increases if '0' found in u+x
//    and cecreases if '1' found in u+x
// >> so, if diff > 0, it means we've to turn more light on than turn off
// >> and, when that happens we would just decide to turn off rather
//    than turning on and set diff to 0


#include <bits/stdc++.h>

using namespace std;

#define N 1000100

char s[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		scanf("%d %d %s", &n, &k, s);
		int one = 0;
		for(int i=0; i<n; i++) {
			if(s[i] == '1') {
				one++;
			}
		}
		int mn = 987654321;
		for(int i=0; i<k; i++) {
			int diff = 0;
			for(int j=i; j<n; j+=k) {
				if(s[j] == '0') diff++;
				else diff--;
				if(diff > 0) diff = 0;
				mn = min(mn, one + diff);
			}
		}
		printf("%d\n", mn);
	}
	return 0;
}

<|start_filename|>dynamic_programming/lcs/loj/F1110/Solution.cpp<|end_filename|>
// problem name: An Easy LCS
// problem link: http://lightoj.com/volume_showproblem.php?problem=1110
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

string dp[128][128];
char a[128];
char b[128];

void lcs(int i, int j) {
    if(dp[i][j].length() > 0) {
        return;
    }
    if(a[i] == '\0' || b[j] == '\0') {
        return;
    }
    if(a[i] == b[j]) {
        lcs(i+1, j+1);
        dp[i][j] = a[i] + dp[i+1][j+1];
    } else {
        lcs(i+1, j);
        lcs(i, j+1);
        if(dp[i+1][j].length() == dp[i][j+1].length()) {
            dp[i][j] = (dp[i+1][j].compare(dp[i][j+1]) < 0) ? dp[i+1][j] : dp[i][j+1];
        } else {
            dp[i][j] = (dp[i+1][j].length() > dp[i][j+1].length()) ? dp[i+1][j] : dp[i][j+1];
        }
    }
}


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        for(int i=0; i<104; i++) {
            for(int j=0; j<104; j++) {
                dp[i][j].clear();
            }
        }
        scanf("%s", a);
        scanf("%s", b);
        lcs(0, 0);
        if(dp[0][0].length() == 0) {
            dp[0][0] = ":(";
        }
        printf("Case %d: %s\n", cc+1, dp[0][0].c_str());
    }
    return 0;
}


<|start_filename|>hashing/string_hashing/codeforces/F727E/Solution.cpp<|end_filename|>
// problem name: Games on a CD
// problem link: https://codeforces.com/contest/727/problem/E
// contest link: https://codeforces.com/contest/727(Technocup 2017 - Elimination Round 1 (Unofficially Open for Everyone, Rated for Div. 2))
// time: (?)
// author: reyad

// other_tags: data structures, string suffix structures, strings
// difficulty_level: expert

// note: this problem's solution is very easy.
// but solving it with hash is a pain
// i had to use two hashes to avoid hash collision
// while implmenting hash make sure you choose base and mod very carefully


#include <bits/stdc++.h>

using namespace std;

#define N 1000100
#define M 1000000007
#define M2 1000000009

int n, k, gn, ans[N / 10], acnt = 0;
pair<int, int> s[N+N];
bool seen[N / 10];
char cd[N+N], g[N / 10];
map<pair<int, int>, int> gmp;


int main() {
	scanf("%d %d", &n, &k);
	scanf("%s", cd);

	int l = n * k;
	for(int i=0; i<l; i++) cd[l+i] = cd[i];
	l += l;
	long long int h = 0, h2 = 0, pwm = 1, pwm2 = 1, p = 647, p2 = 2797;
	for(int i=0; i<k; i++) {
		pwm = (pwm * p) % M;
		pwm2 = (pwm2 * p2) % M2;
	}
	for(int i=0; i<l; i++) {
		h = (h * p + (cd[i] - 'a' + 1)) % M;
		h2 = (h2 * p2 + (cd[i] - 'a' + 1)) % M2;
		if(i >= k) {
			h = (h - (((cd[i-k] - 'a' + 1) * pwm) % M) + M) % M;
			h2 = (h2 - (((cd[i-k] - 'a' + 1) * pwm2) % M2) + M2) % M2;
		}
		if(i >= k-1) s[i-k+1] = make_pair(h, h2);
	}

	scanf("%d", &gn);
	for(int i=0; i<gn; i++) {
		scanf("%s", g);
		long long int hs = 0, hs2 = 0;
		for(int j=0; j<k; j++) {
			hs = (hs * p + (g[j] - 'a' + 1)) % M;
			hs2 = (hs2 * p2 + (g[j] - 'a' + 1)) % M2;
		}
		gmp[make_pair(hs, hs2)] = i;
	}

	assert(gmp.size() == gn);
	
	for(int i=0; i<gn; i++) seen[i] = false;
	for(int i=0; i<k; i++) {
		acnt = 0;
		for(int j=i, r=0; r<n; r++, j+=k) {
			if(gmp.count(s[j])) {
				int idx = gmp[s[j]];
				if(seen[idx]) break;
				ans[acnt++] = idx;
				seen[idx] = true;
			}
			else break;
		}
		if(acnt == n) break;
		for(int j=0; j<acnt; j++) seen[ans[j]] = false;
	}
	if(acnt == n) {
		printf("YES\n");
		for(int i=0; i<acnt; i++) printf("%d ", ans[i] + 1);
		printf("\n");
	}
	else printf("NO\n");
	return 0;
}


<|start_filename|>brute_force/loop/codeforces/F1362B/Solution.cpp<|end_filename|>
// problem name: Johnny and His Hobbies
// problem link: https://codeforces.com/contest/1362/problem/B
// contest link: https://codeforces.com/contest/1362
// time: (?)
// author: reyad

// other_tags: bitmask
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

#define N 2048

int a[N];
int c[N];
int d[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		memset(c, 0, sizeof(int) * 1032);
		int n;
		scanf("%d", &n);
		for(int i=0; i<n; i++) {
			scanf("%d", &a[i]);
			c[a[i]]++;
		}
		int ans = -1;
		for(int k=1; k<=1024; k++) {
			bool flag = true;
			memset(d, 0, sizeof(int) * 1032);
			for(int i=0; i<n; i++) {
				d[(a[i] ^ k)]++;
			}
			for(int i=0; i<1024; i++) {
				if(c[i] != d[i]) {
					flag = false;
					break;
				}
			}
			if(flag) {
				ans = k;
				break;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

<|start_filename|>dynamic_programming/tsp/loj/F1119/Solution.cpp<|end_filename|>
// problem name: Pimp My Ride 
// problem link: http://lightoj.com/volume_showproblem.php?problem=1119
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


#define N 16

const long long INF = 12345678911LL;

long long dist[N][N];
long long dp[N][(1<<N)];

long long run(int u, int mask, int n) {
    if(dp[u][mask] != -1) {
        return dp[u][mask];
    }
    dp[u][mask] = INF;
    long long tcost = 0;
    for(int v=0; v<n; v++) {
        if(!(mask & (1<<v))) {
            dp[u][mask] = min(dp[u][mask], run(v, mask | (1<<v), n));
        } else {
            tcost = tcost + dist[u][v];
        }
    }
    if(dp[u][mask] == INF) {
        dp[u][mask] = 0;
    }
    dp[u][mask] = dp[u][mask] + tcost;
    return dp[u][mask];
}


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                scanf("%lld", &dist[i][j]);
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<(1<<n); j++) {
                dp[i][j] = -1;
            }
        }
        long long cost = INF;
        for(int i=0; i<n; i++) {
            long long t = run(i, 0, n);
            cost = min(cost, t);
        }
        printf("Case %d: %lld\n", cc+1, cost);
    }
    return 0;
}


<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1504A/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: https://codeforces.com/contest/1504/problem/A
// contest link: https://codeforces.com/contest/1504
// time: (?)
// author: reyad


// other_tags: string
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

char s[300030];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        scanf("%s", s);
        int l = strlen(s);
        int ac = 0;
        for(int i=0; i<l; i++) {
            if(s[i] == 'a') {
                ac++;
            }
        }
        if(ac == l) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for(int i=0; i<l; i++) {
            if(s[i] == s[l-i-1]) {
                if(s[i] != 'a') {
                    printf("%c", 'a');
                    printf("%s\n", s+i);
                    break;
                }
            } else {
                printf("%c", s[i]);
                s[i] = 'a';
                printf("%s\n", s+i);
                break;
            }
            printf("%c", s[i]);
        }
    }
    return 0;
}


<|start_filename|>math/number_theory/codeforces/F1475A/Solution.cpp<|end_filename|>
// problem name: Odd Divisor
// problem link: https://codeforces.com/contest/1475/problem/A
// contest link: https://codeforces.com/contest/1475/
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: beginner



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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        long long n;
        cin >> n;
        while(n>1 && !(n&1)) {
            n /= 2;
        }
        if(n == 1) {
            cout << "NO" << "\n";
        } else {
            cout << "YES" << "\n";
        }
    }
    return 0;
}


<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1504D/Solution.cpp<|end_filename|>
// problem name: 3-Coloring
// problem link: https://codeforces.com/contest/1504/problem/D
// contest link: https://codeforces.com/contest/1504
// time: (?)
// author: reyad


// other_tags: game, interactive, graph
// difficulty_level: beginner


// solution idea:
// with two colors we can create a pattern as
// follows so that no neighboring cell share
// same colors
// x y x y x
// y x y x y
// x y x y x
// y x y x y
// x y x y x
// so, as we're given the choice to select from
// one of two colors(as alice blocks the other color)
// we can always between either x or y
// so, what we'll do first is
// either complete all the cells of x
// or, complete all the cells of y
// one of the x or y must complete prior to other
// let's assume x is completed first
// and for the one which is not complete, we can select
// between one of (y and z), cause alice can't force us
// to select a single color x in anyway.
// so, the solved graph may look(considering x is completed first)
// x y x y x
// y x y x y
// x z x y x
// y x z x z
// x z x y x


#include <bits/stdc++.h>

using namespace std;


pair<int, int> x[10010];
pair<int, int> y[10010];

int main() {
    int n;
    scanf("%d", &n);
    int xc = 0, yc = 0;
    for(int i=0; i<n; i++) {
        if(!(i&1)) {
            for(int j=0; j<n; j++) {
                if(!(j&1)) {
                    x[xc++]= {i+1, j+1};
                } else {
                    y[yc++] = {i+1, j+1};
                }
            }
        } else {
            for(int j=0; j<n; j++) {
                if(!(j&1)) {
                    y[yc++] = {i+1, j+1};
                } else {
                    x[xc++]= {i+1, j+1};
                }
            }
        }
    }
    int m = n * n;
    int _xc = 0, _yc = 0;
    for(int i=0; i<m; i++) {
        int a;
        scanf("%d", &a);
        if(_xc < xc && _yc < yc) {
            if(a == 1) {
                printf("%d %d %d\n", 2, y[_yc].first, y[_yc].second);
                ++_yc;
                fflush(stdout);
            } else {
                printf("%d %d %d\n", 1, x[_xc].first, x[_xc].second);
                ++_xc;
                fflush(stdout);
            }
        } else {
            if(_xc < xc) {
                int choose = (a == 1) ? 3 : 1;
                printf("%d %d %d\n", choose, x[_xc].first, x[_xc].second);
                ++_xc;
                fflush(stdout);
            }
            if(_yc < yc) {
                int choose = (a == 2) ? 3 : 2;
                printf("%d %d %d\n", choose, y[_yc].first, y[_yc].second);
                ++_yc;
                fflush(stdout);
            }
        }
    }
    return 0;
}


<|start_filename|>greedy/basic/codeforces/F1353B/Solution.cpp<|end_filename|>
// problem name: Two Arrays And Swaps
// problem link: https://codeforces.com/contest/1353/problem/B
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: sortings
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

#define N 32

int a[N], b[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		scanf("%d %d", &n, &k);
		for(int i=0; i<n; i++) {
			scanf("%d", &a[i]);
		}
		for(int i=0; i<n; i++) {
			scanf("%d", &b[i]);
		}
		sort(a, a+n);
		sort(b, b+n);
		int i = n-1, j = n-1, h = 0, cnt = 0;
		long long sum = 0;
		while(cnt < n && h < k) {
			if(a[i] >= b[j]) {
				sum = sum + a[i];
				i--;
			}
			else {
				sum = sum + b[j];
				j--;
				h++;
			}
			cnt++;
		}
		while(i >= 0 && cnt < n) {
			sum = sum + a[i];
			i--;
			cnt++;
		}
		printf("%lld\n", sum);
	}
	return 0;
}

<|start_filename|>search/binary_search/codeforces/F1490E/Solution.cpp<|end_filename|>
// problem name: Accidental Victory
// problem link: https://codeforces.com/contest/1490/problem/E
// contest link: https://codeforces.com/contest/1490
// author: reyad
// time: (?)


// other_tags: greedy, implementation
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

#define N 200020

int a[N], x[N], b[N];

bool cmp(int i, int j) {
    return a[i] < a[j];
}

bool does_satisfy(int s, int n) {
    long long int sum = 0;
    for(int i=0; i<=s; i++) {
        sum = sum + a[x[i]];
    }
    for(int i=s+1; i<n; i++) {
        if(sum < a[x[i]]) {
            return false;
        }
        sum = sum + a[x[i]];
    }
    return true;
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d", &a[i]);
            x[i] = i;
        }
        sort(x, x+n, cmp);
        int s = 0, e = n-1, p = -1;
        while(s <= e) {
            int m = (s + e) / 2;
            if(does_satisfy(m, n)) {
                p = m;
                e = m - 1;
            } else {
                s = m + 1;
            }
        }
        assert(p != -1);
        int bc = 0;
        for(int i=p; i<n; i++) {
            b[bc++] = x[i];
        }
        sort(b, b+bc);
        printf("%d\n", bc);
        for(int i=0; i<bc; i++) {
            printf("%d ", b[i] + 1); // cause, 1 based indexing of codeforces
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>string/hashing/codeforces/F271D/Solution.cpp<|end_filename|>
// problem name: Good Substrings
// problem link: https://codeforces.com/contest/271/problem/D
// contest link: https://codeforces.com/contest/271
// time: (?)
// author: reyad

// other_tags: data structures
// difficulty_level: medium

// the problem can be solved in multiple ways
// hashing is an intelligent technique, but can be hacked easily
// while using polynomial hashing, choose your base and mod value carefully


#include <bits/stdc++.h>

using namespace std;

#define N 1520
#define MOD 1000000007

int main() {
	char s[N], gb[32];
	int k, bc = 0;
	long long int b[N * N];

	scanf("%s %s %d", s, gb, &k);
	
	int l = strlen(s);
	for(int i=0; i<l; i++) {
		int badCnt = 0, p = 47;
		long long int h = 0;
		for(int j=i; j<l; j++) {
			if(gb[s[j] - 'a'] == '0') badCnt++;
			if(badCnt > k) break;
			h = h * p + (s[j] - 'a' + 1);
			if(h >= MOD) h -= MOD;
			b[bc++] = h;
		}
	}

	sort(b, b + bc);
	int c = (bc) ? 1 : 0;
	for(int i=1; i<bc; i++) {
		if(b[i] == b[i-1]) continue;
		else c++;
	}
	printf("%d\n", c);
	
	return 0;
}

<|start_filename|>graph/lca/loj/F1101/Solution.cpp<|end_filename|>
// problem name: A Secret Mission
// problem link: http://lightoj.com/volume_showproblem.php?problem=1101
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: tree path queries, minimum spanning tree, dfs, data structures
// difficulty_level: expert


#include <bits/stdc++.h>

using namespace std;


#define N 50010
#define M 100010
#define K 20


struct E {
    int x, y, w;
    E(){}
};

bool cmp(const E &e1, const E &e2) {
    return e1.w < e2.w;
}


E e[M];
int p[2 * N];
vector<int> mst[2 * N];
map<int, int> wc;
int spt[2 * N][K];
int lev[2 * N];


int find(int i) {
    return (i == p[i]) ? i : (p[i] = find(p[i]));
}


void dfs(int u, int par, int lv) {
    lev[u] = lv;
    spt[u][0] = par;
    for(int i=1; i<K; i++) {
        if(spt[u][i-1] != -1) {
            spt[u][i] = spt[spt[u][i-1]][i-1];
        }
    }
    for(int v: mst[u]) {
        dfs(v, u, lv+1);
    }
}

int lca(int u, int v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(int i=K-1; i>=0; i--) {
        if((lev[u] - (1 << i)) >= lev[v]) {
            u = spt[u][i];
        }
    }
    if(u == v) {
        return u;
    }
    for(int i=K-1; i>=0; i--) {
        if(spt[u][i] != -1 && spt[u][i] != spt[v][i]) {
            u = spt[u][i];
            v = spt[v][i];
        }
    }
    return spt[u][0];
}


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, m;
        scanf("%d %d", &n, &m);
        
        for(int i=0; i<=2*n; i++) {
            mst[i].clear();
        }
        wc.clear();

        for(int i=0; i<m; i++) {
            scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
        }
        
        sort(e, e+m, cmp);
        for(int i=1; i<=2*n; i++) {
            p[i] = i;
        }

        int z = n;
        for(int i=0; i<m; i++) {
            int u = e[i].x;
            int v = e[i].y;
            if(find(u) != find(v)) {
                z += 1;
                int pu = find(u), pv = find(v), pz = find(z);
                p[pu] = p[pv] = pz;
                wc[z] = e[i].w;
                mst[pz].push_back(pu);
                mst[pz].push_back(pv);
            }
        }

        for(int i=0; i<=z; i++) {
            for(int j=0; j<K; j++) {
                spt[i][j] = -1;
            }
        }

        assert(z <= 2*n);
        assert(find(1) == find(z));
        
        dfs(z, -1, 0);

        int q;
        scanf("%d", &q);
        printf("Case %d:\n", cc+1);
        for(int i=0; i<q; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            int t = lca(u, v);
            assert(wc.count(t) != 0);
            printf("%d\n", wc[t]);
        }
    }

    return 0;
}

<|start_filename|>string/hashing/codeforces/F835D/Solution.cpp<|end_filename|>
// problem name: Palindromic characteristics
// problem link: https://codeforces.com/contest/835/problem/D
// contest link: https://codeforces.com/contest/835
// time: (?)
// author: reyad

// other_tags: brute force, dp
// difficulty_level: medium


// note: solution is done using the following formula
// (1) if p_k is a k plindrome, then it is also a (k-1) palindrome
// (2) p_k = p_(k-1) + p_(k-1) if substring length is even
// (3) p_k = p_(k-1) + some character + p_(k-1) if sunstring length is odd
// using 2 and 3 one may find the max_k for a particular substring in a bottom
// up approach i.e. from using smaller substring for constructing result for
// larger substring in a iterative fashion
// complexity of this solution is O(n^2)

// there's also a faster dp solution for this problem
// there may have multiple other solution(faster)
// one such solution(complexity O(n)) is using palindromic tree
// read the comments in the editorial to find the link for that solution


#include <bits/stdc++.h>

using namespace std;

#define N 5004
#define MOD 1000000007

int memo[N][N];
int maxk[N][N] = {0}, cnt[N] = {0};

int main() {
	char str[N];
	
	scanf("%s", str);
	int n = strlen(str);
	for(int i=0; i<n; i++) {
		long long int h = 0, rh = 0, p = 47, pw = 1;
		for(int j=i; j<n; j++) {
			int v = str[j] - 'a' + 1;
			h = (h * p + v) % MOD;
			rh = (rh + v * pw) % MOD;
			pw = (pw * p) % MOD;
			memo[i][j] = (int)h;
			memo[j][i] = (int)rh;
		}
	}

	for(int l=1; l<=n; l++) {
		for(int i=0, j=i+l-1; j<n; i++, j++) {
			if(memo[i][j] == memo[j][i]) {
				maxk[i][j] = 1;
				if(l&1) {
					int m = (i+j) / 2;
					if(memo[i][m-1] == memo[m+1][j]) {
						maxk[i][j] = max(maxk[i][j], maxk[m+1][j] + 1);
					}
				} else {
					int m = (i+j) / 2;
					if(memo[i][m] == memo[m+1][j]) {
						maxk[i][j] = max(maxk[i][j], maxk[m+1][j] + 1);
					}
				}
				cnt[maxk[i][j]]++;
			}
		}
	}
	for(int i=n-1; i>0; i--) cnt[i] += cnt[i+1];

	for(int i=1; i<=n; i++) printf("%d ", cnt[i]);
	printf("\n");

	return 0;
}

<|start_filename|>dynamic_programming/basic/loj/F1106/Solution.c<|end_filename|>
//problem name: 1106 - Gone Fishing 
//problem link: http://lightoj.com/volume_showproblem.php?problem=1106
//contest link: (?)
//time: (?)
//author: aman

//other_tags: dynamic programming
//difficulty_level: (?)

#include<stdio.h>
#include<string.h>

#define max 30
#define mxtime 200

int dp[max][mxtime];
int trace[max][mxtime];
int n,h;
int f[max],d[max],dist[max];

//Num of fishes caught for a given time and area
int catch (int lake,int time) {
	if (d[lake] > 0)
		if (f[lake]/d[lake]+1 < time)
			time = f[lake]/d[lake]+1;

	int a = (time)*f[lake];
	int b = (time)*(time-1)/2;
	return a - b*d[lake];
}

//print time spent in every lake
void printTrace (int lake,int time) {
	if (lake > n)
		return;

	if (time<0) printf("%d",0 );
	else printf("%d",trace[lake][time]*5 );
	if (lake < n) printf(", ");

	printTrace(lake+1,time-trace[lake][time]-dist[lake]);
}


//Recursive Function calculating max number of fishes caught
int maxfish (int lake,int time)
{
	//printf("%d %d\n",lake,time );
	if (time<0 || lake>n) 
		return 0;

	if (dp[lake][time] != -1)
		return dp[lake][time];

	for (int i=time ;i>=0; i--) {
		int t = catch(lake,i) + maxfish(lake+1,time-i-dist[lake]);
		if (t > dp[lake][time]) {
			 dp[lake][time] = t;
			 trace[lake][time] = i;
		}
	}

	//printf("%d %d %d\n",lake,time,dp[lake][time] );
	return dp[lake][time];
}


int main() 
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int t;
	scanf("%d",&t);

	for (int c=1; c<=t; c++) {

		for (int i=0; i<max; i++) {
			memset(dp[i],-1,sizeof(dp[i]) );
			memset(trace[i],-1,sizeof(trace[i]) );
		}

		scanf("%d %d",&n,&h);

		for (int i=1; i<=n; i++) scanf("%d",&f[i]);
		for (int i=1; i<=n; i++) scanf("%d",&d[i]);
		for (int i=1; i<n; i++) scanf("%d",&dist[i]);

		h = h*60/5;

		int res = maxfish(1,h);
		printf("Case %d:\n",c);
		printTrace(1,h);
		printf("\n");
		printf("Number of fish expected: %d\n",res );

	}

	return 0;
}

<|start_filename|>math/probability/loj/F1104/Solution.cpp<|end_filename|>
// problem name: Birth<NAME>
// problem link: http://lightoj.com/volume_showproblem.php?problem=1104
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        long long n;
        scanf("%d", &n);
        double x = 1.0;
        int m = 0;
        for(int i=1; x > 0.5; i++) {
            x = x * (n - i) / n;
            m = i;
        }
        printf("Case %d: %d\n", cc+1, m);
    }
    return 0;
}


<|start_filename|>ad_hoc/implementation/codeforces/F1512B/Solution.cpp<|end_filename|>
// problem name: Almost Rectangle
// problem link: https://codeforces.com/contest/1512/problem/B
// contest link: https://codeforces.com/contest/1512
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: beginner


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

string s[412];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n;
        cin >> n;
        vector<pair<int, int>> p;
        for(int i=0; i<n; i++) {
            cin >> s[i];
            for(int j=0; j<n; j++) {
                if(s[i][j] == '*') {
                    p.push_back({i, j});
                }
            }
        }
        assert(p.size() == 2);
        assert(p[0] != p[1]);
        if(p[0].first == p[1].first) { // same row
            for(int i=0; i<n; i++) {
                if(i != p[0].first) {
                    s[i][p[0].second] = '*';
                    s[i][p[1].second] = '*';
                    break;
                }
            }
        } else if(p[0].second == p[1].second) { // same col
            for(int i=0; i<n; i++) {
                if(i != p[0].second) {
                    s[p[0].first][i] = '*';
                    s[p[1].first][i] = '*';
                    break;
                }
            }
        } else { // different row-col
            s[p[0].first][p[1].second] = '*';
            s[p[1].first][p[0].second] = '*';
        }
        for(int i=0; i<n; i++) {
            cout << s[i] << "\n";
        }
    }
    return 0;
}


<|start_filename|>search/binary_search/codeforces/F1355C/Solution.cpp<|end_filename|>
// problem name: Count Triangles
// problem link: https://codeforces.com/contest/1355/problem/C
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: implementation, math, two pointers
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

int main() {
	int a, b, c, d;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	long long tot = 0;
	for(int i=a; i<=b; i++) {
		int s = b, e = c, yp = -1;
		while(s <= e) {
			int m = (s + e) / 2;
			if(i + m > c) {
				yp = m;
				e = m - 1;
			} else {
				s = m + 1;
			}
		}
		if(yp != -1) {
			/* trying to measure the range of x(i) + y, where x(i) + y is always greater than z */
			/* then, we are trying to count for possible no. of z's for each x(i) + y */
			// for low      possible z's are c....low-1
			// for low + 1  possible z's are c....low
			// ....
			// ....
			// for d        possible z's are c....d-1
			// for d + 1    possible z's are c....d
			// for d + 2    possible z's are c....d
			// ....
			// ....
			// for high     possible z's are c....d
			// i.e. if low <= d, then for x + y = (low...d) the no of z's will be an arithmetic series
			int low = i + yp; // note: low > z(c), see the binary search above
			int high = i + c;
			if(low > d) {
				tot = tot + 1LL * (d - c + 1) * (c - yp + 1); // all (c...d) is eligible as z for y = (yp...c)
			} else {
				// so, z = (low-1) + low + (low+1) + ... + (h-1) for x+y = (low...min(d, high))
				int h = min(high, d);
				int u = (h - 1) - c + 1;   // z's range for (x+y = h): c...h-1
				int v = (low - 2) - c + 1; // z's range for (x+y = low-1): c...low-2
				tot = tot + (1LL * u * (u + 1) - 1LL * v * (v + 1)) / 2;
				// for x+y = d+1...high if high > d
				if(high > d) {
					tot = tot + 1LL * (high - d) * (d - c + 1);
				}
			}
		}
	}
	printf("%lld\n", tot);
	return 0;
}

<|start_filename|>graph/dfs/loj/F1111/Solution.cpp<|end_filename|>
// problem name: Best Picnic Ever
// problem link: http://lightoj.com/volume_showproblem.php?problem=1111
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: bfs, brute force
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


#define K 104
#define N 1004
#define M 10004

vector<int> g[N];
int seen[N];
int cnt[N];
int ks[K];


void dfs(int u) {
    seen[u] = true;
    cnt[u]++;
    for(int v: g[u]) {
        if(!seen[v]) {
            dfs(v);
        }
    }
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int k, n, m;
        scanf("%d %d %d", &k, &n, &m);
        for(int i=0; i<n; i++) {
            g[i].clear();
            cnt[i] = 0;
        }
        for(int i=0; i<k; i++) {
            scanf("%d", &ks[i]);
            --ks[i];
        }
        for(int i=0; i<m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            --u; --v;
            g[u].push_back(v);
        }
        for(int i=0; i<k; i++) {
            memset(seen, 0, sizeof(int) * n);
            dfs(ks[i]);
        }
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(cnt[i] == k) {
                ans++;
            }
        }
        printf("Case %d: %d\n", cc+1, ans);
    }
    return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1504C/Solution.cpp<|end_filename|>
// problem name: Balance the Bits
// problem link: https://codeforces.com/contest/1504/problem/C
// contest link: https://codeforces.com/contest/1504
// time: (?)
// author: reyad


// other_tags: greedy
// difficulty_level: beginner


// solution idea:
// when, 1: either both are open or both are close(so, when 1 both string are the same)
//       0: one is open and another is close
// so, n(0) must be even and the string cannot start or end with 0

#include <bits/stdc++.h>

using namespace std;

char s[200020];
char a[200020];
char b[200020];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        int z = 0;
        for(int i=0; s[i]; i++) {
            if(s[i] == '0') {
                z++;
            }
        }
        if(s[0] == '0' || s[n-1] == '0' || (z&1)) {
            printf("NO\n");
            continue;
        }
        int o = n - z;
        int co = 0, cz = 0;
        for(int i=0; i<n; i++) {
            if(s[i] == '1') {
                if((co << 1) < o) {
                    a[i] = b[i] = '(';
                } else {
                    a[i] = b[i] = ')';
                }
                co++;
            } else {
                if(cz&1) {
                    a[i] = '(';
                    b[i] = ')';
                } else {
                    a[i] = ')';
                    b[i] = '(';
                }
                cz++;
            }
        }
        a[n] = b[n] = 0;
        printf("YES\n");
        printf("%s\n", a);
        printf("%s\n", b);
    }
    return 0;
}


<|start_filename|>data_structure/priority_queue/codeforces/F1353D/Solution.cpp<|end_filename|>
// problem name: Constructing the Array
// problem link: https://codeforces.com/contest/1353/problem/D
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: constructive algorithm, sortings
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

#define N 200010

struct Range {
	int l, r;
	Range() {}
	Range(int l_, int r_) {
		l = l_;
		r = r_;
	}
	bool operator<(const Range &v) const {
		// cpp by default max priority queue
		if((r - l) == (v.r - v.l)) {
			return l > v.l; // max priority queue..so, reversing operation
		}
		return (r - l) < (v.r - v.l); // reversing operation..max priority queue
	}
};

int a[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		priority_queue<Range> pq;
		pq.push(Range(1, n));
		int action = 1;
		while(!pq.empty()) {
			Range u = pq.top();
			pq.pop();
			int m = (u.l + u.r) / 2;
			a[m] = action++;
			if(u.l < m) pq.push(Range(u.l, m-1));
			if(u.r > m) pq.push(Range(m+1, u.r));
		}
		for(int i=1; i<=n; i++) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}

<|start_filename|>data_structure/binary_search_tree/leetcode/F1801/Solution.cpp<|end_filename|>
// problem name: Number of Orders in the Backlog
// problem link: https://leetcode.com/contest/weekly-contest-233/problems/number-of-orders-in-the-backlog/
// contest link: https://leetcode.com/contest/weekly-contest-233/
// time: (?)
// author: reyad


// other_tags: segment tree
// difficulty_level: beginner



class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        map<int, long long> buy_backlog;
        map<int, long long> sell_backlog;
        int order_length = (int)orders.size();
        for(int i=0; i<order_length; i++) {
            if(orders[i][2] == 0) { // i.e. type is `buy`
                while(!sell_backlog.empty()) {
                    auto smallest_sell = sell_backlog.begin();
                    if(smallest_sell->first <= orders[i][0]) {
                        long long reduce = min((long long)orders[i][1], smallest_sell->second);
                        orders[i][1] -= (int)reduce;
                        smallest_sell->second -= reduce;
                        if(smallest_sell->second == 0) {
                            sell_backlog.erase(smallest_sell);
                        }
                        if(orders[i][1] == 0) {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if(orders[i][1]) {
                    buy_backlog[orders[i][0]] += (long long)orders[i][1];
                }
            } else { // i.e. type is `sell`
                while(!buy_backlog.empty()) {
                    auto largest_buy = buy_backlog.end();
                    largest_buy--;
                    if(largest_buy->first >= orders[i][0]) {
                        long long reduce = min((long long)orders[i][1], largest_buy->second);
                        orders[i][1] -= (int)reduce;
                        largest_buy->second -= reduce;
                        if(largest_buy->second == 0) {
                            buy_backlog.erase(largest_buy);
                        }
                        if(orders[i][1] == 0) {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if(orders[i][1]) {
                    sell_backlog[orders[i][0]] += (long long)orders[i][1];
                }
            }
        }
        long long ans = 0;
        for(auto it: buy_backlog) {
            ans += it.second;
        }
        for(auto it: sell_backlog) {
            ans += it.second;
        }
        printf("ans: %lld", ans);
        return (ans % (int)(1e9+7));
    }
};

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1345D/Solution.cpp<|end_filename|>
// problem_name: Monopole Magnets
// problem_link: https://codeforces.com/contest/1345/problem/D
// contest_link: https://codeforces.com/contest/1345
// time: (?)
// author: reyad

// other_tags: dfs, dsu
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

int n, m;
char b[1024][1024];
int p[1024 * 1024];

int find(int i) {
	return (i == p[i]) ? i : (p[i] = find(p[i]));
}

int _hash(int i, int j) {
	return (i * m) + j;
}

int countBlack() {
	int cntBlack = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(b[i][j] == '#') cntBlack++;
		}
	}
	return cntBlack;
}

bool okay() {
	bool rw = false, cw = false;
	for(int i=0; i<n; i++) {
		int cnt = (b[i][0] == '.') ? 0 : 1;
		for(int j=1; j<m; j++) {
			if(b[i][j] == '#' && b[i][j-1] != '#') cnt++;
		}
		if(cnt > 1) return false;
		if(cnt == 0) rw = true;
	}
	for(int j=0; j<m; j++) {
		int cnt = (b[0][j] == '.') ? 0 : 1;
		for(int i=1; i<n; i++) {
			if(b[i][j] == '#' && b[i-1][j] != '#') cnt++;
		}
		if(cnt > 1) return false;
		if(cnt == 0) cw = true;
	}
	return (rw == cw);
}

bool inrange(int i, int j) {
	return (0 <= i && i < n && 0 <= j && j < m);
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++) {
		scanf("%s", b[i]);
	}
	if(okay()) {
		if(!countBlack()) {
			printf("0\n");
			return 0;
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				int u = _hash(i, j);
				p[u] = u;
			}
		}
		int dx[] = {0, 0, 1, -1};
		int dy[] = {1, -1, 0, 0};
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(b[i][j] != '#') {
					continue;
				}
				int u = _hash(i, j);
				for(int k=0; k<4; k++) {
					int ti = i + dx[k];
					int tj = j + dy[k];
					if(!inrange(ti, tj) || b[ti][tj] != '#') {
						continue;
					}
					int v = _hash(ti, tj);
					if(find(u) != find(v)) {
						p[find(u)] = find(v);
					}
				}
			}
		}
		int res = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				int u = _hash(i, j);
				if(b[i][j] == '#' && find(u) == u) res++;
			}
		}
		printf("%d\n", res);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

<|start_filename|>greedy/basic/codeforces/F1348D/Solution.cpp<|end_filename|>
// problem_name: Phoenix and Science
// problem_link: https://codeforces.com/contest/1348/problem/D
// contest_link: https://codeforces.com/contest/1348
// time: (?)
// author: reyad

// other_tags: binary search, constructive algorithm, implementation, math
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


int main() {
	int tc;

	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		vector<int> v;
		for(int i=1; i<=n; i+=i) {
			n -= i;
			v.push_back(i);
		}
		if(n > 0) v.push_back(n);
		sort(v.begin(), v.end());
		printf("%d\n", (int)v.size() - 1);
		for(int i=1; i<(int)v.size(); i++) printf("%d ", v[i] - v[i-1]);
		printf("\n");
	}

	return 0;
}

<|start_filename|>dynamic_programming/non_classical/codeforces/F1475D/Solution.cpp<|end_filename|>
// problem name: Cleaning the Phone
// problem link: https://codeforces.com/contest/1475/problem/D
// contest link: https://codeforces.com/contest/1475/
// time: (?)
// author: reyad


// other_tags: binary search, sorting, two pointers
// difficulty_level: intermediate


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

#define N 200020

int mem[N];
int cost[N];
int mem1[N];
int mem2[N];
int p1[4 * N];
int p2[4 * N];
long long dp[4 * N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n, m;
        cin >> n >> m;
        for(int i=0; i<n; i++) {
            cin >> mem[i];
        }
        for(int i=0; i<n; i++) {
            cin >> cost[i];
        }
        int c1 = 0, c2 = 0;
        int mxc = 0;
        for(int i=0; i<n; i++) {
            if(cost[i] == 1) {
                mem1[c1++] = mem[i];
            } else {
                mem2[c2++] = mem[i];
            }
            mxc += cost[i];
        }
        sort(mem1, mem1 + c1);
        sort(mem2, mem2 + c2);
        p1[0] = c1 - 1, p2[0] = c2 - 1;
        dp[0] = 0;
        dp[1] = mem1[p1[0]];
        p1[1] = p1[0]-1;
        p2[1] = p2[0];
        int ans = (dp[1] >= m) ? 1 : -1;
        if(ans != -1) {
            cout << ans << "\n";
            continue;
        }
        for(int i=2; i<=mxc; i++) {
            dp[i] = -1;
            // int sel = -1;
            if(p1[i-1] >= 0 && dp[i-1] + mem1[p1[i-1]] > dp[i]) {
                dp[i] = dp[i-1] + mem1[p1[i-1]];
                p1[i] = p1[i-1]-1;
                p2[i] = p2[i-1];
                // sel = mem1[p1[i-1]];
            }
            if(p2[i-2] >= 0 && dp[i-2] + mem2[p2[i-2]] > dp[i]) {
                dp[i] = dp[i-2] + mem2[p2[i-2]];
                p1[i] = p1[i-2];
                p2[i] = p2[i-2]-1;
                // sel = mem2[p2[i-2]];
            }
            // cout << i << ": " << mem1[p1[i-1]] << " || " << mem2[p2[i-2]] << " || " << dp[i] << "\n";
            // cout << i << ": " << sel << "\n";
            if(dp[i] >= m) {
                ans = i;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}


<|start_filename|>hashing/string_hashing/codeforces/F752D/Solution.cpp<|end_filename|>
// problem name: Santa Claus and a Palindrome
// problem link: https://codeforces.com/contest/752/problem/D
// contest link: https://codeforces.com/contest/752
// time: (?)
// author: reyad


// other_tags: data structures, greedy, strings
// difficulty_level: expert



// note: this is by far the worst problem i've met while solving problems using hash
// the testcase is very strong, it hacks almost every single hash, and even some double hash
// i had to use double hashes simultaneously with two different bases and mods
// one my 'double hash without modulo' got hacked
// modulo with two different values saved the solution(for the provided testcase)


#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define M 1000000007
#define M2 1000000009

typedef long long int ll;

int a[N];
char g[N];

struct Compare {
	bool operator()(const int i, const int j) const {
		return a[i] < a[j];
	}
};

map<pair<ll, ll>, priority_queue<int, vector<int>, Compare>> hmp;
map<pair<ll, ll>, priority_queue<int, vector<int>, Compare>> rhmp;
map<pair<ll, ll>, priority_queue<int, vector<int>, Compare>> pmp;

int main() {
	int k, n;
	scanf("%d %d", &k, &n);
	for(int kk=0; kk<k; kk++) {
		scanf("%s %d", g, &a[kk]);
		ll h = 0, h2 = 0, rh = 0, rh2 = 0, p = 647, p2 = 2797;
		for(int i=0; i<n; i++) {
			h = (h * p + (g[i] - 'a' + 1)) % M;
			h2 = (h2 * p2 + (g[i] - 'a' + 1)) % M2;
			rh = (rh * p + (g[n-i-1] - 'a' + 1)) % M;
			rh2 = (rh2 * p2 + (g[n-i-1] - 'a' + 1)) % M2;
		}
		pair<ll, ll> hp = make_pair(h, h2);
		pair<ll, ll> hrev = make_pair(rh, rh2);
		if(hp == hrev) {
			pmp[hp].push(kk);
		} else {
			hmp[hp].push(kk);
			rhmp[hrev].push(kk);
		}
	}
	ll mxb = 0;
	for(auto it = hmp.begin(); it != hmp.end(); it++) {
		auto it2 = rhmp.find(it->first);
		if(it2 == rhmp.end()) continue;
		auto &q = it->second;
		auto &q2 = it2->second;
		while(!q.empty() && !q2.empty() && a[q.top()] + a[q2.top()] > 0) {
			mxb = mxb + a[q.top()] + a[q2.top()];
			q.pop();
			q2.pop();
		}
	}
	mxb = mxb / 2;
	int x = 0;
	for(auto it = pmp.begin(); it != pmp.end(); it++) {
		auto &q = it->second;
		while(q.size() >= 2) {
			int u = q.top();
			q.pop();
			if(a[u] + a[q.top()] > 0) {
				int v = q.top();
				q.pop();
				mxb = mxb + a[u] + a[v];
				if(a[v] < 0) x = max(x, -a[v]);
			} else {
				q.push(u);
				break;
			}
		}
		if(!q.empty()) x = max(x, a[q.top()]);
	}
	mxb = mxb + x;
	printf("%lld\n", mxb);
	return 0;
}


<|start_filename|>search/binary_search/codeforces/F1490G/Solution.cpp<|end_filename|>
// problem name: Old Floppy Drive
// problem link: https://codeforces.com/contest/1490/problem/G
// contest link: https://codeforces.com/contest/1490
// author: reyad
// time: (?)


// other_tags: math, binary search, data structures, sortings
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

#define N 200020

int a[N], x[N], y[N];
long long int s[N];


bool cmp(int i, int j) {
    return s[i] < s[j];
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; i++) {
            scanf("%d", &a[i]);
            x[i] = i;
        }
        s[0] = a[0];
        for(int i=1; i<n; i++) {
            s[i] = s[i-1] + a[i];
        }
        sort(x, x+n, cmp);
        y[n-1] = x[n-1];
        for(int i=n-2; i>=0; i--) {
            y[i] = min(y[i+1], x[i]);
        }
        for(int i=0; i<m; i++) {
            int sum;
            scanf("%d", &sum);
            if(s[n-1] <= 0 && s[x[n-1]] < sum) {
                printf("-1 ");
                continue;
            }
            long long int step = 0;
            if(s[n-1] > 0) {
                int start = 0;
                int end = (sum + s[n-1]) / s[n-1];
                int p = -1;
                while(start <= end) {
                    int mid = (start + end) / 2;
                    if(mid * s[n-1] + s[x[n-1]] >= sum) {
                        p = mid;
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                    }
                }
                assert(p != -1);
                sum = sum - (p * s[n-1]);
                step = step + (long long int)p * n;
            }
            int start = 0, end = n-1, p = -1;
            while(start <= end) {
                int mid = (start + end) / 2;
                if(sum <= s[x[mid]]) {
                    p = mid;
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            assert(p != -1);
            step += y[p];
            printf("%lld ", step);
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>string/hashing/spoj/FNHAY/Solution.cpp<|end_filename|>
// problem name: NHAY - A Needle in the Haystack
// problem link: https://www.spoj.com/problems/NHAY/
// contest link: (?)
// time: (?)
// author: reyad

// other_tags: substring finding and similiar
// difficulty_level: beginner


// note: this is very easy straight forward problem
// one may solve it using multiple ways


#include <bits/stdc++.h>
 
using namespace std;
 
 
#define N 2000010
#define MOD 1000000007

char txt[N], pat[N];
 
int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		scanf("%s %s", pat, txt);
		int m = strlen(pat);
		int n = strlen(txt);

		long long int base = 47, pwm = 1;
		for(int i=0; i<m; i++) pwm = (pwm * base) % MOD;

		long long int hpat = 0;
		for(int i=0; i<m; i++) hpat = (hpat * base + (pat[i] - 'a' + 1)) % MOD;

		long long int htxt = 0;
		bool flag = false;
		for(int i=0; i<n; i++) {
			htxt = (htxt * base + (txt[i] - 'a' + 1)) % MOD;
			if(i >= m) htxt = (htxt - (((txt[i-m] - 'a' + 1) * pwm) % MOD) + MOD) % MOD;
			if(i >= m-1 && htxt == hpat) {
				printf("%d\n", i-m+1);
				flag = true;
			}
		}
		if(!flag) printf("\n");
	}
	return 0;
}

<|start_filename|>math/number_theory/codeforces/F1350B/Solution.cpp<|end_filename|>
// problem name: Orac and Models
// problem link: https://codeforces.com/contest/1350/problem/B
// contest link: https://codeforces.com/contest/1350
// time: (?)
// author: reyad

// other_tags: dp
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

#define N 100000

vector<int> dv[N+10];
int b[N+10], r[N+10];

int main() {
	for(int i=1; i<=N; i++) {
		for(int j=i+i; j<=N; j+=i) {
			dv[j].push_back(i);
		}
	}

	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		for(int i=1; i<=n; i++) {
			scanf("%d", &b[i]);
			r[i] = 1;
		}
		for(int i=n; i>=1; i--) {
			for(int d: dv[i]) {
				if(b[i] > b[d]) {
					r[d] = max(r[d], r[i] + 1);
				}
			}
		}
		int mx = 0;
		for(int i=1; i<=n; i++) {
			mx = max(mx, r[i]);
		}
		printf("%d\n", mx);
	}
	return 0;
}

<|start_filename|>dynamic_programming/basic/codeforces/F1363B/Solution.cpp<|end_filename|>
// problem name: Subsequence Hate
// problem link: https://codeforces.com/contest/1363/problem/B
// contest link: https://codeforces.com/contest/1363
// time: (?)
// author: reyad


// other_tags: data structures, brute force, strings, implementation
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

#define N 1024

char s[N];
int one[N];
int zero[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		scanf("%s", s);
		int n = strlen(s);
		for(int i=0; i<n; i++) {
			one[i] = 0;
			zero[i] = 0;
		}
		for(int i=0; i<n; i++) {
			if(s[i] == '1') {
				one[i] = ((i == 0) ? 1 : (one[i-1] + 1));
				zero[i] = ((i == 0) ? 0 : zero[i-1]);
			} else {
				one[i] = ((i == 0) ? 0 : one[i-1]);
				zero[i] = ((i == 0) ? 1 : (zero[i-1] + 1));
			}
		}
		// printf("%d %d\n", one[n-1], zero[n-1]);
		int mn = 987654321;
		for(int i=0; i<n; i++) {
			// taking 0..i as left and i+1...n-1 as right
			// taking left all 0 and right 1: so we've to change left 1's and right 0's
			mn = min(one[i] + zero[n-1] - zero[i], mn);
			// printf("%d: %d %d\n", i, one[i], zero[n-1] - zero[i]);
			// taking left all 1 and right 0: so we've to change left 0's and right 1's
			mn = min(zero[i] + one[n-1] - one[i], mn);
		}
		printf("%d\n", mn);
	}
	return 0;
}

<|start_filename|>ad_hoc/beginner/codeforces/F1392A/Solution.cpp<|end_filename|>
// problem name: Omkar and Password
// problem link: https://codeforces.com/contest/1392/problem/A
// contest link: https://codeforces.com/contest/1392
// author: reyad
// time: (?)


// other tags: greedy, math
// difficulty level: beginner


#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, a, b;
		scanf("%d %d", &n, &a);
		bool same = true;
		for(int i=1; i<n; i++) {
			scanf("%d", &b);
			if(b != a) {
				same = false;
			}
		}
		if(same) {
			printf("%d\n", n);
		} else {
			printf("%d\n", 1);
		}
	}
	return 0;
}

<|start_filename|>graph/lca/codeforces/F1486F/Solution.cpp<|end_filename|>
// problem name: Pairs of Paths
// problem link: https://codeforces.com/contest/1486/problem/F
// contest link: https://codeforces.com/contest/1486
// time: (?)
// author: reyad


// other_tags: combinatorics, data structures, dynamic programming, trees, dfs
// difficulty_level: expert


#include <bits/stdc++.h>

using namespace std;

#define DEBUG 1

#define N 300030
#define K 20


/**
 *                   (o) parent of u
 *                    |
 *                   (u) parent of v1, v2, ...
 *             /    /   \    \
 *            /    /     \    \
 *           /    /       \    \
 *          /    /         \    \
 *         /    /           \    \
 *       (v1) (v2)         (v3) (v4)
 */


/**
 * @var
 * g is graph(stores adj list)
 */
vector<int> g[N];
/**
 * @var
 * pt stands for parent table, it is a sparse table
 * helps calculating lca
 * lev keeps track of level i.e. depth
 */
int pt[N][K], lev[N];
/**
 * @var
 * cnt the number of paths(given through query) of which a node 'u' is lca
 */
int lca_cnt[N] = {0};
/**
 * @var
 * ssc[v1] denotes the number of paths(given in query) which's lca is the parent of v1(in this
 * case, 'u')
 * `ssc` stands for `shared single edge count`(in this case edge u->v)
 * note: we don't need to keep track of 'u', cause v1 parent will always be 'u' in a rooted tree
 */
int ssc[N] = {0};
/**
 * @var
 * spc[u][{v1, v2}] denotes the number of paths(given in query) which's lca is the parent of {v1, 
 * v2} where v1, v2 are siblings and in this case their parent is 'u'.
 * `spc` stands for `shared pair edge count(in this case, u->v1 and u->v2)
 * note: we need to keep track of 'u' for computational purposes, otherwise we could just generate
 * all pair combination of `u's` children and find out their shared edge count.
 */
map<pair<int, int>, int> spc[N];
/**
 * @var
 * ptc stands for pass through count
 * it calculates the number of paths are going through a node `v` where 'v' is not a lca of the
 * path. That means the paths will eventually be go through `v's` parent(which is in this case 
 * 'u')
 */
int ptc[N] = {0};
/**
 * @var
 * a global vaiable which hold the answer
 */
long long ans;


/**
 * @function
 * prepares pt i.e sparse table
 */
void dfs(int u, int par, int lv) {
    lev[u] = lv;
    pt[u][0] = par;
    for(int i=1; i<K; i++) {
        if(pt[u][i-1] != -1) {
            pt[u][i] = pt[pt[u][i-1]][i-1];
        }
    }
    for(int v: g[u]) {
        if(v != par) {
            dfs(v, u, lv+1);
        }
    }
}

/**
 * @function
 * returns lca
 */
int lca(int u, int v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(int i=K-1; i>=0; i--) {
        if((lev[u] - (1 << i)) >= lev[v]) {
            u = pt[u][i];
        }
    }
    if(u == v) {
        return u;
    }
    for(int i=K-1; i>=0; i--) {
        if(pt[u][i] != -1 && pt[u][i] != pt[v][i]) {
            u = pt[u][i];
            v = pt[v][i];
        }
    }
    return pt[u][0];
}

/**
 * @function
 * returns nth_ancestor of a given node
 */
int nth_ancestor(int u, int nth) {
    for(int i = K-1; i >= 0; i--) {
        if((nth >> i) & 1) {
            u = pt[u][i];
        }
    }
    return u;
}

/**
 * @function
 * calculates no of pairs for a set of given n elements
 */
long long count_pair(int n) {
    return (long long)n * (n - 1) / 2;
}

/**
 * @function
 * processes pass through
 */
void process_pass_through(int u, int par) {
    for(auto v: g[u]) {
        if(v != par) {
            process_pass_through(v, u);
            ptc[u] += ptc[v];
        }
    }
}

/**
 * @function
 * calculates final answer
 */
void calc_ans(int u, int par) {
    // calculate ans for children
    for(auto v: g[u]) {
        if(v != par) {
            calc_ans(v, u);
        }
    }
    // calc ans for type 1 i.e. same lca
    // first add all possible pairs for which 'u' is lca
    ans += count_pair(lca_cnt[u]);
    // now subtract all pairs which has shared edge u->v1, u->v2, ...
    for(auto v: g[u]) {
        if(v != par) {
            ans -= count_pair(ssc[v]);
        }
    }
    // now, if there are some paths which goes through both two edges such as {v1, v2}
    // those path's pair have been subtracted twice, one for v1 and another fot v2
    // so, we must add those pairs
    for(auto sp: spc[u]) {
        ans += count_pair(sp.second);
    }

    // calc ans for type 2 i.e. different lca
    // first calculate total possible intersection
    // i.e. the number of pairs where one of the path has lca 'u'
    // and the other path pass through 'u' to its parent
    ans += (long long)ptc[u] * lca_cnt[u];
    // now, some path those pass through 'u'(i.e. goes to u's parent o)
    //      has shared edge with v1 with those paths which has lca at
    //      'u' and also goes through v1
    //      this is also tru for v2, v3, ...
    //      so, we must get rid of them
    // for that, first we need to determine the no of paths those goes through 'v1->u', 
    // 'v2->u', ... but does not have lca at 'u', i.e. goes to `u's` parent `o`
    // we may count it by subtracting ssc[v1] from ptc[v1]
    // i.e. ptc[v1] - ssc[v1]
    // ptc[v1] contains the number of paths that passes through v1 to u
    // ssc[v1] contains the number of paths that has lca at 'u'
    for(auto v: g[u]) {
        if(v != par) {
            int ptc_vuo = ptc[v] - ssc[v];
            // now, count the pairs those shared v->u edge
            ans -= (long long)ssc[v] * ptc_vuo;
        }
    }
}

/**
 * @function
 * driver function @main
 */
int main() {
    #undef DEBUG
    int n;
    scanf("%d", &n);
    for(int i=1; i<n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0, 0);
    int m;
    scanf("%d", &m);
    for(int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        // here, 'u' is the lca
        int u = lca(x, y);
        lca_cnt[u]++;
        // determining the children through which the path (x, y)
        // meets at 'u'
        int v1 = -1, v2 = -1;
        if(x != u) {
            v1 = nth_ancestor(x, lev[x] - lev[u] - 1);
        }
        if(y != u) {
            v2 = nth_ancestor(y, lev[y] - lev[u] - 1);
        }

        #ifdef DEBUG
        printf("lca of %d, %d: %d\n", x, y, u);
        printf("v1, v2: %d, %d\n", v1, v2);
        #endif
        
        // increase shared single edge count for v1
        if(v1 != -1) {
            ssc[v1]++;
        }
        // increase shared single edge count for v1
        if(v2 != -1) {
            ssc[v2]++;
        }
        // if v1, v2 both are used for path, then
        // increase count for shared pair edge count for {v1, v2}
        if(v1 != -1 && v2 != -1) {
            if(v2 < v1) {
                swap(v1, v2);
            }
            spc[u][{v1, v2}]++;
        }
        // now, update pass through count
        // ptc at x and y should be increased by 1
        // which will flow upward, you'll see in process_pass_through function
        ptc[x]++;
        ptc[y]++;
        // and therefore, ptc at 'u' i.e. lca must be reduced to 0
        ptc[u] -= 2;
        // in this way, ptc only contains the no of paths
        // that must go through a node to it's parent
    }
    
    process_pass_through(1, 0);

    #ifdef DEBUG
    printf("lca debug\n");
    for(int i=1; i<=n; i++) {
        printf("lca of %d: %d\n", i, lca_cnt[i]);
    }
    printf("\n");
    printf("shared single edge count debug\n");
    for(int i=1; i<=n; i++) {
        printf("ssc of %d: %d\n", i, ssc[i]);
    }
    printf("\n");
    printf("pass through count debug\n");
    for(int i=1; i<=n; i++) {
        printf("ptc of %d: %d\n", i, ptc[i]);
    }
    printf("\n");
    #endif

    ans = 0;
    calc_ans(1, 0);
    printf("%lld\n", ans);
}


<|start_filename|>greedy/basic/codeforces/F1506B/Solution.cpp<|end_filename|>
// problem name: Partial Replacement
// problem link: https://codeforces.com/contest/1506/problem/B
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: implementation
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

char s[64];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, k;
        scanf("%d %d %s", &n, &k, s);
        int f = -1, l = -1;
        for(int i=0; i<n; i++) {
            if(s[i] == '*' && f == -1) {
                f = i;
            }
            if(s[n-i-1] == '*' && l == -1) {
                l = n-i-1;
            }
        }
        int cnt = 1;
        if(f != l) {
            cnt++;
        }
        int i = f;
        while(i < l) {
            bool stop = false;
            for(int j=k; j>0; j--) {
                if(i+j < l) {
                    if(s[i+j] == '*') {
                        cnt++;
                        i = i+j;
                        break;
                    }
                } else {
                    stop = true;
                    break;
                }
            }
            if(stop) {
                break;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

<|start_filename|>math/basic/codeforces/F701B/Solution.cpp<|end_filename|>
// problem name: Cells Not Under Attack
// problem link: https://codeforces.com/contest/701/problem/B
// contest link: https://codeforces.com/contest/701
// time: (?)
// author: reyad

// other_tags: data structure
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

#define N 100010

int r[N] = {0};
int c[N] = {0};

int main() {
	long long n, m;
	scanf("%lld %lld", &n, &m);
	long long freeRow = n, freeCol = n;
	for(int i=0; i<m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if(!r[x]) {
			r[x] = 1;
			freeRow--;
		}
		if(!c[y]) {
			c[y] = 1;
			freeCol--;
		}
		printf("%lld ", freeRow * freeCol);
	}
	printf("\n");
	return 0;
}

<|start_filename|>math/basic/loj/F1090/Solution.cpp<|end_filename|>
// problem name: Trailing Zeroes (II) 
// pronlem link: http://lightoj.com/volume_showproblem.php?problem=1090
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: dynamic programming
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


#define N 1000010


int calc(int num, int div) {
    int cnt = 0;
    while((num % div) == 0) {
        num = num / div;
        cnt++;
    }
    return cnt;
}

int two[N];
int five[N];

int main() {
    two[0] = five[0] = 0;
    for(int i=1; i<N; i++) {
        two[i] = two[i-1] + calc(i, 2);
        five[i] = five[i-1] + calc(i, 5);
    }

    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, r, p, q;
        scanf("%d %d %d %d", &n, &r, &p, &q);
        int ts = two[n] - two[r] - two[n-r] + calc(p, 2) * q;
        int fs = five[n] - five[r] - five[n-r] + calc(p, 5) * q;
        printf("Case %d: %d\n", cc+1, min(ts, fs));
    }
    return 0;
}


<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1504B/Solution.cpp<|end_filename|>
// problem name: Flip the Bits
// problem link: https://codeforces.com/contest/1504/problem/B
// contest link: https://codeforces.com/contest/1504
// time: (?)
// author: reyad


// other_tags: greedy, implementation, math
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;


char s[300030];
char b[300030];
int c[300030];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        scanf("%s", b);
        for(int i=0; i<n; i++) {
            s[i] = s[i] - '0';
            b[i] = b[i] - '0';
            if(s[i] == 0) {
                c[i] = ((i > 0) ? c[i-1] : 0) + 1;
            } else {
                c[i] = ((i > 0) ? c[i-1] : 0);
            }
        }
        int shift = 0;
        int flag = 1;
        for(int i=n-1; i>=0; i--) {
            if((s[i] ^ shift) == b[i]) {
                continue;
            }
            if((c[i] * 2) != (i + 1)) {
                flag = 0;
                break;
            }
            shift ^= 1;
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}


<|start_filename|>graph/dfs/codeforces/F1490D/Solution.cpp<|end_filename|>
// problem name: Permutation Transformation
// problem link: https://codeforces.com/contest/1490/problem/D
// contest link: https://codeforces.com/contest/1490
// author: reyad
// time: (?)


// other_tags: divide and conquer, implementation
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


#define N 128

int d[N], a[N];

void calc_depth(int dv, int l, int r) {
    int x = l;
    for(int i=l+1; i<=r; i++) {
        if(a[i] > a[x]) {
            x = i;
        }
    }
    d[x] = dv;
    if(l <= x-1) {
        calc_depth(dv+1, l, x-1);
    }
    if(x+1 <= r) {
        calc_depth(dv+1, x+1, r);
    }
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d", &a[i]);
            d[i] = 0;
        }
        calc_depth(0, 0, n-1);
        for(int i=0; i<n; i++) {
            printf("%d ", d[i]);
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>brute_force/non_classical/codeforces/F1355A/Solution.cpp<|end_filename|>
// problem name: Sequence with Digits
// problem link: https://codeforces.com/contest/1355/problem/A
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: implementation, math
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		long long a, k;
		scanf("%lld %lld", &a, &k);
		for(int i=2; i<=k; i++) {
			int mn = 10, mx = -1;
			long long b = a;
			while(b > 0) {
				int d = b % 10;
				b = b / 10;
				mn = min(mn, d);
				mx = max(mx, d);
			}
			if(mn == 0) {
				break;
			}
			a = a + mn * mx;
		}
		printf("%lld\n", a);
	}
	return 0;
}

<|start_filename|>math/combinatorics/loj/F1117/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: http://lightoj.com/volume_showproblem.php?problem=1117
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: inclusion exclusion, gcd, lcm, divisibility
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

#define N 128

long long d[N];

long long gcd(long long a, long long b) {
    while(b != 0) {
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        long long n;
        scanf("%lld", &n);
        int m;
        scanf("%d", &m);
        for(int i=0; i<m; i++) {
            scanf("%lld", &d[i]);
        }
        long long tot = 0;
        for(int i=0; i<(1<<m); i++) {
            long long div = 1;
            int cnt = 0;
            for(int j=0; j<m; j++) {
                if(i&(1<<j)) {
                    div = lcm(div, d[j]);
                    cnt++;
                }
            }
            if(cnt) {
                if(cnt&1) {
                    tot = tot + (n / div);
                } else {
                    tot = tot - (n / div);
                }
            }
        }
        printf("Case %d: %lld\n", cc+1, n - tot);
    }
    return 0;
}


<|start_filename|>search/binary_search/codeforces/F1345B/Solution.cpp<|end_filename|>
// problem_name: Card Constructions
// problem_link: https://codeforces.com/contest/1345/problem/B
// contest_link: https://codeforces.com/contest/1345
// time: (?)
// author: reyad

// other_tags: brute force, dp, math
// difficulty_level: easy


#include <stdio.h>

using namespace std;


int main() {
	int tc;

	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		int cnt = 0;
		while(n > 0) {
			int s = 0, e = 1000000000, x = 0;
			while(s <= e) {
				int m = (s + e) / 2;
				if(((3LL * m * m + m) / 2) <= n) {
					x = m;
					s = m + 1;
				}
				else {
					e = m - 1;
				}
			}
			if(x) {
				n = n - (3LL * x * x + x) / 2;
				cnt++;
			}
			else n = 0;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

<|start_filename|>data_structure/list/leetcode/F19/Solution.cpp<|end_filename|>
// problem name: Remove Nth Node From End of List
// problem link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
// contest link: (?)
// time: (?)
// author: pri1311


// other_tags: (?)
// difficulty_level: beginner


/**
 * meta:
 *   - short_problem_description: Given the head of a linked list, remove the nth node from the end of the list and return its head.
 *   - follow_up: Could you do this in one pass?
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count=0;
        ListNode*p=head;
        while(p){
            count++;
            p=p->next;
        }
        if (count==1){
            delete p;
            return NULL;
        }
        p=head;
        int i=count-n-1;
        if (n==count){
            head=head->next;
            delete p;
            return head;
        }
        while(i--){
            p=p->next;
        }
        ListNode*t=p->next;
        p->next=t->next;
        delete t;
        return head;
    }
};


<|start_filename|>graph/sssp/codeforces/F1486E/Solution.cpp<|end_filename|>
// problem name: Paired Payment
// problem link: https://codeforces.com/contest/1486/problem/E
// contest link: https://codeforces.com/contest/1486
// time: (?)
// author: reyad


// other_tags: binary search, brute force, constructive algorithms, dp, flows
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

#define N 100010

vector<pair<int, int>> adj[N];
int d[N], mpe[N]; // note: mpe means `minimum of edges visited from parents`
                  //       i.e. the minimum of all edges
                  //       through which this particular node is discovered as an intermediary
                  //       node
int sqr(int n) {
    return n * n;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        --u; --v;
        adj[u].push_back({w, v}); // note: weight is saved in first and node no in second
        adj[v].push_back({w, u}); //       this is also maintained in priority_queue
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0}); // note: x.first will target weight and x.second will target node no
    d[0] = 0;
    mpe[0] = INT_MAX;
    for(int i=1; i<n; i++) mpe[i] = d[i] = INT_MAX;
    while(!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        if(d[x.second] < x.first) {
            continue;
        }
        for(auto y: adj[x.second]) {
            if(y.first < mpe[y.second]) {
                for(auto z: adj[y.second]) {
                    // note: `.second` targets node no, both in adj and pq
                    if(d[z.second] > d[x.second] + sqr(y.first + z.first)) {
                        d[z.second] = d[x.second] + sqr(y.first + z.first);
                        pq.push({d[z.second], z.second});
                    }
                }
                mpe[y.second] = y.first;
            }
        }
    }
    for(int i=0; i<n; i++) {
        if(d[i] == INT_MAX) {
            d[i] = -1;
        }
        printf("%d ", d[i]);
    }
    printf("\n");
    return 0;
}


<|start_filename|>greedy/basic/codeforces/F701A/Solution.cpp<|end_filename|>
// problem name: Cards
// problem link: https://codeforces.com/contest/701/problem/A
// contest link: https://codeforces.com/contest/701
// time: (?)
// author: reyad

// other_tags: implementation
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

int a[128];
int x[128];

bool cmp(const int i, const int j) {
	return a[i] < a[j];
}

int main() {
	int n;
	scanf("%d", &n);
	int tot = 0;
	for(int i=0; i<n; i++) {
		scanf("%d", &a[i]);
		tot += a[i];
		x[i] = i;
	}
	sort(x, x+n, cmp);
	int l = n / 2;
	for(int i=0; i<l; i++) {
		printf("%d %d\n", x[i]+1, x[n-i-1]+1);
	}
	return 0;
}

<|start_filename|>graph/lca/codeforces/F208E/Solution.cpp<|end_filename|>
// problem name: Blood Cousins
// problem link: https://codeforces.com/contest/208/problem/E
// contest link: https://codeforces.com/contest/208
// time: (?)
// author: reyad


// other_tags: dfs and similar, trees, binary search, data structures
// difficulty_level: expert


#include <bits/stdc++.h>

using namespace std;


#define N 100010
#define K 19

vector<int> adj[N];
int p[N];
int lev[N];
int stp[N][K];
int stm[N], etm[N];
int dtm = 0;
vector<int> b[N];


void dfs(int u, int par, int lv) {
    stm[u] = dtm++;
    b[lv].push_back(stm[u]);
    lev[u] = lv;
    stp[u][0] = par;
    for(int i=1; i<K; i++) {
        if(stp[u][i-1] != -1) {
            stp[u][i] = stp[stp[u][i-1]][i-1];
        }
    }
    for(int v: adj[u]) {
        dfs(v, u, lv+1);
    }
    etm[u] = dtm++;
}

int getAncestor(int u, int x) {
    for(int i=K-1; i>=0; i--) {
        if((1 << i) <= x) {
            u = stp[u][i];
            if(u == -1) {
                return u;
            }
            x = x - (1 << i);
        }
    }
    return u;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d", &p[i]);
        if(p[i] != 0) {
            adj[p[i]].push_back(i);
        }
    }
    for(int i=0; i<=n; i++) {
        for(int j=0; j<K; j++) {
            stp[i][j] = -1;
        }
    }
    for(int i=1; i<=n; i++) {
        if(p[i] == 0) {
            dfs(i, -1, 0);
        }
    }
    int m;
    scanf("%d", &m);
    for(int i=0; i<m; i++) {
        int u, r;
        scanf("%d %d", &u, &r);
        int t = getAncestor(u, r);
        if(t == -1) {
            printf("0 ");
            continue;
        }
        int lv = lev[u];
        int s = 0, e = (int)b[lv].size() - 1, x = -1;
        while(s <= e) {
            int m = (s + e) / 2;
            if(b[lv][m] > stm[t]) {
                x = m;
                e = m - 1;
            } else {
                s = m + 1;
            }
        }
        if(x == -1) {
            printf("0 ");
            continue;
        }
        s = 0; e = (int)b[lv].size() - 1; int y = -1;
        while(s <= e) {
            int m = (s + e) / 2;
            if(b[lv][m] < etm[t]) {
                y = m;
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        if(y == -1) {
            printf("0 ");
            continue;
        }
        printf("%d ", max(0, y - x));
    }
    printf("\n");

    return 0;
}

<|start_filename|>search/ternary_search/codeforces/F1355E/Solution.cpp<|end_filename|>
// problem name: Restorer Distance
// problem link: https://codeforces.com/contest/1355/problem/E
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: binary search, greedy, math, sorting
// difficulty_level: medium


// note: this problem can also be solved using binary_search
// to see solution for binary_search see search/binary_search/codeforces/F1355E/Solution.cpp

// solution idea:
// the cost curve would be somewhat like below:
// .                  .
//  .                .
//    .            .
//      .       .
//         . .
// so we just have to find the height of lowest cost point

#include <bits/stdc++.h>

using namespace std;

#define N 100010

const long long inf = (long long)1e18;

int h[N];
int n, a, r, m;

long long calc(long long lev) {
	long long put = 0;
	long long remove = 0;
	for(int i=0; i<n; i++) {
		if(h[i] <= lev) {
			put = put + lev - h[i];
		} else {
			remove = remove + h[i] - lev;
		}
	}
	// now, some elements to put, some to remove and some to move
	// the num of elements can be removed is cnt = min(put, remove) and
	// cnt element should be moved only when move cost(m) < put cost(a) + remove cost(r)
	// and other remaining should be removed or put just normally
	// so,
	long long cnt = min(put, remove);
	put -= cnt;
	remove -= cnt;
	return put * a + remove * r + cnt * min(a + r, m);
}

int main() {
	scanf("%d %d %d %d", &n, &a, &r, &m);
	for(int i=0; i<n; i++) {
		scanf("%d", &h[i]);
	}
	long long minCost = inf;
	int s = 0, e = (int)1e9; // height range 0...1e9
	// note: e - s > 1 condition is a must
	// cause if e = s + 1
	// then __m1 = s + s + e = s + s + s + 1 = 3*s + 1
	// and __m2 = s + e + e = s + (s+1) + (s+1) = 3*s + 2
	// so, __m2 = __m1 + 1
	// and it is then possible m1 = (__m1 / 3) = s
	// and m2 = (__m2 / 3) = s
	// i.e. m1 == m2
	// which is something we do not want and it would totally ignore value e
	// and would provide us wrong result
	while(e - s > 1) {
		long long m1 = (0LL + s + s + e) / 3;
		long long m2 = (0LL + s + e + e) / 3;
		if(calc(m1) > calc(m2)) {
			/**
			 * m1 provides much more than
			 * so, we should pull down the m1 until
			 * it equals or provides
			 * less value than m2
			 */
			s = m1 + 1; // we should add 1 to avoid infinite loop
			// and also +1 is totally okay
			// cause calc(m1) > calc(m2) i.e. m1 can never the answer while m2 is present
		} else {
			// its the reverse of situation of previous situation
			e = m2;
		}
	}
	printf("%lld\n", min(calc(s), calc(e)));
	return 0;
}

<|start_filename|>search/binary_search/codeforces/F701D/Solution.cpp<|end_filename|>
// problem name: As Fast As Possible
// problem link: https://codeforces.com/contest/701/problem/D
// contest link: https://codeforces.com/contest/701
// time: (?)
// author: reyad

// other_tags: math
// difficulty_level: medium

#include <bits/stdc++.h>

using namespace std;

// solution idea:
// (01) first we've to observe that, if we want to minimize the time, we've to consider that, all
//      the pupils reach the end of the line at the same time
// (02) now, let the time, t = t1 + t2(here, t1 pupil has v1 speed, and t2 was the time on bus they spend)
//      (note: each pupil has spent exactly t2 time on bus i.e. they were at v2 speed)
// (03) so, to carry all the pupils bus has to be used cnt = ceil(n / k) times and return i.e. go to
//      opposite direction (cnt - 1) times
// (04) let's assume: t = t1 + t2 = (l1 / v1) + (l2 / v2)
//      we know that, v2 > v1, so increasing l2 will minimize the time(cause, l1 + l2 = l, constant)
// (05) so, a pupil crosses l2 length on bus and l1 on its own
//      let's assume, the bus has to came back(i.e. travel in opposite direction) to pick up next k
//      pupil which is a distance of x
//      so, we may say that:
//      => the time bus travel = the time pupil travel
//      => (l2 + x) / v2 = (l2 - x) / v1
//      => x = l2 * (v2 - v1) / (v1 + v2)
// (05) so, the total distance the bus has to travel is: cnt * l2 + (cnt - 1) * x
// (06) so, the total time the bus has to travel: b_time = (cnt * l2 + (cnt - 1) * x) / v2;
// (07) and, the total time a pupil has to travel: p_time = (l2 / v2) + ((l - l2) / v1)
// (08) when, b_time <= p_time, we can see for larger l2, if that's also satisfy b_time <= p_time
//      else, we reduce l2 and watch for that
//      and bibary serach can perfectly do this job

int main() {
	int n, l, v1, v2, k;
	scanf("%d %d %d %d %d", &n, &l, &v1, &v2, &k);
	double s = 0.0, e = 0.0 + l, optimal = 0.0 + l;
	int cnt = (n+k-1) / k;
	while(e - s > 1e-9) {
		double l2 = (s + e) / 2.0;
		double x = (l2 * (v2 - v1)) / (0.0 + v1 + v2);
		double b_time = (l2 * cnt + (cnt - 1) * x) / v2;
		double p_time = (l2 / v2) + ((l - l2) / v1);
		if(b_time <= (p_time + 1e-9)) {
			optimal = p_time;
			s = l2;
		} else {
			e = l2;
		}
	}
	printf("%.9f\n", optimal);
	return 0;
}

<|start_filename|>greedy/basic/codeforces/F1348B/Solution.cpp<|end_filename|>
// problem_name: Phoenix and Beauty
// problem_link: https://codeforces.com/contest/1348/problem/B
// contest_link: https://codeforces.com/contest/1348
// time: (?)
// author: reyad

// other_tags: constructive algorithm, data structures, sorting
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


int main() {
	int tc, b[128], p[128];

	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		scanf("%d %d", &n, &k);
		
		set<int> s;
		for(int i=0; i<n; i++) {
			scanf("%d", &b[i]);
			s.insert(b[i]);
		}

		if((int)s.size() > k) {
			printf("-1\n");
			continue;
		}
		
		int h = 0;
		for(int it: s) {
			p[h++] = it;
		}
		while(h < k) p[h++] = 1;
		printf("%d ", n * k);
		for(int i=0; i<n; i++) {
			for(int j=0; j<k; j++) {
				printf("%d ", p[j]);
			}
		}
		printf("\n");
	}
	return 0;
}


<|start_filename|>greedy/basic/codeforces/F1512E/Solution.cpp<|end_filename|>
// problem name: Permutation by Sum
// problem link: https://codeforces.com/contest/1512/problem/E
// contest link: https://codeforces.com/contest/1512
// time: (?)
// author: reyad


// other_tags: brute force, math
// difficulty_level: beginner


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n, l, r, s;
        cin >> n >> l >> r >> s;
        int o = r - l + 1;
        int min_sum = o * (o + 1) / 2;
        int _o = n - o;
        int max_sum = (n * (n + 1) / 2) - (_o * (_o + 1) / 2);
        if(s < min_sum || s > max_sum) {
            cout << -1 << "\n";
            continue;
        }
        set<int> st;
        for(int i=n; i>=1; i--) {
            if((s - i) >= (o * (o - 1) / 2)) {
                s -= i;
                o--;
                st.insert(i);
            }
        }
        assert(s == 0);
        int c = 1;
        for(int i=1; i<=n; i++) {
            if(c == l) {
                for(auto it: st) {
                    cout << it << " ";
                }
                c++;
            }
            if(st.find(i) == st.end()) {
                cout << i << " ";
                c++;
            }
        }
        if(c == l) {
            for(auto it: st) {
                cout << it << " ";
            }
            c++;
        }
        cout << "\n";
    }
    return 0;
}


<|start_filename|>computational_geometry/picks_theorem/loj/F1418/Solution.cpp<|end_filename|>
// problem name: Trees on My Island
// problem link: http://lightoj.com/volume_showproblem.php?problem=1418
// contest link: (?)
// time: (?)
// author: sumnoon


// other_tags: (?)
// difficulty_level: expert


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point { long long x, y;   // only used if more precision is needed
  	point() { x = y = 0.0; }                      // default constructor
    point(long long _x, long long _y) : x(_x), y(_y) {}        // user-defined
};
long long area(const vector<point> &P) {
long long result = 0.0, x1, y1, x2, y2;
    for (int i = 0; i < (int)P.size()-1; i++) {
        x1 = P[i].x; x2 = P[i+1].x;
        y1 = P[i].y; y2 = P[i+1].y;
        result += (x1 * y2 - x2 * y1);
    }
    return fabs(result) / 2.0;
}
int main(){
    int tc,i,n,j;
    long long x,y,inside;
    scanf("%d",&tc);
    for(i=1;i<=tc;i++){
        scanf("%d",&n);
        vector<point>p;
        long long tempx=0,tempy=0,on=0;
        double a;
        for(j=0;j<n;j++){
            scanf("%lld%lld",&x,&y);
            p.push_back(point(x,y));
            tempx=x,tempy=y;
        }
        p.push_back(p[0]);
        for(j=0;j<(int)p.size()-1;j++)on+=__gcd(llabs(p[j].x-p[j+1].x),llabs(p[j].y-p[j+1].y));
        on/=2;
        a=area(p);
        inside=llabs(a)-on+1;
        printf("Case %lld: %lld\n",i,inside);
    }
    return 0;
}



<|start_filename|>graph/dfs/codeforces/F701E/Solution.cpp<|end_filename|>
// problem name: Connecting Universities
// problem link: https://codeforces.com/contest/701/problem/E
// contest link: https://codeforces.com/contest/701
// time: (?)
// author: reyad

// other_tags: dp, graph, tree
// difficulty_level: medium

#include <bits/stdc++.h>

using namespace std;

#define N 200020

// solution idea:
// (1) the whole solution is dependent on properties of tree
// (2) the idea is to increase the number of usage of an edge to have the maximum possible sum(distance)
//     of university pairs
// (3) and it can be done by choosing maximum possible times an edge can be used(where we always take the
//     maximum for each edge), when the subtree which is hold by that edge(considering a rooted tree)
// (4) it can be proved that, the maximum possible number of times an edge can be used is:
//     let's consider an edge u-v, where u is parent of v
//     and v subtree has tcnt universities(including v)
//     then, maximum no. of times u-v edge can be used is: min(tcnt, (k+k) - tcnt)
//     i.e. the no. of pairs that can be constructed with outside of the v subtree
// (5) the proof of min(tcnt, (k+k) - tcnt) is maximum:
//     if it is not maxmimum, then consider other cases that could be maximum
//     and example of such cases would be: atleast one or more pairs are constructed inside v subtree and
//     atleast one or more pairs are construted outside v subtree which gives much more edge usage than our
//     provided formula. and if we van prove that such example couldn't give much than our provided formula
//     then we are done
//     proof by example:
//     consider a pair outside of v subtree is p, q and a pair inside of v subtree is x, y
//     then, the distance between p and q is: dist(p, q) = dist(p, lca(p, q)) + dist(q, lca(p, q))
//     and, the distance between x and y is: dist(x, y) = dist(x, lca(x, y)) + dist(y, lcs(x, y))
//     Now, let's consider the distance between: p, x and q, y
//     here we've to consider some cases regarding lca(p, q)
//     case-01: when lca(p, q) is nearer to v than both p and q
//              dist(p, x) = dist(p, lca(p, q)) + dist(lca(p, q), lca(x, y)) + dist(lca(x, y), x)
//              dist(q, y) = dist(q, lca(p, q)) + dist(lca(p, q), lca(x, y)) + dist(lca(x, y), y)
//       >> case-01 clearly shows that, dist(p, x) + dist(q, y) >= dist(p, q) + dist(x, y)
//     case-02: either p or q is nearer to v than lca(p, q), let's assume it p:
//              dist(p, x) = dist(p, lca(x, y)) + dist(lca(x, y), x)
//              dist(q, y) = dist(q, lca(p, q)) + dist(lca(p, q), lca(x, y)) + dist(lca(x, y), y)
//       >> case-02 also clearly shows that, dist(p, x) + dist(q, y) >= dist(p, q) + dist(x, y)
//     [[proved]]


vector<int> adj[N];
int seen[N] = {0};
int hasUniversity[N] = {0};

int n, k, k2;

long long maxSum = 0;

int dfs(int u) {
	seen[u] = 1;
	int cnt = (hasUniversity[u]) ? 1 : 0;
	for(int v: adj[u]) {
		if(!seen[v]) {
			/* we are calculating maximum possible use of edge (u to v) */
			/* tcnt refers to no of nodes(i.e. cities) under
			 * edge u-v(i.e. v subtree) which has universities
			 */
			int tcnt = dfs(v);
			maxSum = maxSum + min(tcnt, k2 - tcnt); // updating maxSum with max possible
			// usage of edge u-v in pairs
			cnt += tcnt; // updating cnt i.e. no of universities to return to parent node
		}
	}
	return cnt;
}

int main() {
	scanf("%d %d", &n, &k);
	k2 = k + k;
	for(int i=0; i<k2; i++) {
		int uni;
		scanf("%d", &uni);
		hasUniversity[uni] = 1;
	}
	for(int i=1; i<n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	printf("%lld\n", maxSum);
	return 0;
}

<|start_filename|>string/hashing/spoj/FNAJPF/Solution.cpp<|end_filename|>
// problem name: NAJPF - Pattern Find
// problem link: https://www.spoj.com/problems/NAJPF/
// contest link: (?)
// time: (?)
// author: reyad

// other_tags: substring finding and similiar
// difficulty_level: beginner


// note: this is very easy straight forward problem
// one may solve it using multiple ways


#include <bits/stdc++.h>
 
using namespace std;
 
 
#define N 1000010
#define MOD 1000000007
 
char txt[N], pat[N];
vector<int> v;
 
int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		v.clear();
		scanf("%s %s", txt, pat);
		int n = strlen(txt);
		int m = strlen(pat);
 
		long long int h = 0, hs = 0, p = 331, pw = 1;
		for(int i=0; i<m; i++) pw = (pw * p) % MOD;
		for(int i=0; i<m; i++) hs = (hs * p + (pat[i] - 'a' + 1)) % MOD;
		for(int i=0; i<n; i++) {
			h = (h * p + (txt[i] - 'a' + 1)) % MOD;
			if(i >= m) h = (h - (((txt[i-m] - 'a' + 1) * pw) % MOD) + MOD) % MOD;
			if(i >= m-1 && h == hs) v.push_back(i-m+1);
		}
 
		if(cc) printf("\n");
		if(v.size() == 0) {
			printf("Not Found\n");
			continue;
		}
		printf("%d\n", v.size());
		for(int it: v) printf("%d ", it+1);
		printf("\n");
	}
	return 0;
}

<|start_filename|>math/basic/codeforces/F1350A/Solution.cpp<|end_filename|>
// problem name: Orac and Factors
// problem link: https://codeforces.com/contest/1350/problem/A
// contest link: https://codeforces.com/contest/1350
// time: (?)
// author: reyad

// other_tags: number theory
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

int getFirstDiv(int n) {
	// note: n is always greater than or equal 2
	if((n&1) == 0) return 2;
	for(int i=3; (long long)i*i <= n; i+=2) {
		if((n % i) == 0) return i;
	}
	return n;
}

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		scanf("%d %d", &n, &k);
		int d = getFirstDiv(n);
		if(d == n) { // if prime
			printf("%lld\n", n + n + (long long)(k-1) * 2);
		} else if(d == 2) { // if even
			printf("%lld\n", n + (long long)k * 2);
		} else { // if odd
			printf("%lld\n", n + d + (long long)(k-1) * 2);
		}
	}
	return 0;
}

<|start_filename|>ad_hoc/implementation/codeforces/F1363A/Solution.cpp<|end_filename|>
// problem name: Odd Selection
// problem link: https://codeforces.com/contest/1363/problem/A
// contest link: https://codeforces.com/contest/1363
// time: (?)
// author: reyad


// other_tags: brute force, math
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, x;
		scanf("%d %d", &n, &x);
		int odd = 0, even = 0;
		for(int i=0; i<n; i++) {
			int a;
			scanf("%d", &a);
			if(a&1) {
				odd++;
			} else {
				even++;
			}
		}
		if(odd == 0 || ((even == 0) && ((x&1) == 0)) || ((x == n) && ((odd&1) == 0))) {
			printf("No\n");
		} else {
			printf("Yes\n");
		}
	}
	return 0;
}

<|start_filename|>brute_force/loop/codeforces/F1506C/Solution.cpp<|end_filename|>
// problem name: Double-ended Strings
// problem link: https://codeforces.com/contest/1506/problem/C
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: dynamic programming, hashing, string
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

char a[32], b[32];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        scanf("%s %s", a, b);
        int an = strlen(a);
        int bn = strlen(b);
        int ans = an + bn;
        for(int i=0; i<an; i++) {
            for(int j=i; j<an; j++) {
                int w = j-i+1;
                for(int k=0; k<bn; k++) {
                    bool matched = true;
                    for(int h=0; h<w; h++) {
                        if(b[k+h] != a[i+h]) {
                            matched = false;
                            break;
                        }
                    }
                    if(matched) {
                        ans = min(ans, an+bn-(w+w));
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}


<|start_filename|>graph/lca/codeforces/F191C/Solution.cpp<|end_filename|>
// problem name: Fools and Roads
// problem link: https://codeforces.com/contest/191/problem/C
// contest link: https://codeforces.com/contest/191
// time: (?)
// author: reyad


// other_tags: data structures, trees, dfs, bfs
// difficulty_level: expert


#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define K 18

int lev[N];
int par[N];
int seen[N];
int od[N];
int qu[N];
int qw[N];
int sp[N][K];
int cnt[N];
int res[N];
vector<int> g[N];
map<pair<int, int>, int> mp;


void dfs(int u, int p, int lv) {
    lev[u] = lv;
    par[u] = p;
    seen[u] = true;
    sp[u][0] = p;
    for(int i=1; i<K; i++) {
        if(sp[u][i-1] != -1) {
            sp[u][i] = sp[sp[u][i-1]][i-1];
        }
    }
    for(int v: g[u]) {
        if(!seen[v]) {
            dfs(v, u, lv+1);
            od[u]++;
        }
    }
}

int lca(int u, int v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(int i=K-1; i>=0; i--) {
        if(lev[u] - (1 << i) >= lev[v]) {
            u = sp[u][i];
        }
    }
    if(u == v) {
        return u;
    }
    for(int i=K-1; i>=0; i--) {
        if(sp[u][i] != -1 && sp[u][i] != sp[v][i]) {
            u = sp[u][i];
            v = sp[v][i];
        }
    }
    return sp[u][0];
}


int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i<n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
        mp[make_pair(min(u, v), max(u, v))] = i;
    }
    for(int i=0; i<=n; i++) {
        seen[i] = 0;
        od[i] = 0;
        cnt[i] = 0;
        for(int j=0; j<K; j++) {
            sp[i][j] = -1;
        }
    }
    dfs(1, -1, 0);
    int k;
    scanf("%d", &k);
    for(int i=0; i<k; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        int anc = lca(u, v);
        cnt[u]++;
        cnt[v]++;
        cnt[anc]-=2;
    }
    int qs = 0, qe = 0;
    for(int i=1; i<=n; i++) {
        if(!od[i]) {
            qw[qe] = cnt[i];
            qu[qe++] = i;
        }
    }
    while(qs != qe) {
        int w = qw[qs];
        int u = qu[qs++];
        int p = par[u];
        if(p != -1) {
            res[mp[make_pair(min(u, p), max(u, p))]] = w;
            cnt[p] += w;
            od[p]--;
            if(od[p] == 0) {
                qw[qe] = cnt[p];
                qu[qe++] = p;
            }
        }
    }
    for(int i=1; i<n; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    
    return 0;
}

<|start_filename|>ad_hoc/implementation/codeforces/F1392B/Solution.cpp<|end_filename|>
// problem name: Omkar and Infinity Clock
// problem link: https://codeforces.com/contest/1392/problem/B
// contest link: https://codeforces.com/contest/1392
// author: reyad
// time: (?)


// other tags: math
// difficulty level: beginner


#include <bits/stdc++.h>

using namespace std;


int a[200020];

int main() {

	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		long long n, k;
		scanf("%lld %lld", &n, &k);
		bool hasZero = false;
		int mx = -1000000007;
		for(int i=0; i<n; i++) {
			scanf("%d", &a[i]);
			if(a[i] == 0) {
				hasZero = true;
			}
			mx = max(mx, a[i]);
		}
		int nmx = -1000000007;
		for(int i=0; i<n; i++) {
			a[i] = mx - a[i];
			nmx = max(nmx, a[i]);
		}
		k--;
		mx = nmx;
		if(k&1) {
			for(int i=0; i<n; i++) {
				a[i] = mx - a[i];
			}
		}
		for(int i=0; i<n; i++) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}

<|start_filename|>search/binary_search/codeforces/F1486C2/Solution.cpp<|end_filename|>
// problem name: Guessing the Greatest (hard version)
// problem link: https://codeforces.com/contest/1486/problem/C2
// contest link: https://codeforces.com/contest/1486
// time: (?)
// author: reyad


// other_tags: interactive
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


int query(int l, int r) {
    if(l < r) {
        printf("? %d %d\n", l, r);
        fflush(stdout);
        int y;
        scanf("%d", &y);
        return y;
    }
    return -1;
}


int main() {
    int n;
    scanf("%d", &n);
    int x = query(1, n);
    bool left = true;
    if(query(1, x) != x) {
        left = false;
    }
    int len = left ? x : (n - x + 1);
    int k = 1;
    while(len > 0) {
        k += k;
        len /= 2;
    }
    if(left) {
        int u = 1;
        while(k > 0) {
            int m = u + (k / 2);
            if(query(m, x) == x) {
                u += k / 2;
            }
            k = k / 2;
        }
        printf("! %d\n", u+k);
    } else {
        int u = n;
        while(k > 0) {
            int m = u - (k / 2);
            if(query(x, m) == x) {
                u -= k / 2;
            }
            k = k / 2;
        }
        printf("! %d\n", u-k);
    }
    return 0;
}


<|start_filename|>greedy/non_classical/codeforces/F1506D/Solution.cpp<|end_filename|>
// problem name: Epic Transformation
// problem link: https://codeforces.com/contest/1506/problem/D
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: constructive algorithm, data structure
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        map<int, int> mp;
        priority_queue<int> pq;
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            int a;
            scanf("%d", &a);
            mp[a]++;
        }
        for(auto it: mp) {
            pq.push(it.second);
        }
        while(!pq.empty()) {
            int x = pq.top();
            pq.pop();
            if(pq.empty()) {
                pq.push(x);
                break;
            }
            int y = pq.top();
            pq.pop();
            // printf("x, y: %d\n", x, y);
            --x; --y;
            if(x) {
                pq.push(x);
            }
            if(y) {
                pq.push(y);
            }
        }
        int ans = 0;
        while(!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}


<|start_filename|>graph/bfs/codeforces/F1350E/Solution.cpp<|end_filename|>
// problem name: Orac and Game of Life
// problem link: https://codeforces.com/contest/1350/problem/E
// contest link: https://codeforces.com/contest/1350
// time: (?)
// author: reyad

// other_tags: data structures, implementations, math
// difficulty_level: medium


// observation or solution hints:
// (i)   once a cell starts flipping color, after that it'll never stop
// (ii)  so, try to find out when a cell will start flipping
// (iii) according to definiton: two consecutive cell with same color starts the flipping at iteration 1
// (iv)  flipping cells will make the non-flipping start flipping
// (v)   so find out, what is the least possible time a cell may start flipping

#include <bits/stdc++.h>

using namespace std;

#define N 1004

int n;
int m;
int t;
char color[N][N];
int lev[N][N] = {0};
int qx[N * N];
int qy[N * N];
int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};

bool inrange(int x, int y) {
	return (0 <= x && x <= n-1 && 0 <= y && y <= m-1);
}

int main() {
	scanf("%d %d %d", &n, &m, &t);
	for(int i=0; i<n; i++) {
		scanf("%s", color[i]);
	}
	int s = 0, e = 0;
	for(int x=0; x<n; x++) {
		for(int y=0; y<m; y++) {
			for(int k=0; k<4; k++) {
				int tx = x + dx[k];
				int ty = y + dy[k];
				if(!inrange(tx, ty)) continue;
				if(color[x][y] == color[tx][ty]) {
					lev[x][y] = 1;
					qx[e] = x;
					qy[e++] = y;
					break;
				}
			}
		}
	}
	while(s != e) {
		int ux = qx[s];
		int uy = qy[s++];
		for(int k=0; k<4; k++) {
			int vx = ux + dx[k];
			int vy = uy + dy[k];
			if(!inrange(vx, vy) || lev[vx][vy]) continue;
			lev[vx][vy] = lev[ux][uy] + 1;
			qx[e] = vx;
			qy[e++] = vy;
		}
	}
	for(int tt=0; tt<t; tt++) {
		int x, y;
		long long p;
		scanf("%d %d %lld", &x, &y, &p);
		--x;
		--y;
		if(!lev[x][y] || p < lev[x][y]) {
			printf("%c\n", color[x][y]);
		} else {
			if((p - lev[x][y]) & 1) {
				printf("%c\n", color[x][y]);
			} else {
				printf("%c\n", ((color[x][y] == '1') ? '0' : '1'));
			}
		}
	}
	return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1348C/Solution.cpp<|end_filename|>
// problem_name: Phoenix and Distribution
// problem_link: https://codeforces.com/contest/1348/problem/C
// contest_link: https://codeforces.com/contest/1348
// time: (?)
// author: reyad

// other_tags: greedy, strings, sorting
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

int cnt[128];
char s[100010];
char b[32];

int main() {
	int tc;

	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		
		scanf("%d %d", &n, &k);
		scanf("%s", s);
		
		for(int i='a'; i<='z'; i++) cnt[i] = 0;
		for(int i=0; i<n; i++) cnt[s[i]]++;
		int bc = 0;
		for(int i='a'; i<='z'; i++) if(cnt[i]) b[bc++] = i;

		int p = 0, tot = 0;
		while(tot + cnt[b[p]] < k) {
			tot += cnt[b[p]];
			p++;
		}
		if(p > 0) printf("%c", b[p]);
		else {
			printf("%c", b[p]);
			cnt[b[p]] -= k;
			if(bc == 1) {
				while(cnt[b[p]] > 0) {
					printf("%c", b[p]);
					cnt[b[p]] -= k;
				}
			}
			else if(!cnt[b[p]] && bc == 2) {
				int x = (cnt[b[++p]] + k - 1) / k;
				for(int i=0; i<x; i++) printf("%c", b[p]);
			}
			else {
				while(p < bc) {
					for(int i=0; i<cnt[b[p]]; i++) {
						printf("%c", b[p]);
					}
					p++;
				}
			}
		}
		printf("\n");
	}

	return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1392D/Solution.cpp<|end_filename|>
// problem name: Omkar and Bed Wars
// problem link: https://codeforces.com/contest/1392/problem/D
// contest link: https://codeforces.com/contest/1392
// author: reyad
// time: (?)


// other tags: greedy, dp
// difficulty level: medium


#include <bits/stdc++.h>

using namespace std;

// solution idea:
// -----------------------
// only (RRR...) and 
//      (LLL...) are the wrongs
// i.e. no substring of length 3 with same char is allowed

char a[200020];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d %s", &n, a);
		int c = 1;
		int cost = 0;
		for(int i=n-1; i>0; i--) {
			if(a[i] == a[0]) {
				c++;
			} else {
				break;
			}
		}
		if(c == n) { // then, all th chars are same
			cost = (n / 3) + (((n%3) == 0) ? 0 : 1); // playing method is circular, and all chars are same
			// so, we need take one more if n is not divided by 3
			// cause, RRR -> RLR it's good
			// but,   RRRR -> RRLR, not good(still, RRR is possible). Rather, LRLR would be good(no RRR)
		} else {
			n = n - c + 1; // reducing n by the number of last char's which
			// are same as first char of string, cause playing method is circular
			for(int i=1; i<n; i++) {
				if(a[i] == a[i-1]) {
					c++;
				} else {
					cost = cost + (c / 3); // splitting up length c of same chars
					// printf("%d: %d\n", i, c);
					c = 1;
				}
			}
			cost = cost + (c / 3);
		}
		printf("%d\n", cost);
	}
	return 0;
}

<|start_filename|>search/binary_search/codeforces/F1355E/Solution.cpp<|end_filename|>
// problem name: Restorer Distance
// problem link: https://codeforces.com/contest/1355/problem/E
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: ternary search, greedy, math, sorting
// difficulty_level: medium


// note: this problem can also be solved using ternary_search
// to see solution for ternary_search see search/ternary_search/codeforces/F1355E/Solution.cpp

// solution idea:
// the cost curve would be somewhat like below:
// .                  .
//  .                .
//    .            .
//      .       .
//         . .
// so we just have to find the height of lowest cost point

#include <bits/stdc++.h>

using namespace std;

#define N 100010

const long long inf = (long long)1e18;

int h[N];
int n, a, r, m;

long long calc(int lev) {
	long long put = 0;
	long long remove = 0;
	for(int i=0; i<n; i++) {
		if(h[i] <= lev) {
			put = put + lev - h[i];
		} else {
			remove = remove + h[i] - lev;
		}
	}
	// now, some elements to put, some to remove and some to move
	// the num of elements can be removed is cnt = min(put, remove) and
	// cnt element should be moved only when move cost(m) < put cost(a) + remove cost(r)
	// and other remaining should be removed or put just normally
	// so,
	long long cnt = min(put, remove);
	put -= cnt;
	remove -= cnt;
	return put * a + remove * r + cnt * min(a + r, m);
}

int main() {
	scanf("%d %d %d %d", &n, &a, &r, &m);
	for(int i=0; i<n; i++) {
		scanf("%d", &h[i]);
	}
	long long minCost = inf;
	int s = 0, e = (int)1e9; // height range 0...1e9
	while(s <= e) {
		int m = (s + e) / 2;
		long long costAtMid = calc(m);
		long long costJustAfterMid = calc(m + 1);
		if(costAtMid < costJustAfterMid) {
			minCost = min(costAtMid, minCost);
			// we've to go left to find the lowest point
			e = m - 1;
		} else {
			minCost = min(costJustAfterMid, minCost);
			// we've to go right to find the lowest point
			s = m + 1;
		}
	}
	printf("%lld\n", minCost);
	return 0;
}

<|start_filename|>graph/mst/loj/F1123/Solution.java<|end_filename|>
// problem_name: Trail Maintenance 
// problem_link: http://lightoj.com/volume_showproblem.php?problem=1123
// contest_link: (?)
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: medium


import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.PrintWriter;
 
import java.io.IOException;
 
import java.util.Collections;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
 
public class Solution {
    static Reader in;
    static PrintWriter out;
   
    static class Edge implements Comparable<Edge> {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
        public int compareTo(Edge e) { return this.w - e.w; }
    }
    static int[] p = new int[200];
    static int find(int i) { return (i == p[i]) ? i:(p[i] = find(p[i])); }
 
    static int n, cost;
    static int[][] adj = new int[200][200];
    static boolean[] visited = new boolean[200];
    static List<Edge> path = new ArrayList<>();
    static boolean dfs(int s, int e) {
        if(visited[s])  return false;
        visited[s] = true;
        if(s == e)  return true;
        for(int i=0; i<n; i++) {
            if(adj[s][i] != 0)  {
                if(dfs(i, e))   {
                    path.add(new Edge(s, i, adj[s][i]));
                    return true;
                }
            }
        }
        return false;
    }
    static void fix(int u, int v, int w) {
        for(int i=0; i<n; i++)  visited[i] = false;
        path.clear();
        dfs(u, v);
        Edge max = null;
        for(Edge e: path) {
            if(max == null) max = e;
            else {
                if(e.w > max.w) max = e;
            }
        }
        if(max.w <= w)  return;
        cost = cost + w - adj[max.u][max.v];
        adj[max.u][max.v] = 0;
        adj[max.v][max.u] = 0;
        adj[u][v] = w;
        adj[v][u] = w;
    }
    static void solve() throws IOException {
        int cc, tc, ne;
        int i, j, m, u, v, w;
 
        tc = in.nextInt();
        for(cc=0; cc<tc; cc++) {
            ne = 0;
            cost = 0;
            n = in.nextInt();
            m = in.nextInt();
            for(i=0; i<n; i++) {
                p[i] = i;
                for(j=0; j<n; j++)  adj[i][j] = 0;
            }
            out.println("Case " + (cc+1) +":");
            for(i=0; i<m; i++) {
                u = in.nextInt()-1;
                v = in.nextInt()-1;
                w = in.nextInt();
                if(find(u) != find(v)) {
                    p[find(u)] = find(v);
                    ne++;
                    cost += w;
                    adj[u][v] = w;
                    adj[v][u] = w;
                }
                else {
                    fix(u, v, w);
                }
                if(ne == n-1) out.println(cost);
                else out.println(-1);
            }
        }
    }
    public static void main(String[] args) {   
        try {
            OutputStreamWriter osw = new OutputStreamWriter(System.out);
            BufferedWriter bw = new BufferedWriter(osw);
            in = new Reader();
            out = new PrintWriter(bw);
 
            solve();
 
            in.close();
            out.close();
            bw.close();
            osw.close();
        }
        catch(IOException e) {
            e.printStackTrace();
        }
    }
    static class Reader {
        InputStreamReader isr;
        BufferedReader br;
        StringTokenizer tk;
        String str;
        Reader() {
            br = new BufferedReader((isr = new InputStreamReader(System.in)));
            tk = new StringTokenizer("");
        }
        String nextLine() throws IOException {
            while(((str = br.readLine()) != null) && (str.length() == 0));
            return str;
        }
        String next() throws IOException {
            if(!tk.hasMoreTokens()) {
                if(nextLine() == null)  return null;
                tk = new StringTokenizer(str);
            }
            return tk.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        void flush() {
            tk = new StringTokenizer("");
        }
        void close() throws IOException {
            br.close();
            isr.close();
        }
    }
}

<|start_filename|>greedy/basic/codeforces/F1506F/Solution.cpp<|end_filename|>
// problem name: Triangular Paths
// problem link: https://codeforces.com/contest/1506/problem/F
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: constructive algorithm, graph, math, sortings, shortest path
// difficulty_level: medium


// one of the worst problem description ever

#include <bits/stdc++.h>

using namespace std;


pair<int, int> p[200020];

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d", &p[i].first);
        }
        for(int i=0; i<n; i++) {
            scanf("%d", &p[i].second);
        }
        sort(p, p+n);
        if(p[0] != make_pair(1, 1)) {
            for(int i=n-1; i>=0; i--) {
                p[i+1] = p[i];
            }
            p[0] = {1, 1};
            n++;
        }
        long long ans = 0;
        for(int i=0; i<n-1; i++) {
            auto x = p[i];
            auto y = p[i+1];
            // i guess, we're moving down strictly and keeping the col same or going right
            // otherwise, this solution won't work
            // and the problem description would be proved to be incorrect
            assert(x.first < y.first && x.second <= y.second);
            if(x.first - x.second == y.first - y.second) { // in the same diagonal
                if(!((x.first - x.second)&1)) { // if even diagonal
                    ans = ans + (y.first - x.first);
                }
            } else {
                // just calculate the direct downward cost
                ans = ans + (y.first - y.second) / 2 - (x.first - x.second) / 2;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}


<|start_filename|>amortized_analysis/two_pointers/codeforces/F701C/Solution.cpp<|end_filename|>
// problem name: They Are Everywhere
// problem link: https://codeforces.com/contest/701/problem/C
// contest link: https://codeforces.com/contest/701
// time: (?)
// author: reyad

// other_tags: binary search, string
// difficulty_level: beginner

#include <bits/stdc++.h>

using namespace std;

#define N 100010

int c[128] = {0};
char s[N];
char u[128];
int k = 0;


set<char> unq;

int okay() {
	for(int i=0; i<k; i++) {
		if(!c[u[i]]) {
			return false;
		}
	}
	return true;
}
int main() {
	int n;
	scanf("%d %s", &n, s);
	for(int i=0; i<n; i++) {
		unq.insert(s[i]);
	}
	for(char it: unq) {
		u[k++] = it;
	}
	int i = 0, j = 0, d = 987654321;
	while(i < n) {
		if(!okay()) {
			c[s[i]]++;
			i++;
		} else {
			// printf("i, j: %d %d\n", i, j);
			d = min(d, (i-1)-j+1);
			c[s[j]]--;
			j++;
		}
	}
	while(j < n && okay()) {
		d = min(d, (n-1)-j+1);
		c[s[j]]--;
		j++;
	}
	printf("%d\n", d);
	return 0;
}

<|start_filename|>math/combinatorics/loj/F1102/Solution.cpp<|end_filename|>
// problem name: Problem Makes Problem
// problem link: http://lightoj.com/volume_showproblem.php?problem=1102
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: expert


#include <bits/stdc++.h>

using namespace std;


#define M 1000000007
#define N 2000000


long long f[N+10];

long long modpow(long long b, long long pw, long long mod) {
    if(pw == 0) {
        return 1;
    }
    long long x = modpow(b, pw/2, mod);
    x = (x * x) % mod;
    if(pw&1) x = (x * b) % mod;
    return x;
}

long long modinv(long long a, long long b, long long mod) {
    return (a * modpow(b, mod-2, mod)) % mod;
}

int main() {
    f[0] = 1;
    for(int i=1; i<=N; i++) {
        f[i] = (f[i-1] * i) % M;
    }

    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, k;
        scanf("%d %d", &n, &k);
        printf("Case %d: %lld\n", cc+1, modinv(f[n+k-1], (f[n] * f[k-1]) % M, M));
    }
    return 0;
}


<|start_filename|>search/binary_search/loj/F1100/Solution.cpp<|end_filename|>
// problem name: Again Array Queries
// problem link: http://lightoj.com/volume_showproblem.php?problem=1100
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: sorting, range query
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


vector<int> b[1024];


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        for(int i=1; i<=1000; i++){
            b[i].clear();
        }
        int n, q;
        scanf("%d %d", &n, &q);
        for(int i=0; i<n; i++) {
            int a;
            scanf("%d", &a);
            b[a].push_back(i);
        }
        printf("Case %d:\n", cc+1);
        for(int i=0; i<q; i++) {
            int l, r;
            scanf("%d %d", &l, &r);
            int prev = -2048;
            int ans = 2048;
            for(int j=1; j<=1000; j++) {
                int s = 0, e = b[j].size() - 1, x = -1;
                while(s <= e) {
                    int m = (s + e) / 2;
                    if(b[j][m] < l) {
                        s = m + 1;
                    } else {
                        x = m;
                        e = m - 1;
                    }
                }
                if(x != -1 && b[j][x] <= r) {
                    if(x < b[j].size()-1 && b[j][x+1] <= r) {
                        ans = 0;
                        break;
                    }
                    ans = min(ans, j - prev);
                    prev = j;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

<|start_filename|>greedy/non_classical/codeforces/F1506G/Solution.cpp<|end_filename|>
// problem name: Maximize the Remaining String
// problem link: https://codeforces.com/contest/1506/problem/G
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: brute force, data structures, dynamic programming, strings
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

char s[200020];
int stck[200020];


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        scanf("%s", s);
        int c[26] = {0};
        int unq = 0;
        for(int i=0; s[i]; i++) {
            int ch = s[i] - 'a';
            if(c[ch] == 0) {
                unq++;
            }
            c[ch]++;
        }
        char ans[32] = {0};
        int ansLen = 0;
        int start = 0;
        // printf("cc: %d\n", cc+1);
        while(unq > 0) {
            int mx = -1;
            int top = 0;
            for(int i=start; s[i]; i++) {
                int ch = s[i] - 'a';
                if(c[ch] == 0) {
                    continue;
                }
                if(ch > mx) {
                    mx = ch;
                    start = i + 1;
                }
                c[ch]--;
                stck[top++] = i;
                if(c[ch] == 0) {
                    break;
                }
            }
            // printf("%c ", (char)(mx + 'a'));
            assert(mx != -1);
            ans[ansLen++] = (char)(mx + 'a');
            // adjusting char counts and unq counts
            while(stck[--top] >= start) {
                c[s[stck[top]] - 'a']++;
            }
            c[mx] = 0;
            unq--;
        }
        printf("%s\n", ans);
    }
    return 0;
}


<|start_filename|>dynamic_programming/basic/codeforces/F1498D/Solution.cpp<|end_filename|>
// problem name: Bananas in a Microwave
// problem link: https://codeforces.com/contest/1498/problem/D
// contest link: https://codeforces.com/contest/1498
// time: (?)
// author: reyad


// other_tags: graph, dfs and similiar, implementation
// difficulty_level: intermediate


// solution idea:
// let,
// function calc(t, k, x):
//     return ceil(k + x) if t == 1 else return ceil(k * x)

// if d(i, k) is possible, then the followings are possible,
// let, kx = calc(t[i], k, x[i])
// - d(i, kx) if d(i, k)'s step is < y[i]
// - d(i+1, k)

#include <bits/stdc++.h>

using namespace std;

#define inf 1000000009
#define M 100010

long long x[M];
int t[M], y[M];
int dp[M], ans[M];

long long calc(int t, long long k, long long x) {
    if(t == 1) {
        return (k * 100000 + x + 99999) / 100000;
    }
    return (k * x + 99999) / 100000;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++) {
        scanf("%d %lld %d", &t[i], &x[i], &y[i]);
    }
    for(int i=0; i<=m; i++) {
        dp[i] = inf;
        ans[i] = -1;
    }
    dp[0] = ans[0] = 0;
    for(int i=0; i<=n; i++) {
        for(int k=0; k<=m; k++) {
            dp[k] = (ans[k] != -1) ? 0 : inf;
        }
        for(int k=0; k<=m; k++) {
            long long kx = calc(t[i], k, x[i]);
            if(kx <= m) {
                dp[kx] = min(dp[k]+1, dp[kx]);
            }
        }
        for(int k=0; k<=m; k++) {
            if(dp[k] <= y[i]) {
                if(ans[k] == -1) {
                    ans[k] = i;
                }
                // printf("%d ", k);
            }
        }
        // printf("\n");
    }
    for(int k=1; k<=m; k++) {
        printf("%d ", ans[k]);
    }
    printf("\n");
    return 0;
}


<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1355D/Solution.cpp<|end_filename|>
// problem name: Game With Array
// problem link: https://codeforces.com/contest/1355/problem/D
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: math
// difficulty_level: easy

// solution idea:
// observation-01: let avg = (S / N)
//                 if avg < 2, then its not possible to construct any solution
//                 cause, 1 would be present, at least once, and if not then multiple times
//                 which ensures that one can make any possible value between 1...S
// onservation-02: if avg >= 2, then:
//                 2, 2, ...2(n-1 times), S - (2 * (n-1)) could be a possible answer
//                 cause, the sum is S and 1 can't be made from any subarray


#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, s;
	scanf("%d %d", &n, &s);
	if(s < 2 * n) { // if avg is less than 2 i.e. between 1 <= avg < 2
		printf("NO\n");
	} else {
		printf("YES\n");
		for(int i=0; i<n-1; i++) {
			printf("2 ");
		}
		printf("%d\n", s - 2 * (n-1));
		printf("1\n");
	}
	return 0;
}

<|start_filename|>data_structure/array/codeforces/F1490F/Solution.cpp<|end_filename|>
// problem name: Equalize the Array
// problem link: https://codeforces.com/contest/1490/problem/F
// contest link: https://codeforces.com/contest/1490
// author: reyad
// time: (?)


// other_tags: sortings, math, binary search, greedy
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


#define N 200020

int a[N], c[N], b[N], s[N];


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d", &a[i]);
            c[i] = 0;
        }
        sort(a, a+n);
        int v = a[0];
        int cnt = 1;
        for(int i=1; i<n; i++) {
            if(a[i] == v) {
                cnt++;
            } else {
                c[i-1] = cnt;
                v = a[i];
                cnt = 1;
            }
        }
        c[n-1] = cnt;
        int bc = 0;
        for(int i=0; i<n; i++) {
            if(c[i] > 0) {
                b[bc++] = c[i];
            }
        }
        sort(b, b+bc);
        s[0] = b[0];
        for(int i=1; i<bc; i++) {
            s[i] = s[i-1] + b[i];
        }
        int mn = N;
        for(int i=bc-1; i>=0; i--) {
            int cost = s[bc-1] - (b[i] * (bc - i));
            mn = min(cost, mn);
        }
        printf("%d\n", mn);
    }
    return 0;
}


<|start_filename|>math/basic/codeforces/F1345C/Solution.cpp<|end_filename|>
// problem_name: <NAME>
// problem_link: https://codeforces.com/contest/1345/problem/C
// contest_link: https://codeforces.com/contest/1345
// time: (?)
// author: reyad

// other_tags: sorting
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		set<int> s;
		for(int i=0; i<n; i++) {
			int a;
			scanf("%d", &a);
			a = (a % n);
			if(a < n) a += n;
			s.insert((i + a) % n);
		}
		if((int)s.size() == n) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}

<|start_filename|>dynamic_programming/non_classical/codeforces/F1498C/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: https://codeforces.com/contest/1498/problem/C
// contest link: https://codeforces.com/contest/1498
// time: (?)
// author: reyad


// other_tags: brute force, data structure
// difficulty_level: easy


// solution idea:
// d(k, n-x) = d(k, n-x-1) + d(k-1, x)
// let, n-x = m
// so, d(k, m) = d(k, m-1) + d(k-1, n-m)

// base cases:
// 1. d(1, m) = 1
// 2. d(x, 0) = 1


#include <bits/stdc++.h>

using namespace std;

#define M 1000000007


long long dp[1024][1024];

long long calc(int k, int m, int n) {
    if((k == 1) || (m == 0)) {
        return 1;
    }
    if(dp[k][m] != -1) {
        return dp[k][m];
    }
    dp[k][m] = (calc(k, m-1, n) + calc(k-1, n-m, n)) % M;
    // printf("k, m, dp: %d %d %lld\n", k, m, dp[k][m]);
    return dp[k][m];
}

int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, k;
        scanf("%d %d", &n, &k);
        for(int i=0; i<=k; i++) {
            for(int j=0; j<=n; j++) {
                dp[i][j] = -1;
            }
        }
        long long ans = calc(k, n, n);
        printf("%lld\n", ans);
    }
    return 0;
}


<|start_filename|>hashing/string_hashing/codeforces_gym/F101466E/Solution.cpp<|end_filename|>
// problem name: Text Editor
// problem link: https://codeforces.com/gym/101466/problem/E
// contest link: https://codeforces.com/gym/101466
// time: (?)
// author: reyad

// other_tags: binary search, dp, string suffix structures, substring searching
// difficulty_level: medium

// note: this problem can be solved in multiple ways

#include <bits/stdc++.h>

using namespace std;

#define N 100010

char a[N], b[N];
int k, na, nb;

int count(int w) {
	long long int h = 0, eh = 0, hs = 0, pwm = 1, p = 47;
	int count = 0;
	for(int i=0; i<w; i++) hs = hs * p + (b[i] - 'a' + 1);
	for(int i=0; i<w; i++) pwm = pwm * p;
	for(int i=0; i<na; i++) {
		h = h * p + (a[i] - 'a' + 1);
		if(i >= w) eh = eh * p + (a[i-w] - 'a' + 1) * pwm;
		if(i >= w-1 && (eh + hs) == h) count++;
	}
	return count;
}

int main() {
	gets(a);
	gets(b);
	scanf("%d", &k);
	na = strlen(a);
	nb = strlen(b);
	int s = 1, e = nb, x = -1;
	while(s <= e) {
		int m = (s + e) / 2; // m represents length of prefix that we're counting
		int cnt = count(m);
		if(cnt >= k) {
			x = m;
			s = m + 1;
		} else {
			e = m - 1;
		}
	}
	if(x == -1) printf("IMPOSSIBLE\n");
	else {
		b[x] = '\0';
		printf("%s\n", b);
	}
	return 0;
}

<|start_filename|>greedy/basic/codeforces/F1355B/Solution.cpp<|end_filename|>
// problem name: Young Explorers
// problem link: https://codeforces.com/contest/1355/problem/B
// contest link: https://codeforces.com/contest/1355
// time: (?)
// author: reyad

// other_tags: sortings, dp
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;

#define N 200020

int c[N] = {0};

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		set<int> unq;
		for(int i=0; i<n; i++) {
			int e;
			scanf("%d", &e);
			c[e]++;
			unq.insert(e);
		}
		int rem = 0, g = 0;
		for(int e: unq) {
			int x = c[e] / e;
			g += x;
			rem += c[e] - x * e;
			if(rem >= e) {
				int y = rem / e;
				g += y;
				rem -= y * e;
			}
			c[e] = 0; // resetting
		}
		printf("%d\n", g);
	}
	return 0;
}

<|start_filename|>math/combinatorics/codeforces/F1091D/Solution.cpp<|end_filename|>
// problem name: New Year and the Permutation Concatenation
// problem link: https://codeforces.com/contest/1091/problem/D
// contest link: https://codeforces.com/contest/1091
// time: (?)
// author: reyad


// other_tags: dynamic programming
// difficulty_level: beginner

/**
 * Solution idea:
 * 1 2 3 4 -> 3
 * 1 2 4 3 -> 2
 * 1 3 2 4 -> 3
 * 1 3 4 2 -> 2
 * 1 4 2 3 -> 3
 * 1 4 3 2 -> 1
 * 2 1 3 4 -> 3
 * 2 1 4 3 -> 2
 * 2 3 1 4 -> 3
 * 2 3 4 1 -> 3
 * 2 4 1 3 -> 2
 * 2 4 3 1 -> 1
 * ...
 * ...
 *
 *
 * answer must be formed of an subarray which contains all the elements from 1, 2, ..., n
 * Observation says, there are two ways to form an answer
 * 1. each individual row (such as just the second row: `1 2 4 3`)
 * 2. start with ith position in xth row and expand to (i-1)th element of (x+1)th row
 *    (such as the second to third row, starting from 2: `2 4 3 1`)
 * 
 * (Also observation says)
 * check 1st and 2nd row closely, and check the position where it mismatches:
 * 1 2 3 4 (check the 3rd position, it gives 3)
 * 1 2 4 3 (check the 3rd position, it gives 4)
 * So, the first row will give `3` subarray which's sum = (n * (n+1)) / 2
 * check 2nd and 3rd array, and check the position where it mismatches:
 * 1 2 4 3 (check the 2nd position, it gives 2)
 * 1 3 2 4 (check the 2nd position, it gives 3)
 * So, 2nd row will give `2` subarray which's sum will be (n * (n+1)) / 2
 *
 * and so on...
 *
 * Now, observe the count of results(subarray those give sum (n * (n+1))/2) of each row
 * 1. `1` will appear [`n`] times i.e. `4` times in the example
 * 2. `2` will appear [`n * (n-1)` - no of times `1` appear] = n * (n-1) - n = `8` times
 * 3. `3` will appear [`n * (n-1) * (n-2)` - no of times `1` and `2` appear] = n * (n-1) * (n-2) - [n + (n * (n-1) - n)] = `12` times
 * 4. ans so on ...(if `n` is greater than `4` of course..., the example is only for `n=4`, so its stops at `step 3`)
 */

/**
 * To calculate answer:
 * let,
 * number of changes in 1st position is c_1 = n
 * number of changes in 2nd position is c_2 = n * (n-1) - c_1
 * number of changes in 3rd position is c_3 = n * (n-1) * (n-2) - (c_1 + c_2)
 * ...
 * ...
 * number of changes in rth position is c_r = n * (n-1) * ... * (n-(r-1)) - (c_1 + c_2 + ... + c_(r-1))
 *                                          = nPr - (c_1 + c_2 + ... + c_(r-1))
 *
 * so, the ans will be:
 * ans = 1 * c_1 + 2 * c_2 + 3 * c_3 + ... + (n-1) * c_(n-1)
 */


#include <bits/stdc++.h>

using namespace std;

#define M 998244353


int main() {
    long long n;
    scanf("%lld", &n);
    if(n == 1) {
        printf("1\n");
        return 0;
    }
    long long sum_of_c_rs = 0;
    long long nPr = 1;
    long long ans = 0;
    for(int r=1; r<n; r++) {
        nPr = (nPr * (n-(r-1))) % M;
        long long c_r = (nPr - sum_of_c_rs + M) % M;
        ans = (ans + (c_r * r) % M) % M;
        sum_of_c_rs = (sum_of_c_rs + c_r) % M;
    }
    printf("%lld\n", ans);
    return 0;
}


<|start_filename|>math/basic/codeforces/F1345A/Solution.cpp<|end_filename|>
// problem_name: Puzzle Pieces
// problem_link: https://codeforces.com/contest/1345/problem/A
// contest_link: https://codeforces.com/contest/1345
// time: (?)
// author: reyad

// other_tags: game
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


int main() {
	int tc;

	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, m;
		scanf("%d %d", &n, &m);

		if(n == 1 || m == 1) {
			printf("YES\n");
		} else {
			if(n <= 2 && m <= 2) {
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	}
	return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1353A/Solution.cpp<|end_filename|>
// problem name: Most Unstable Array
// problem link: https://codeforces.com/contest/1353/problem/A
// contest link: https://codeforces.com/contest/1353
// time: (?)
// author: reyad

// other_tags: greedy, math
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, m;
		scanf("%d %d", &n, &m);
		long long ans = 0;
		if(n == 1) {
			ans = 0LL;
		} else if(n == 2) {
			ans = m;
		} else {
			ans = 2LL * m;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

<|start_filename|>ad_hoc/implementation/codeforces/F1512A/Solution.cpp<|end_filename|>
// problem name: Spy Detected!
// problem link: https://codeforces.com/contest/1512/problem/A
// contest link: https://codeforces.com/contest/1512
// time: (?)
// author: reyad


// other_tags: brute force
// difficulty_level: beginner


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n;
        cin >> n;
        map<int, vector<int>> mp;
        for(int i=0; i<n; i++) {
            int a;
            cin >> a;
            mp[a].push_back(i);
        }
        for(auto it: mp) {
            if((int)it.second.size() == 1) {
                cout << it.second[0] + 1 << "\n";
                break;
            }
        }
    }
    return 0;
}


<|start_filename|>greedy/basic/codeforces/F1392C/Solution.cpp<|end_filename|>
// problem name: Omkar and Waterslide
// problem link: https://codeforces.com/contest/1392/problem/C
// contest link: https://codeforces.com/contest/1392
// author: reyad
// time: (?)


// other tags: implementation
// difficulty level: beginner


#include <bits/stdc++.h>

using namespace std;

int x[200020];
int a[200020];
int seen[200020];

bool cmp(int i, int j) {
	if(a[i] == a[j]) {
		return i < j;
	}
	return a[i] < a[j];
}

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n;
		scanf("%d", &n);
		for(int i=0; i<n; i++) {
			scanf("%d", &a[i]);
			x[i] = i;
			seen[i] = false;
		}
		sort(x, x + n, cmp);
		
		long long cost = 0;
		int i = 0;
		while(i < n) {
			if(!seen[i]) {
				if(x[i] == 0 || a[x[i]-1] <= a[x[i]]) {
					i++;
					continue;
				}
				int j = i+1;
				while(j < n && a[x[j]] == a[x[i]] && x[j] == x[j-1]+1) {
					seen[j] = true;
					j++;
				}
				cost = cost + a[x[i]-1] - a[x[i]];
				i = j;
			} else {
				i++;
			}
		}

		printf("%lld\n", cost);
	}
	return 0;
}

<|start_filename|>ad_hoc/constructive_algorithm/codeforces/F1350D/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: https://codeforces.com/contest/1350/problem/D
// contest link: https://codeforces.com/contest/1350
// time: (?)
// author: reyad

// other_tags: greedy
// difficulty_level: medium


// solution:
// >> let's denote l_k for number of elements less than k
//                 e_k for number of elements equal to k
//                 g_k for number of lements greater than k
// Now it can be shown that there's no solution if
// for every possible subarray which's length greater than 1 the following
// condition is true:
// l_k >= e_k + g_k .....(i)
// it's easy to realize that, if equation(i) holds, then k could never the middle element ever
// notice that: if we can solve it for any value greater than k, then its also solvable
// for k, if there's at least one k present in the array in any place
// notice: there's only two type of transitions, positive transition(when value >= e_k) and
// negative transition(when value <= k)

// see below an example graph:
//         _   _   _
// (i)   _| |_| |_| |_...
//
//
// (ii)  _          
//        |_       _
//          |_   _| |_...
//            |_|
//
//               _
//             _| |_
//           _|     |_...
//         _|
// (iii) _|
//
// (point-01) So it clearly shows that there could only be a solution if and only if
//            there's at least 2 positive transitions in a window of three transitions...
//            cause, then in a three window e_k + g_k > l_k would satisfied
// (point-02) As there's only positive or negative transitions, it can be showed that,
//            if there's no solution for a window of size 'w'( we are considering all possible 'w' size
//            windows) then there's no solution for 'w+1' size windows
// (point-03) for n == 1 and 2 solve it manually


#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define INF 12345678

int b[N];

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k, np = 0;
		scanf("%d %d", &n, &k);
		bool flag = false, seenK = false;
		for(int i=0; i<n; i++) {
			scanf("%d", &b[i]);
			seenK |= (b[i] == k);
			np += (b[i] >= k);
			if(i >= 3) np -= (b[i-3] >= k);
			if(np >= 2) {
				flag = true;
			}
		}
		if(seenK && (flag || (n == 1 && np == 1))) {
			// note: for n == 2, flag has to be on
			// cause, np should be equal to 2
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}
	return 0;
}

<|start_filename|>math/basic/codeforces/F1475B/Solution.cpp<|end_filename|>
// problem name: New Year's Number
// problem link: https://codeforces.com/contest/1475/problem/B
// contest link: https://codeforces.com/contest/1475/
// time: (?)
// author: reyad


// other_tags: dynamic programming, brute force
// difficulty_level: beginner


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int n;
        cin >> n;
        if(n < 2020) {
            cout << "NO\n";
            continue;
        }
        int q = n / 2020;
        int r = n - (2020 * q);
        if(r <= q) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}


<|start_filename|>graph/dfs/codeforces/F1363E/Solution.cpp<|end_filename|>
// problem name: Tree Shuffling
// problem link: https://codeforces.com/contest/1363/problem/E
// contest link: https://codeforces.com/contest/1363
// time: (?)
// author: reyad


// other_tags: data structures, greedy, sortings, trees
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

#define N 200010
#define INF 1000000007

vector<int> adj[N];
bool seen[N] = {0};
long long a[N];
int b[N];
int c[N];

long long minTotCost =0;

pair<int, int> dfs(int u, long long minCost) {
	seen[u] = true;
	pair<int, int> cnt = make_pair(0, 0);
	for(int v: adj[u]) {
		if(!seen[v]) {
			auto p = dfs(v, min(a[u], minCost));
			cnt.first += p.first;
			cnt.second += p.second;
		}
	}
	if(b[u] != c[u]) {
		if(c[u] == 0) cnt.first++;
		else cnt.second++;
	}
	if(a[u] <= minCost) {
		int k = min(cnt.first, cnt.second);
		minTotCost = minTotCost + 2LL * k * a[u];
		cnt.first -= k;
		cnt.second -= k;
	}
	return cnt;
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%lld %d %d", &a[i], &b[i], &c[i]);
	}
	for(int i=1; i<n; i++) {
		int u;
		int v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	auto p = dfs(1, INF);
	if(p.first == 0 && p.first == p.second) {
		printf("%lld\n", minTotCost);
	} else {
		printf("-1\n");
	}

	return 0;
}

<|start_filename|>math/combinatorics/loj/F1105/Solution.cpp<|end_filename|>
// problem name: Fi Binary Number 
// problem link: http://lightoj.com/volume_showproblem.php?problem=1105
// contest link: (?)
// time: (?)
// author: reyad


// other_tags: fibonacci
// difficulty_level: easy


#include <bits/stdc++.h>

using namespace std;


#define N 1000010
#define M 1000000000
 
int stck[128];
char str[128];
 
int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n;
        scanf("%d", &n);
        int top = 0;
        while(n > 0) {
            int a = 1, b = 2;
            int i = 1;
            while(b <= n) {
                int c = a + b;
                a = b;
                b = c;
                i++;
            }
            stck[top++] = i - 1;
            n = n - a;
        }
        int l = stck[0];
        for(int i=0; top > 0; i++) {
            if(i == stck[top-1]) {
                str[i] = '1';
                top--;
            } else {
                str[i] = '0';
            }
        }
        printf("Case %d: ", cc+1);
        for(int i=l; i>=0; i--) {
            printf("%c", str[i]);
        }
        printf("\n");
    }
    return 0;
}


<|start_filename|>search/binary_search/codeforces/F1363D/Solution.cpp<|end_filename|>
// problem name: Guess The Maximums
// problem link: https://codeforces.com/contest/1363/problem/D
// contest link: https://codeforces.com/contest/1363
// time: (?)
// author: reyad

// other_tags: implementation, interactive, math
// difficulty_level:

// note: this is a interactive problem. read problem description well, don't assume anything.


#include <bits/stdc++.h>

using namespace std;

char status[32];

int query(vector<int> &buf, bool ispw = false) {
	if(ispw) {
		printf("!");
	}
	else {
		printf("? %d", buf.size());
	}
	for(auto v: buf) {
		printf(" %d", v);
	}
	printf("\n");
	fflush(stdout);

	if(ispw) {
		scanf("%s", status);
		return 0;
	}
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	int tc;
	scanf("%d", &tc);
	for(int cc=0; cc<tc; cc++) {
		int n, k;
		scanf("%d %d", &n, &k);
		vector<vector<int>> subset(k);
		for(auto &it: subset) {
			int c;
			scanf("%d", &c);
			it.resize(c);
			for(auto &v: it) {
				scanf("%d", &v);
			}
		}
		vector<int> q;
		for(int i=1; i<=n; i++) {
			q.push_back(i);
		}
		int mx = query(q);
		int s = 0, e = k-1;
		while(s < e) {
			vector<int> q;
			int m = (s + e) / 2;
			for(int i=s; i<=m; i++) {
				for(auto v: subset[i]) {
					q.push_back(v);
				}
			}
			int x = ((q.size() > 0) ? query(q) : 0);
			if(x < mx) {
				s = m + 1;
			} else {
				e = m;
			}
		}
		set<int> mxSet(subset[s].begin(), subset[s].end());
		vector<int> qq;
		for(int i=1; i<=n; i++) {
			if(!mxSet.count(i)) {
				qq.push_back(i);
			}
		}
		int y = ((qq.size() > 0) ? query(qq) : 0);
		vector<int> p;
		for(int i=0; i<k; i++) {
			if(i != s) {
				p.push_back(mx);
			} else {
				p.push_back(y);
			}
		}
		query(p, true);
	}
	return 0;
}

<|start_filename|>hashing/string_hashing/codechef/FINSQ15_A/Solution.cpp<|end_filename|>
// problem name: The Gift Of <NAME>
// problem link: https://www.codechef.com/INSQ2015/problems/INSQ15_A
// contest link: https://www.codechef.com/INSQ2015
// time: (?)
// author: reyad

// other_tags:  binary-search, string suffix structures, strings
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;


#define N 5000010

char str[N];
long long int p = 647, pw[N], h[N];

int main() {
	scanf("%s", str);
	int l = strlen(str);
	h[0] = str[0] - 'a' + 1;
	pw[0] = 1;
	for(int i=1; i<l; i++) {
		pw[i] = pw[i-1] * p;
		h[i] = h[i-1] + (str[i] - 'a' + 1) * pw[i];
	}
	int q;
	scanf("%d", &q);
	for(int i=0; i<q; i++) {
		int k;
		scanf("%d", &k);
		int s = 0, e = k-1, x = -1;
		while(s <= e) {
			int m = (s + e) / 2;
			if((h[m] * pw[k]) + h[k-1] == h[k+m]) {
				x = m;
				s = m + 1;
			} else {
				e = m - 1;
			}
		}
		printf("%d\n", x+1);
	}
	return 0;
}

<|start_filename|>ad_hoc/implementation/codeforces/F1512C/Solution.cpp<|end_filename|>
// problem name: A-B Palindrome
// problem link: https://codeforces.com/contest/1512/problem/C
// contest link: https://codeforces.com/contest/1512
// time: (?)
// author: reyad


// other_tags: constructive algorithm, string
// difficulty_level: beginner


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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    for(int cc=0; cc<tc; cc++) {
        int a, b;
        cin >> a >> b;
        string s;
        cin >> s;
        // balance
        int n = a + b;
        for(int i=0; i<n; i++) {
            if(s[i] == '?' && s[n-i-1] != '?') {
                s[i] = s[n-i-1];
            }
        }
        // check if palindrome is maintained in current state
        int flag = 1;
        for(int i=0; i<n; i++) {
            if(s[i] != s[n-i-1]) {
                flag = 0;
                break;
            }
        }
        if(!flag) {
            cout << -1 << "\n";
            // cout << "here is unbalanced s: " << s << "\n";
            continue;
        }
        // reduce count of 0 and 1
        for(int i=0; i<n; i++) {
            if(s[i] == '0') {
                a--;
            }
            if(s[i] == '1') {
                b--;
            }
        }
        if(a < 0 || b < 0) {
            cout << -1 << "\n";
            // cout << "run out of stock: " << s << "\n";
            continue;
        }
        // get count of '?'
        int cq = 0;
        for(int i=0; i<n; i++) {
            if(s[i] == '?') {
                cq++;
            }
        }
        assert((a+b) == cq);
        if(!((a+b)&1) && (a&1)) {
            cout << -1 << "\n";
            // cout << "when even/odd mismatched: " << s << "\n";
            continue;
        }
        for(int i=0; i<n; i++) {
            if(s[i] == '?') {
                if(i == n-i-1) {
                    if(a == 1) {
                        s[i] = s[n-i-1] = '0';
                        a -= 1;
                    } else {
                        s[i] = s[n-i-1] = '1';
                        b -= 1;
                    }
                } else {
                    if(a > 1) {
                        s[i] = s[n-i-1] = '0';
                        a -= 2;
                    } else {
                        s[i] = s[n-i-1] = '1';
                        b -= 2;
                    }
                }
            }
        }
        // assert((a == 0) && (b == 0));
        cout << s << "\n";
    }
    return 0;
}


<|start_filename|>search/binary_search/codeforces/F1486D/Solution.cpp<|end_filename|>
// problem name: <NAME>
// problem link: https://codeforces.com/contest/1486/problem/D
// contest link: https://codeforces.com/contest/1486
// time: (?)
// author: reyad


// other_tags: data structure, dynamic programming
// difficulty_level: medium


#include <bits/stdc++.h>

using namespace std;

#define N 200020

int a[N], t[N], mn[N];


int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
    }
    mn[0] = t[0] = 0;
    int s = 0, e = n, p = -1;
    while(s <= e) {
        int m = (s + e) / 2;
        for(int i=1; i<=n; i++) {
            if(a[i] >= m) {
                t[i] = t[i-1] + 1;
            } else {
                t[i] = t[i-1] - 1;
            }
            mn[i] = min(mn[i-1], t[i]);
        }
        bool flag = false;
        for(int i=k; i<=n; i++) {
            if(t[i] - mn[i-k] > 0) {
                flag = true;
                break;
            }
        }
        if(flag) {
            p = m;
            s = m + 1;
        } else {
            e = m - 1;
        }
    }
    assert(p != -1);
    printf("%d\n", p);
    return 0;
}

<|start_filename|>data_structure/list/leetcode/F61/Solution.cpp<|end_filename|>
// problem name: Rotate List
// problem link: https://leetcode.com/problems/rotate-list/
// contest link: (?)
// time: (?)
// author: pri1311


// other_tags: (?)
// difficulty_level: beginner


/**
 * meta:
 *   - input: head = [1,2,3,4,5], k = 2
 *   - output: [4,5,1,2,3]
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* temp = head;
        int count = 0;
        while(temp){
            count++;
            temp = temp->next;
        }
        if (count == 0 || k == 0 || count == 1 || k % count == 0 ) return head;
        count -= (k%count);
        temp = head;
        ListNode * q = NULL;
        while (count--){
            q = temp;
            temp = temp->next;
        }
        q->next = NULL;
        ListNode * p;
        p = temp;
        while (temp->next && temp){
            temp = temp->next;
        }
        temp->next = head;
        return p;
    }
};


<|start_filename|>math/basic/codeforces/F1506A/Solution.cpp<|end_filename|>
// problem name: Strange Table
// problem link: https://codeforces.com/contest/1506/problem/A
// contest link: https://codeforces.com/contest/1506
// time: (?)
// author: reyad


// other_tags: (?)
// difficulty_level: beginner


#include <bits/stdc++.h>

using namespace std;


int main() {
    int tc;
    scanf("%d", &tc);
    for(int cc=0; cc<tc; cc++) {
        int n, m;
        long long x;
        scanf("%d %d %lld", &n, &m, &x);
        long long c = (x + n - 1) / n;
        long long r = x % n;
        if(r == 0) {
            r = n;
        }
        printf("%lld\n", m * (r-1) + c);
    }
    return 0;
}


<|start_filename|>hashing/set_hashing/codeforces/F154C/Solution.cpp<|end_filename|>
// problem name: Double Profiles
// problem link: https://codeforces.com/contest/154/problem/C
// contest link: https://codeforces.com/contest/154
// time: (?)
// author: reyad

// other_tags: graphs, sorting
// difficulty_level: expert


// solution idea:
// two possible cases:
// (case-01) when u and v are friend's
//         let u's friendlist be f(u) = {v, x, y, z}, a set;
//         let v's friendlist be f(v) = {u, x, y, z}, a set;
// Now, u and v would be duplicate if,
// f(u) - {v} == f(v) - {u}
// i.e. if their friendlist is same without including themselves(according to problem definition)
//
// (case-02) when u and v are not friend
//         let u's friendlist be f(u) = {x, y, z}, a set;
//         let v's friendlist be f(v) = {x, y, z}, a set;
// Now, in this case u and v would be friend if,
// f(u) == f(v)
// i.e. their friendlist totally same(according to problem definition)

// implementation idea:
// we can use hash to check if two sets are equal or not
// but the problem is removing an element from set(when u and v are friend)
// and then find the hash
// Now, the two solution to solve this issue:
// (01) first method:
//       - make graph using adjacency list
//       - sort adjacency list of each node
//       - use polynomial hash for each node to compute hash of neighbour/friend set
//       - first solve for case-02, calculate result for case-02
//       - insert 'u' into u's friendlist(for each node) in proper sorted position
//       - so, u's friendlist become f(u) = {u, v, x, y, z}, v's friendlist become
//         f(v) = {u, v, x, y, z} and so on..
//       - now, we can solve case-01 using the same procedure as case-02
//       - done
// (02) second method:
//       - notice: friendlist set consists of unique numbers i.e. no numbers twice
//       - so, we can use non-positional rolling hash in this case
//       - distribute 10^6 numbers in 10^18 numbers, so that their sum or xor of any set
//         always give use some unique result
//       - i've used xor in this case
//       - solve for case-01
//       - sort, then solve for case-02
//       - done


#include <bits/stdc++.h>

using namespace std;

#define N 1000010

#define B 1747591
#define P  479001599

long long int x[N], h[N];
int u[N], v[N];

int main() {
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	x[0] = P;
	for(int i=1; i<=n; i++) {
		x[i] = x[i-1] * B;
		h[i] = 0;
	}
	for(int i=0; i<m; i++) {
		scanf("%d %d", &u[i], &v[i]);
		h[u[i]] ^= x[v[i]];
		h[v[i]] ^= x[u[i]];
	}

	long long int cnt = 0;
	for(int i=0; i<m; i++) {
		if((h[u[i]] ^ x[v[i]]) == (h[v[i]] ^ x[u[i]])) cnt++;
	}

	sort(h+1, h+n+1);
	long long int c = 1;
	for(int i=2; i<=n; i++) {
		if(h[i] == h[i-1]) c++;
		else {
			cnt = cnt + ((1LL * c * (c-1)) / 2);
			c = 1;
		}
	}
	if(c) cnt = cnt + ((1LL * c * (c-1)) / 2);

	printf("%lld\n", cnt);
	return 0;
}