<center> <h1> week of 12/12 </h1>

here we go...
</center>

---
### `📝 notes`

USACO returns this friday.

---

## contest reflection ([cf round #837](https://codeforces.cc/contest/1771))

### performance:
horrible, i solved the first two problems, which were incredibly standard in the first 10 minutes. but died on implementation for p2 for the next hour.

if i was more focused on debugging problem 2, i could have probably solved problem 3.

nonetheless, it was enough to promote to the Pupil rank in CodeForces.

Which, for just participating in only $5$ contests, is just alright.

### problems:

#### hossam and combinatorics (https://codeforces.cc/contest/1771/problem/A)

simply find occurences of the min & max, and do $2 \cdot (\text{min} \cdot \text{max})$, if all elements are the same, do $n \cdot (n - 1)$.

remember to use long longs to avoid overflow.

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int, int> occ;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		occ[a[i]]++;
	}

	bool same = 1;
	for (int i = 1; i < n; i++) {
		if (a[i] != a[i - 1]) same = 0;
	}

	if (same) {
		cout << (n * (n - 1)) << endl;
		return;
	}

	sort(all(a));

	cout << (occ[a[0]] * occ[a.back()]) * 2 << endl;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

#### hossam and friends (https://codeforces.cc/contest/1771/problem/B)

we'll count subsegments, by the number of subsegments starting at $i$ for all $i$.

the longest we can go is, the min of all friends from $i \dots n$. we can precalculate a suffix array for this.

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

void solve() {
	int n, m;
	cin >> n >> m;

	vector<int> mini(n + 1, inf);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (u > v) swap(u, v);
		mini[u] = min(mini[u], v);
	}
	vector<int> back(n + 2, inf);
	for (int i = n; ~i; --i) {
		back[i] = min(back[i + 1], mini[i]);
	}

	int ans = 0;
	for (int i = 1; i < n; i++) {
		int len = back[i] - i - 1;
		if (back[i] == inf) {
			len = (n + 1) - i - 1;
		}
		// cout << i << ' ' << len << endl;
		// cout << i << ' ' << mini[i] << ' ' << len << endl;

		ans += len;
	}
	cout << ans + n << endl;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

#### hossam and trainees (https://codeforces.cc/contest/1771/problem/C)

we want to find if any two elements in the array have a $\text{gcd} > 1$.

the elements go up to $10^9$, and a property about the prime factorizations for a large number like $10^9$ is that the degree of a prime $> \sqrt{10^9}$ will only have a degree of one.

so, we'll just calcualate all primes up until $\sqrt{10^9}$, and check for prime factor occurences.

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

vector<bool> pp(32000 + 1);
vector<int> lst;
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int, int> occ;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j : lst) {
			if (a[i] % j == 0) {
				if (occ[j] > 0) {
					dbg(occ);
					cout << "YES" << endl;
					for (int k = i + 1; k < n; k++) cin >> a[k];
					return;
				}
				occ[j]++;
			}
			while (a[i] % j == 0) {
				a[i] /= j;
			}
		}
		if (a[i] > 1) {
			if (occ[a[i]] > 0) {
				dbg(occ);
				cout << "YES" << endl;
				for (int j = i + 1; j < n; j++) cin >> a[j];
				return;
			}
			occ[a[i]]++;
		}
	}

	cout << "NO" << endl;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	pp[0] = pp[1] = true;
	for (int i = 2; i * i <= (int)(32000); i++) {
		if (!pp[i]) {
			for (int j = i * i; j <= (int)(32000); j += i) pp[j] = true;
		}
	}
	for (int i = 2; i <= (int)(32000); i++) {
		if (!pp[i]) lst.push_back(i);
	}
	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

#### [hossam and (sub-)palindromic tree](https://codeforces.cc/contest/1771/problem/D)

Consider storing the answer for some interval in $dp_{l,r}$. Where $l$ and $r$ represent the left and right endpoints in the interval, respectively.

