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

:city_sunset:
</center>

---
### `📝 notes`

last dance :cow2:

---

## progress report!

here's my progress in the [usaco.guide gold curriculum](https://usaco.guide/gold).

## `USACO Gold Topics`

- [x] Divisibility
- [x] Modular Arithmetic
- [x] Combinatorics
- [x] Intro to DP
- [x] Knapsack DP
- [x] Paths on Grids
- [x] LIS
- [x] Bitmask DP
- [ ] Range DP
- [x] BFS
- [x] DSU
- [ ] Top Sort
- [x] Shortest paths
- [x] MSTs
- [ ] Stacks
- [ ] Sliding Window
- [ ] PURS
- [ ] Euler Tour
- [x] DP on trees
- [ ] String hashing
- [ ] MITM
- [ ] Bitwise Ops

Unfortunately, there's still a lot I need to learn and grow upon.

## [BOX](https://atcoder.jp/contests/abc279/tasks/abc279_f)

Here's a really interesting problem.

There are $N$ boxes numbered $1\dots N$, and $10^{100}$ balls numbered $1 \dots 10^{100}$.

At the beginning, the $i$th box contains the $i$th ball.

Process $q$ queries, each being one of the following types.

**Type 1**
- They are given in the form of: ```1 x y```
- Put all the contents of box $y$ into box $x$.
- $x \neq y$

**Type 2**
- They are given in the form of: ```2 x```
- Put the ball numbered $k + 1$ into box $x$. Here, $k = \sum^{i<n}_{i=0} num_i$. Where $num_i$ represents the number of balls in box $i$.

**Type 3**
* They are given in the form of ```3 x```
* Report the number of the box that contains $x$

| **Constraints**
---
| $2 \leq n \leq 3 \times 10^5$ |
|$1 \leq q \leq 3 \times 10^5$ |
| There is at least one type $3$ operation |
---

### `solution`

Now, this problem seems realy far-fetched. How can we possibly process type $1$ and $2$ operations quickly?

First of all, let's analyze the worst case time complexity of the most straightforward approach.

Each box contains a vector, and we manually transfer balls in between them.

There are at most $n + q - 1$ balls that can exist, so in the worst case, we'd do $(n + q - 1)^2$ operations, which doesn't work.

But what if add on another constraint: $num_y < num_x$?

Then, after moving, the number of balls grows by at least $2$ times.

So, we'd only do $(n + q - 1) \times \log_2(n + q - 1)$ operations!

That's great, but how to we switch balls between boxes as quick as possible?

Let's add a middleman, a bag for each box, where all balls are stored in.

Then, we can switch the bags per box quickly, since swapping vectors is $\mathcal{O}(1)$.

That's enough the solve the problem.

We have to store $3$ arrays.

bag -> box

box -> bag

bag -> balls

### implementation:

#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, q;
	cin >> n >> q;
	// note that we want to place specific items into bags,
	// like connected components yk
	// so whenever we transfer, we ditch that bag, and start a new bag

	// how should we do this? we'll have at most n + q "bags"
	// and each bag will have a pointer to the respective box
	vector<int> bag_to_box(n);
	iota(bag_to_box.begin(), bag_to_box.begin() + n, 0);
	// and each ball has a pointer to the bag
	vector<int> ball_to_bag(n + q);
	iota(ball_to_bag.begin(), ball_to_bag.begin() + n, 0);
	// at first box i has bag i
	vector<int> box_to_bag(n);
	for (int i = 0; i < n; i++) box_to_bag[i] = i;

	vector<vector<int>> bag(n);
	for (int i = 0; i < n; i++) {
		bag[i].push_back(i);
	}

	int crball = n;

	for (int _ = 0; _ < q; _++) {
		int type;
		cin >> type;

		// new bag
		if (type == 1) {
			int x, y;
			cin >> x >> y;
			--x;
			--y;

			// y -> x
			// transfer ownership

			if (sz(bag[box_to_bag[x]]) < sz(bag[box_to_bag[y]])) {
				// cheaper to move from x -> y and swap
				for (int i : bag[box_to_bag[x]]) {
					bag[box_to_bag[y]].push_back(i);
					ball_to_bag[i] = box_to_bag[y];
				}
				bag[box_to_bag[x]].clear();
				swap(box_to_bag[x], box_to_bag[y]);
				bag_to_box[box_to_bag[x]] = x;
				bag_to_box[box_to_bag[y]] = y;

			} else {
				for (int i : bag[box_to_bag[y]]) {
					bag[box_to_bag[x]].push_back(i);
					ball_to_bag[i] = box_to_bag[x];
				}
				bag[box_to_bag[y]].clear();
			}
			// cout << x << " has bag " << box_to_bag[x] << endl;
			// cout << y << " has bag " << box_to_bag[y] << endl;
			// cout << bag[box_to_bag[x]] << endl;
			// cout << bag[box_to_bag[y]] << endl;

			// new balls
		} else if (type == 2) {
			int x;
			cin >> x;
			--x;
			ball_to_bag[crball++] = box_to_bag[x];
			bag[box_to_bag[x]].push_back(crball - 1);
			// qry
		} else {
			// what box has ball x
			int x;
			cin >> x;
			--x;
			// cout << "it's in bag " << ball_to_bag[x] << endl;
			cout << bag_to_box[ball_to_bag[x]] + 1 << endl;
		}
	}
}

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

This is also solvable using DSU, since it relies on the same small-to-large merging.

## [Factorial & Multiple](https://atcoder.jp/contests/abc280/tasks/abc280_d)

You are given an integer $K > 1$, find the minimum number $n$ such that $n! \equiv 0 \pmod k$.

| $k \leq 10^{12}$ |
---

---

### `solution`

Recall that in order for $x$ to be divisible by $y$, every prime in $x$'s prime factorization should be in $y$, and every exponent of these primes should also be $\geq$ than the other prime's exponent.

Thus, let's split up $k$ into it's prime factorization. Since the minimum value in factor pairs must be $< \sqrt{k}$, we can prime factorize in $\sqrt{k} \log k$. ($\log k$ can be dropped due to Big O)

Next, note that to satisfy the exponent, our factorial must also satisfy this.

$n! = 1 \times 2 \times \dots \times n$, so let's count this in order. Only multiples of $x$ will carry this exponent, so let's count.

$2$ contributes $2^1$
$4$ contributes $2^2$
$6$ contributes $2^1$

and so on.

Well, we know that the exponent can be at most $\log_2 k$, so this runs very quickly.

The "bottleneck" is in the prime factorization, so the time complexity is $\mathcal{O}(\sqrt{K})$

## [Critical Hit](https://atcoder.jp/contests/abc280/tasks/abc280_e)

There is a monster with stamina $n$. Each attack lowering the monster's stamina by $2$ with probability $\frac{p}{100}$, and by $1$ with probability $1 - \frac{p}{100}$.

Find the expected number of attacks to lower the monster's stamina $\leq 0$.

We expect that it takes $1$ move to lower the monster's stamina by (at least) $1$, and so we can form a recurrence relationship like this:
$$dp_i = dp_{i-2} \times \frac{p}{100} + dp_{i-1} \times (1 - \frac{p}{100}) + 1$$

This can be calculated on the fly in $\mathcal{O}(n)$.

#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;
}

const ll MOD = 998244353;
template <ll M>
struct modint {
	static ll _pow(ll n, ll k) {
		ll r = 1;
		for (; k > 0; k >>= 1, n = (n * n) % M)
			if (k & 1) r = (r * n) % M;
		return r;
	}

	ll v;
	modint(ll n = 0) : v(n % M) { v += (M & (0 - (v < 0))); }

	friend string to_string(const modint n) { return to_string(n.v); }
	friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
	friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
	template <typename T>
	explicit operator T() { return T(v); }

	friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
	friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
	friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
	friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
	friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
	friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }

	modint& operator+=(const modint n) {
		v += n.v;
		v -= (M & (0 - (v >= M)));
		return *this;
	}
	modint& operator-=(const modint n) {
		v -= n.v;
		v += (M & (0 - (v < 0)));
		return *this;
	}
	modint& operator*=(const modint n) {
		v = (v * n.v) % M;
		return *this;
	}
	modint& operator/=(const modint n) {
		v = (v * _pow(n.v, M - 2)) % M;
		return *this;
	}
	friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
	friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
	friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
	friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
	modint& operator++() { return *this += 1; }
	modint& operator--() { return *this -= 1; }
	modint operator++(int) {
		modint t = *this;
		return *this += 1, t;
	}
	modint operator--(int) {
		modint t = *this;
		return *this -= 1, t;
	}
	modint operator+() { return *this; }
	modint operator-() { return modint(0) -= *this; }

	modint pow(const ll k) const {
		return k < 0 ? _pow(v, M - 1 - (-k % (M - 1))) : _pow(v, k);
	}
	modint inv() const { return _pow(v, M - 2); }
};

using mi = modint<int(MOD)>;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, p;
	cin >> n >> p;

	vector<mi> ans(n + 1);
	ans[0] = 0;
	ans[1] = 1;

	for (int i = 2; i <= n; i++) {
		ans[i] = ((mi(p) / 100) * ans[i - 2] + (mi(100 - p) / 100) * ans[i - 1]) + 1;
	}
	cout << ans[n] << endl;
}

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

## [Pay or Receive](https://atcoder.jp/contests/abc280/tasks/abc280_f)
---

There are $n \leq 10^5$ towns and $m \leq 10^5$ roads. Each road is given as $x, y, w$, which connects $x \rightarrow y$ with weight $w$, and $y \rightarrow x$ with weight $-w$.

You are given $q \leq 10^5$ queries, each consisting of two integers, $u, v$.

Find the maximum weight you can possibly gain by traveling from $u$ to $v$.

If it's not possible, print `"nan"`, if you can make it infinitely high, print `"inf"`, otherwise print the maximum weight.

#### `solution`

At first, this seems outright impossible. How can we get the distance between two nodes in $\mathcal{O}(1)$ time?

Actually, this is pretty solvable if we remember that $d(x, y) = d(x, v) + d(v, y)$. If we root the graph at any point, we can quickly solve this.

However, how do we solve an infinitely high graph? Clearly, there has to be some cycle in the graph which continuosly generates a larger number than it started with. So, we should try to detect it.

In fact, note that if we walk around this "cycle" counter-clockwise, we can invert the positive/negativeness of the number. Thus, if any cycle gives a non-zero gain/loss, we can infinitely amp up the answer.

That's enough to solve the problem. We'll do $\mathcal{O}(n + m)$ precalculation and answer each query in $\mathcal{O}(1)$ time.

#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;
}

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {	// union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q;
	cin >> n >> m >> q;

	DSU dsu(n);
	vector<vector<pi>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;

		--a;
		--b;

		dsu.unite(a, b);
		adj[a].emplace_back(b, w);
		adj[b].emplace_back(a, -w);
	}
	vector<int> dst(n, -inf);
	vector<bool> ruhroh(n);

	auto bfs = [&](int cc) {
		// x, dst
		queue<pi> todo;
		todo.push({cc, 0});

		while (sz(todo)) {
			pi top = todo.front();
			todo.pop();

			for (pi v : adj[top.f]) {
				if (dst[v.f] == -inf) {
					dst[v.f] = top.s + v.s;
					todo.push({v.f, dst[v.f]});
				} else {
					// implies non-zero cycle
					if (dst[v.f] != top.s + v.s) {
						ruhroh[cc] = 1;
					}
				}
			}
		}
	};

	for (int i = 0; i < n; i++) {
		if (dsu.get(i) == i) {
			// root connected component i at 'i'
			bfs(i);
		}
	}
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;

		--a;
		--b;

		if (!dsu.same_set(a, b)) {
			cout << "nan" << endl;
		} else if (ruhroh[dsu.get(a)]) {
			cout << "inf" << endl;
		} else {
			cout << dst[b] - dst[a] << endl;
		}
	}
}

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