<center> <h1> week of 1/23 </h1>

</center>

---
### `📝 notes`

usaco returns this friday :scream:

---

## USACO Mock

There was a third-party mock contest this weekend that was really bad.

(let m)

Here's my analysis.

### P1:

#### problem:

#### solution:

note that we don't really care about the indices of the query, only the length, because if we shift the window one over, we'll keep the same number of distinct elements.

now, given this information, we have two cases to handle.

$a$ overlaps $b$, in this case, we can imagine giving $a$ all $(r-l+1)$ indices, and $b$, $b+(r-l+1) - a$.

$a$ doesn't overlap $b$, then they both get $(r-l+1)$

this motivates us to use a difference array, we just have to find the number of elements that exceed $(r-l+1)$, and multiply that by $(r-l+1)$, and add $\texttt{pref}[i] + (r-l+1)$, where $i$ represents the first index in the sorted difference array where $\texttt{diff}_i < (r-l+1)$, and $\texttt{pref}_i$ represents the prefix sum of the sorted difference array.

comments: overall, pretty ok problem, a little on the easier side though >.<

### p2:

#### problem:


#### solution:

note that the values of each element are only up to $10^6$, which is a little fishy...

why would they do this?

the possibilties for a sum are $2 \cdot 10^6$, so, if there are $n^2$ possible pairs, then by the pigeonhole principle, we're bound to run into a repeat if $n$ is large enough.

we can just implement a brute force $n^2$ algorithm with early return.

comments: this would never appear on a usaco contest ! plus this problem was stolen from codeforces

### p3:

#### problem:

#### solution:

first of all, it's clear that $b$ must be a subset of $a$ because if not, some divisor would be different for the two currencies.

thus, we just have to find how many values "require" a number (there's no other denomination that will make that value achievable).

this is just standard knapsack DP.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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 f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

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

    set<int> uwu;
    for (int i = 0; i < n; i++) uwu.insert(a[i]);

    vector<bool> ori(lg + 1, 0);
    ori[0] = 1;

    set<int> need;
    for (int i = 1; i <= lg; i++) {
        int cnt = -1;

        for (int k : uwu) {
            if (i - k >= 0) {
                if (ori[i - k]) {
                    if (cnt == -1)
                        cnt = k;
                    else
                        cnt = -2;
                }
                ori[i] = ori[i] || ori[i - k];
            }
        }
        if (cnt >= 0) {
            need.insert(cnt);
        }
    }

    cout << sz(need) << 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
// math it out
// ok well X is always possible, how about X + 1 (etc.)

comments: knapsack would never show up on usaco silver either :face_with_rolling_eyes:

## Moo Particle
### problem:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1040

### solution:

consider an undirected graph where edges are constructed if two particles can interact.

then, if we take the spanning tree, root at a leaf, and walk through the tree, we can make the entire tree only contain one particle at the end.

thus, we just have to find how to construct these connected components in $\mathcal{O}(n)$, (note there could be $n^2$ edges!)

consider sorting by $x$, then for a value $i$ to be in the connected component, some $j<i$ must satisfy $y_j \leq y_i$, or some $j > i$ must satisfy $y_j \geq y_i$.

we can precompute suffix maximums and keep a running minimum.

## Rectangular Pasture

http://www.usaco.org/index.php?page=viewproblem2&cpid=1063

### brief:
given a $N \leq 2500$ 2D points, find the number of subsets that you can form a rectangle around them.

### solution:

well since $N \leq 2500$, this could imply a $N^2$ solution.

let's try fixing the left and right sides $(i,j)$ of the rectangle, then the number of subsets we can make with these two sides fixed are the number of points above $\max(y_i,y_j)$, let's call it $a$, and the number of points below $\min(y_i,y_j)$, let's call it $b$.

we can just choose the ones above or the ones below, so...

$ab + a+b$ is our formula.

we'll calculate the number above and below with 2D prefix sums, or just $n$ prefix sums :/

---

## Mike and Geometry Problem

https://codeforces.cc/contest/689/problem/E
### problem
Given $n$ intervals, count the size of intersection between all possible groups of size $k \pmod {10^9+7}$.

### solution
let $dp_x$ be the number of points which intersect $x$ segments, then the answer is simply $x \choose k$$\times dp_x$ for each $x$.

we'll calculate this using prefix sum on map.

note that we should precompute factorials mod $10^9 + 7$.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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 f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

const int MOD = 1e9 + 7;

template <ll M>
struct modint {
	// bin exp, use binary to calculate powers -- in o(log n) instead
	// sprinkle in a little FLT to calculate via prime mods
	// a^(n-1) = 1 mod n, so rewrite original n^k as n^(\lfloor k/(n-1) \rfloor) * n^(k%(n-1)), reduce left side to 1, and we have the same equation
	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)>;
#define int ll

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

	int n, k;
	cin >> n >> k;
	vector<mi> fact(n + 1);
	fact[0] = 1;

	for (int i = 1; i <= n; i++) {
		fact[i] = fact[i - 1] * i;
	}

	function<mi(int N, int K)> C = [&](int N, int K) {
		if (K > N) return mi{0};
		return (fact[N]) / (fact[K] * (fact[N - K]));
	};

	map<int, int>
			pref;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		pref[a]++;
		pref[b + 1]--;
	}

	int ps = 0;
	mi ans = 0;
	pi prev = *pref.begin();
	for (auto& x : pref) {
		int dist = x.f - prev.f;
		ans += C(ps, k) * dist;

		ps += x.s;
		prev = x;
	}
	cout << ans.v << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