Then, our transitions would be:
$$
dp_{l,r} = \left\{\begin{array}{lr}
dp(l + 1, r - 1) + 2, & s_l = s_r\\
\max(dp_{l+1,r}, dp_{l, r-1}), & s_l \neq s_r\\
\end{array}\right\}
$$

That's pretty simple, especially since we're allotted $\mathcal{O}(n^2)$, the only caveat being that we have to find these intervals on a tree.

In order to process this, we'll compute distances between every pair of nodes.

Then, between two nodes $l, r$. $l + 1$ will simply be the node that's adjacent to $l$ which is closer to $r$ than $l$.

The only special case is if $l = r$, then $dp_{l,r} = 1$.

time complexity: $\mathcal{O}(n^2)$.

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;

	vector<vector<int>> adj(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		--u;
		--v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// first compute distances o(n^2)

	vector<vector<int>> dist(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		function<void(int u, int par)> dfs = [&](int u, int par) {
			for (int v : adj[u]) {
				if (v == par) continue;

				dist[i][v] = (par == -1 ? 0 : dist[i][u]) + 1;
				dfs(v, u);
			}
		};

		dfs(i, -1);
		dbg(i, dist[i]);
	}

	// bfs
	vector<vector<int>> dp(n, vector<int>(n, -1));

	queue<pi> todo;
	for (int i = 0; i < n; i++) todo.push({i, i});

	while (!todo.empty()) {
		pi top = todo.front();
		todo.pop();
		if (dp[top.f][top.s] != -1) continue;
		int xmm = -1, ymm = -1;
		// <- l, r ->
		for (int i : adj[top.f]) {
			if (dist[i][top.s] < dist[top.f][top.s]) {
				xmm = i;
				break;
			}
		}
		for (int i : adj[top.s]) {
			if (dist[i][top.f] < dist[top.f][top.s]) {
				ymm = i;
				break;
			}
		}
		if (top.f == top.s) {
			dp[top.f][top.s] = 1;
			dp[top.s][top.f] = dp[top.f][top.s];
		} else {
			dp[top.f][top.s] = max({dp[top.f][top.s], dp[xmm][top.s], dp[top.f][ymm]});
			if (s[top.f] == s[top.s]) {
				dp[top.f][top.s] = max(dp[top.f][top.s], max(0, dp[xmm][ymm]) + 2);
			}
			dp[top.s][top.f] = dp[top.f][top.s];
		}

		for (int i : adj[top.f]) {
			if (i != xmm) todo.push({i, top.s});
		}
		for (int i : adj[top.s]) {
			if (i != ymm) todo.push({top.f, i});
		}
	}
	int ans = 1;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

#### hossam and a letter

we have a $400 \times 400$ grid, and we have to find the largest "H" that can be constructed given that it cannot contain any "#"s, and can only contain one "m".

this is another common "construct the largest letter" type of problem.

for this problem, we'll find the maximum height a stick can go up at $(i,j)$ for all $(i, j)$, and also the maximum height going down. we'll also add an extra dimension of size two to dictate whether we've already used our "m."

then, for all $(i, j)$, we'll stem a stick starting at $(i, j)$, and the second one at $(i, j + k)$.

Then, the total amount used is $2(\min(up_{i,j}, up_{i,j+k}) + \min(down_{i,j}, down_{i,j+k})) + k$. If we haven't used the "m" on the horizontal, we'll use it on either the up or the down.

// midsummer madness, i can't take it no more
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m;
	cin >> n >> m;

	vector<vector<char>> v(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}

	vector<vector<vector<int>>> up(n, vector<vector<int>>(m, vector<int>(2)));
	vector<vector<vector<int>>> down(n, vector<vector<int>>(m, vector<int>(2)));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// vertical line stemming from (i, j)

			// up
			int pp = i - 1;
			int md = 0;

			while (~pp) {
				if (v[pp][j] == 'm') md++;
				if (v[pp][j] == '#') break;
				if (md > 1) break;

				up[i][j][1] = max(up[i][j][1], i - pp);
				if (md == 0) {
					up[i][j][0] = max(up[i][j][0], i - pp);
				}
				pp--;
			}

			pp = i + 1;
			md = 0;

			while (pp < n) {
				if (v[pp][j] == 'm') md++;
				if (v[pp][j] == '#') break;
				if (md > 1) break;

				down[i][j][1] = max(down[i][j][1], pp - i);
				if (md == 0) {
					down[i][j][0] = max(down[i][j][0], pp - i);
				}

				pp++;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j + 2 < m; j++) {
			// draw line starting from (i, j)
			if (v[i][j] == '#' || v[i][j + 1] == '#') continue;

			int md = (v[i][j] == 'm') + (v[i][j + 1] == 'm');

			// extend rightward
			for (int k = j + 2; k < m; k++) {
				if (v[i][k] == 'm') md++;
				if (v[i][k] == '#') break;
				if (md > 1) break;

				// use md up, down, or center

				if (md == 1) {
					// force
					int mup = min(up[i][j][0], up[i][k][0]);
					int mdown = min(down[i][j][0], down[i][k][0]);

					if (mup && mdown) {
						ans = max(
								ans,
								2 * (mup + mdown) + (k - j + 1));
					}
				} else {
					// up
					int fs = max(min(up[i][j][0], up[i][k][1]), min(up[i][j][1], up[i][k][0]));
					int mdown = min(down[i][j][0], down[i][k][0]);
					if (fs && mdown) {
						ans = max(
								ans,
								2 * (fs + mdown) + (k - j + 1));
					}
					dbg(ans, i, k);
					// down
					int mup = min(up[i][j][0], up[i][k][0]);
					fs = max(min(down[i][j][0], down[i][k][1]), min(down[i][j][1], down[i][k][0]));
					if (mup && fs) {
						ans = max(
								ans,
								2 * (fs + mup) + (k - j + 1));
					}
				}
			}
		}
	}
	cout << ans << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

#### lucky chains

here, we have to find the longest "lucky" chain that starts with $a, b$.

a lucky chain is described a chain of $(a,b), (a+1, b+1), (a+2, b+2), \dots, (a+k, b+k)$, where all pairs $a, b$ have a GCD of $1$.

Answer $n \leq 10^6$ queries.

##### `solution`

wlog assume that $b > a$,

remember that the idea behind Euclid's GCD Algorithm relies on the fact that $\gcd(a, b) = \gcd(a, b-a)$.

thus, $\gcd(a+k,b+k) = \gcd(b - a, a + k)$.

we just have to find the smallest $k$.

obviously, $a + k \equiv 0 \pmod{d}$, where $d$ is a divisor of $b - a$. (actually we only need to consider prime factors).

and so, we'll just find the closest multiple of $d$ greater than $a + k$, and subtract $a$.

There are at most $\log_2(n)$ prime divisors of $n$.

We'll calculate this with eratosthenes' sieve and
slightly alter it to store the maximum prime divisor.

Also if $b-a = 1$, then the answer is $-1$, since it can be extended infinitely.

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

vector<int> isp(1e7 + 1, -1);

void solve() {
	int a, b;
	cin >> a >> b;
	if (__gcd(a, b) > 1) {
		cout << 0 << endl;
	} else if (a % 2 && b % 2) {
		cout << 1 << endl;
	} else if (abs(a - b) == 1) {
		cout << -1 << endl;
	} else {
		int dd = abs(a - b);
		ll ans = inf;
		while (isp[dd] != -1) {
			ll mlt = ((a + isp[dd] - 1) / isp[dd]) * isp[dd];

			ans = min(ans, mlt - a);
			dd /= isp[dd];
		}
		cout << ans << endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = 2; i <= (int)(1e7); i++) {
		if (isp[i] == -1) {
			for (int j = i; j <= (int)(1e7); j += i) {
				if (isp[j] == -1) isp[j] = i;
			}
		}
	}

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

alright, im gonna start the December USACO Contest now.

GLHF!