## Xenia and Bit Operations

https://codeforces.cc/contest/339/problem/D

### problem

read the problem statement! it's pretty concise.

### solution

note that ideally, we should be answering each query in $\mathcal{O}(\log n)$ or faster.

this hints at a segtree approach.

since bitwise OR and XOR are associative, we can keep those values on a seg tree.

we'll simply check the parity of $\log_2(n)$ to check which operation we'll do last, and recursively build the tree from there.

note that every update query will only at most affect $\log_2(n)$ nodes in the segment tree.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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 f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

vector<int> t;
vector<int> a;
void build(int v, int tl, int tr, bool type) {
	if (tl == tr) {
		t[v] = a[tl];
	} else {
		int mid = (tl + tr) / 2;

		build(v * 2, tl, mid, !type);
		build(v * 2 + 1, mid + 1, tr, !type);

		if (type) {
			t[v] = t[v * 2] | t[v * 2 + 1];
		} else {
			t[v] = t[v * 2] ^ t[v * 2 + 1];
		}
	}
}
void update(int v, int tl, int tr, bool type, int pos, int nv) {
	if (tl == tr) {
		t[v] = nv;
	} else {
		int mid = (tl + tr) / 2;
		if (pos <= mid) {
			update(v * 2, tl, mid, !type, pos, nv);
		} else {
			update(v * 2 + 1, mid + 1, tr, !type, pos, nv);
		}

		if (type) {
			t[v] = t[v * 2] | t[v * 2 + 1];
		} else {
			t[v] = t[v * 2] ^ t[v * 2 + 1];
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	n = (1 << n);
	t.assign(4 * n + 1, 0);
	a.assign(n + 1, 0);
	for (int i = 0; i < n; i++) cin >> a[i];
	int type = __lg(n) % 2;
	build(1, 0, n - 1, type);

	for (int i = 0; i < q; i++) {
		int pos, chg;
		cin >> pos >> chg;
		--pos;
		update(1, 0, n - 1, type, pos, chg);
		cout << t[1] << endl;
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

## Ehab the Xorcist

https://codeforces.cc/contest/1325/problem/D

### problem

find the minimum length sequence such that the length of the sequence is minimum, and the XOR of all the numbers equals $u$, and the sum equals $v$.

### solution

first of all, the following relationships are imposisble:

* $u > v$, the XOR never changes by more than the sum of values
* $u \neq v \pmod 2$, XOR and addition work the same for the last bit, so any sum that reaches $v$ not have the same $2^0$ bit as $u$

now, let's try to see if some construction always works.

since $x \oplus x = 0$, $\{u, \frac{v-u}{2}, \frac{v-u}{2}\}$ always works, so we'll just have to find if it's possible with strictly two elements.

remember that:

$$a + b = a \oplus b + 2(a\&b)$$

and we'll reduce. $a \oplus b = u$, so

$$a + b = u + 2(a\&b)$$

and that means $(a\&b) = \frac{v-u}{2}$!

$$a + b = u + 2(\frac{v-u}{2})$$

we'll just check if this satisfies the xor properties, and otherwise, output our $3$ element construction.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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 f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

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

	ll u, v;
	cin >> u >> v;

	if (u == v && !v) {
		cout << 0 << endl;
	} else if (u == v) {
		cout << 1 << endl
				 << u << endl;
	} else if (u > v || u % 2 != v % 2) {
		cout << -1 << endl;
	} else if (((v - u) / 2 ^ (v - ((v - u) / 2))) == u) {
		cout << 2 << endl;
		cout << (v - u) / 2 << ' ' << v - (v - u) / 2 << endl;
	} else {
		cout << 3 << endl;
		cout << (v - u) / 2 << ' ' << (v - u) / 2 << ' ' << u << endl;
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)