Initial commit

53 files changed, 2768 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..600d2d3
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+.vscode
\ No newline at end of file
diff --git a/2015/day1/comehome.cpp b/2015/day1/comehome.cpp
new file mode 100644
index 0000000..e9c72db
--- /dev/null
+++ b/2015/day1/comehome.cpp
@@ -0,0 +1,44 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+#define int long long
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+ii dist[100001], src[100001];
+vector<ii> G[100001];
+
+signed main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N, M, K; cin >> N >> M >> K;
+	while (M--) {
+		int A, B, D; cin >> A >> B >> D;
+		G[A].emplace_back(D, B), G[B].emplace_back(D, A);
+	}
+
+	priority_queue<ii, vector<ii>, greater<ii>> pq;
+	memset(dist, '?', sizeof dist);
+	for (int i = 1; i <= K; ++i) dist[i] = ii(0, 0), pq.emplace(0, i);
+	while (pq.size()) {
+		int d = pq.top().f, u = pq.top().s;
+		pq.pop();
+		if (d > dist[u].s) continue;
+		for (auto & p : G[u]) {
+			int d = p.f, v = p.s;
+			if ((dist[u].s + d == dist[v].f && src[v].f == u) || (dist[u].s + d == dist[d].s && src[v].s == u)) continue;
+			if (dist[u].s + d <= dist[v].f) {
+				dist[v].s = dist[v].f, src[v].s = src[v].f;
+				dist[v].f = dist[u].s + d, src[v].f = u;
+				pq.emplace(dist[v].s, v);
+			}
+			else if (dist[u].s + d <= dist[v].s) {
+				dist[v].s = dist[u].s + d, src[v].s = u;
+				pq.emplace(dist[v].s, v);
+			}
+		}
+	}
+
+	cout << (dist[N].s <= 1e18 ? dist[N].s : -1) << '\n';
+}
\ No newline at end of file
diff --git a/2015/day3/camelot.cpp b/2015/day3/camelot.cpp
new file mode 100644
index 0000000..ea96663
--- /dev/null
+++ b/2015/day3/camelot.cpp
@@ -0,0 +1,71 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+const int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
+const int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
+
+int d[44][44];
+bool b[44][44];
+inline int & dist(int i, int j) { return d[i + 22][j + 22]; }
+inline bool & vis(int i, int j) { return b[i + 22][j + 22]; }
+
+ii P[202];
+int dp[202][101];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N, R, C;
+	cin >> N >> R >> C;
+	for (int i = 0; i < N; ++i) {
+		cin >> P[i].f >> P[i].s;
+		--P[i].f, --P[i].s;
+	}
+
+	// BFS to compute distances
+	auto valid = [&R, &C](int i, int j) { return i > -R && i < R && j > -C && j < C; };
+	dist(0, 0) = 0;
+	queue<ii> q;
+	q.emplace(0, 0);
+	while (q.size()) {
+		ii u = q.front();
+		q.pop();
+		if (vis(u.f, u.s)) continue;
+		vis(u.f, u.s) = 1;
+		for (int d = 0; d < 8; ++d) {
+			ii v(u.f + dx[d], u.s + dy[d]);
+			if (valid(v.f, v.s) && !vis(v.f, v.s)) {
+				dist(v.f, v.s) = dist(u.f, u.s) + 1;
+				q.push(v);
+			}
+		}
+	}
+
+	// O(R^2 * C^2 * N^2)
+	int ans = 1e9;
+	for (int a = 0; a < R; ++a) {
+		for (int b = 0; b < C; ++b) {
+			for (int c = a; c < R; ++c) {
+				for (int d = 0; d < C; ++d) {
+					if (a == c && b == d) continue;
+					// First meetup location: (a, b)
+					// Second meetup location: (c, d)
+					memset(dp, '?', sizeof dp);
+					dp[0][0] = 0;
+					for (int i = 0; i < N; ++i) {
+						for (int j = 0; j <= min(i, N / 2); ++j) {
+							dp[i + 1][j] = min(dist(P[i].f - a, P[i].s - b) + dp[i][j], dp[i + 1][j]);
+							dp[i + 1][j + 1] = min(dist(P[i].f - c, P[i].s - d) + dp[i][j], dp[i + 1][j + 1]);
+						}
+					}
+					ans = min(dp[N][N / 2], ans);
+				}
+			}
+		}
+	}
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2016/day1/tractor.cpp b/2016/day1/tractor.cpp
new file mode 100644
index 0000000..6318ff7
--- /dev/null
+++ b/2016/day1/tractor.cpp
@@ -0,0 +1,30 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int w[55], v[55], dp[55][1001];
+vector<int> G[55];
+
+void dfs(int i) { 
+	dp[i][v[i]] = w[i];
+	for (int j : G[i]) {
+		dfs(j);
+		for (int k = 1000; k >= 0; --k) {
+			for (int l = k; l >= 0; --l) dp[i][k] = min(dp[i][l] + dp[j][k - l], dp[i][k]);
+		}
+	}
+	dp[i][0] = 0;
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	int N, W; cin >> N >> W;
+	for (int i = 1, p; i <= N; ++i) {
+		cin >> w[i] >> v[i] >> p;
+		G[p].push_back(i);
+	}
+	memset(dp, '?', sizeof dp);
+	dfs(0);
+	int ans = 1000;
+	while (dp[0][ans] > W) --ans;
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2016/day3/lct.cpp b/2016/day3/lct.cpp
new file mode 100644
index 0000000..77961fe
--- /dev/null
+++ b/2016/day3/lct.cpp
@@ -0,0 +1,38 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ii = pair<int, int>;
+template<typename T> class fenwick_tree {
+private: vector<T> FT;
+public:
+	fenwick_tree(int N) { FT.assign(N + 1, 0); }
+	void update(int x, T val) { if (x > 0) for (; x < FT.size(); x += x & -x) FT[x] += val; }
+	T query(int x) { T ret = 0; if (x > 0) for (; x > 0; x -= x & -x) ret += FT[x]; return ret; }
+	T query(int x, int y) { return query(y) - query(x - 1); }
+};
+
+int N, Q, ans[200002];
+ii E[200002];
+pair<ii, int> q[200002];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	cin >> N >> Q;
+	fenwick_tree<int> FT(N);
+	for (int i = 0; i < N - 1; ++i) {
+		cin >> E[i].f >> E[i].s;
+		if (E[i].f > E[i].s) swap(E[i].f, E[i].s);
+		FT.update(E[i].s, 1);
+	}
+	for (int i = 0; i < Q; ++i) {
+		cin >> q[i].f.f >> q[i].f.s; q[i].s = i;
+	}
+	sort(E, E + N - 1), sort(q, q + Q);
+	for (int i = 0, j = 0; i < Q; ++i) {
+		while (j < N - 1 && E[j].f < q[i].f.f) FT.update(E[j++].s, -1);
+		ans[q[i].s] = q[i].f.s - q[i].f.f + 1 - FT.query(q[i].f.s);
+	}
+	for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
+}
\ No newline at end of file
diff --git a/2016/day3/nickname.cpp b/2016/day3/nickname.cpp
new file mode 100644
index 0000000..7e28696
--- /dev/null
+++ b/2016/day3/nickname.cpp
@@ -0,0 +1,58 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+vector<int> suffix_array(string& S) {
+	int N = S.length();
+	vector<int> SA(N), rank(N);
+	for (int i = 0; i < N; i++) {
+		SA[i] = N - i - 1;
+		rank[i] = S[i];
+	}
+	stable_sort(SA.begin(), SA.end(), [&S](int i, int j) { return S[i] < S[j]; });
+	for (int t = 1; t < N; t <<= 1) {
+		vector<int> tmp(rank);
+		for (int i = 0; i < N; i++) {
+			bool s = i && SA[i - 1] + t < N && tmp[SA[i]] == tmp[SA[i - 1]] && tmp[SA[i] + (t >> 1)] == tmp[SA[i - 1] + (t >> 1)];
+			rank[SA[i]] = s ? rank[SA[i - 1]] : i;
+		}
+		tmp = SA;
+		vector<int> cnt(N);
+		for (int i = 0; i < N; i++) cnt[i] = i;
+		for (int i = 0; i < N; i++) {
+			if (tmp[i] >= t) SA[cnt[rank[tmp[i] - t]]++] = tmp[i] - t;
+		}
+	}
+	return SA;
+}
+
+vector<int> lcp_array(const vector<int>& SA, string& S) {
+	int N = S.size();
+	vector<int> rank(N), LCP(N - 1);
+	for (int i = 0; i < N; i++) rank[SA[i]] = i;
+	int pre = 0;
+	for (int i = 0; i < N; i++) {
+		if (rank[i] < N - 1) {
+			int j = SA[rank[i] + 1];
+			while (max(i, j) + pre < S.size() && S[i + pre] == S[j + pre]) pre++;
+			LCP[rank[i]] = pre;
+			if (pre > 0) pre--;
+		}
+	}
+	return LCP;
+}
+
+int main() {
+	int A, B;
+	string X, Y;
+	cin >> A >> B >> X >> Y;
+	string S = X + '$' + Y;
+	vector<int> SA = suffix_array(S);
+	vector<int> L = lcp_array(SA, S);
+	int ans = 0;
+	for (int i = 0; i < S.size() - 1; ++i) {
+		if ((SA[i] < A && SA[i + 1] > A) || (SA[i] > A && SA[i + 1] < A)) {
+			ans = max(L[i], ans);
+		}
+	}
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2016/day4/iqtest.cpp b/2016/day4/iqtest.cpp
new file mode 100644
index 0000000..0f55c58
--- /dev/null
+++ b/2016/day4/iqtest.cpp
@@ -0,0 +1,48 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int N, K, A[400004];
+
+inline ll pw(ll base, ll exp) {
+	ll res = 1;
+	while (exp) {
+		if (exp & 1) res = base * res % K;
+		exp >>= 1, base = base * base % K;
+	}
+	return res;
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	
+	cin >> N >> K;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+
+	ll phi = K, tmp = K;
+	vector<int> factors, exp;
+	for (int i = 2; i * i <= K; ++i) {
+		if (tmp % i == 0) {
+			while (tmp % i == 0) tmp /= i;
+			factors.push_back(i), exp.push_back(0);
+			phi = phi * (i - 1) / i;
+		}
+	}
+	if (tmp > 1) {
+		factors.push_back(tmp), exp.push_back(0);
+		phi = phi * (tmp - 1) / tmp;
+	}
+
+	ll cur = 1, ans = A[0];
+	for (int i = 1; i < N; ++i) {
+		ll x = N - i, y = i;
+		for (int j = 0; j < factors.size(); ++j) {
+			while (x % factors[j] == 0) ++exp[j], x /= factors[j];
+			while (y % factors[j] == 0) --exp[j], y /= factors[j];
+		}
+		ll tmp = cur = x * pw(y, phi - 1) % K * cur % K;
+		for (int j = 0; j < factors.size(); ++j) tmp = pw(factors[j], exp[j]) * tmp % K;
+		ans = (tmp * A[i] + ans) % K;
+	}
+	cout << ans;
+}
\ No newline at end of file
diff --git a/2017/day1/arboreal.cpp b/2017/day1/arboreal.cpp
new file mode 100644
index 0000000..659216b
--- /dev/null
+++ b/2017/day1/arboreal.cpp
@@ -0,0 +1,85 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+#define f first
+#define s second
+using namespace std;
+using namespace __gnu_pbds;
+using ii = pair<int, int>;
+template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
+constexpr int MAXN = 100001;
+
+vector<int> T[MAXN + 1];
+ordered_set<int> S[4 * MAXN + 4];
+
+void build(int l = 0, int r = MAXN, int n = 1) {
+	if (l == r) {
+		for (auto& y : T[l]) S[n].insert(y);
+	}
+	else {
+		int m = (l + r) >> 1;
+		build(l, m, n << 1), build(m + 1, r, n << 1 | 1);
+		for (auto& y : S[n << 1]) S[n].insert(y);
+		for (auto& y : S[n << 1 | 1]) S[n].insert(y);
+	}
+}
+
+int query(int xl, int xr, int yl, int yr, int l = 0, int r = MAXN, int n = 1) {
+	if (l > r || l > xr || r < xl) return 0;
+	if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl);
+	else {
+		int m = (l + r) >> 1;
+		return query(xl, xr, yl, yr, l, m, n << 1) + query(xl, xr, yl, yr, m + 1, r, n << 1 | 1);
+	}
+}
+ 
+ii P[100001];
+ 
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N; cin >> N;
+	for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s;
+ 
+	vector<ii> tmp;
+	for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].f, i);
+	sort(begin(tmp), end(tmp));
+	for (int i = 0; i < N; ++i) {
+		if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].f = P[tmp[i - 1].s].f;
+		else P[tmp[i].s].f = i;
+	}
+	tmp.clear();
+	for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].s, i);
+	sort(begin(tmp), end(tmp));
+	for (int i = 0; i < N; ++i) {
+		if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].s = P[tmp[i - 1].s].s;
+		else P[tmp[i].s].s = i;
+	}
+	
+	for (int i = 0; i < N; ++i) T[P[i].f].push_back(P[i].s);
+	build();
+	
+	vector<ii> X, Y;
+	for (int i = 0; i < N; ++i) X.push_back(P[i]), Y.push_back(P[i]);
+ 
+	auto cmpy = [](const ii & a, const ii & b) { return a.s < b.s || (a.s == b.s && a.f < b.f); };
+	sort(begin(X), end(X));
+	sort(begin(Y), end(Y), cmpy);
+	unique(begin(X), end(X));
+	unique(begin(Y), end(Y), cmpy);
+ 
+	int ans = 0;
+	for (int i = 0; i < N; ++i) {
+		auto it = lower_bound(begin(X), end(X), ii(P[i].f, P[i].s));
+		int yh = (next(it) != end(X) && next(it)->f == P[i].f ? next(it)->s : MAXN + 1);
+		int yl = (it != begin(X) && prev(it)->f == P[i].f ? prev(it)->s : -2);
+ 
+		it = lower_bound(begin(Y), end(Y), ii(P[i].f, P[i].s), cmpy);
+		int xh = (next(it) != end(Y) && next(it)->s == P[i].s ? next(it)->f : MAXN + 1);
+		int xl = (it != begin(Y) && prev(it)->s == P[i].s ? prev(it)->f : -2);
+ 
+		int q = query(xl + 1, xh - 1, yl + 1, yh - 1);
+		if (q > 1) ++ans;
+	}
+	cout << ans << '\n';
+}
diff --git a/2017/day1/ingrass.cpp b/2017/day1/ingrass.cpp
new file mode 100644
index 0000000..984fe20
--- /dev/null
+++ b/2017/day1/ingrass.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+ii P[50005];
+
+bool ccw(ii a, ii b, ii c) { return (ll)(b.f - a.f) * (c.s - a.s) - (ll)(c.f - a.f) * (b.s - a.s) > 0; }
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	int N; cin >> N;
+	for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s;
+	int m = min_element(P, P + N) - P;
+	vector<pair<double, int>> A;
+	for (int i = 0; i < N; ++i) {
+		if (i != m) A.emplace_back(atan2(P[i].s - P[m].s, P[i].f - P[m].f), i);
+	}
+	sort(begin(A), end(A));
+	vector<int> S;
+	vector<ii> ans;
+	for (int i = 0; i < A.size(); ++i) {
+		ans.emplace_back(m, A[i].s);
+		while (i) {
+			ans.emplace_back(A[i].s, S.back());
+			if (S.size() <= 1 || ccw(P[A[i].s], P[S[S.size() - 2]], P[S.back()])) break;
+			else S.pop_back();
+		}
+		S.push_back(A[i].s);
+	}
+	cout << 3 * N - 2 * S.size() - 4 << ' ' << ans.size() << '\n';
+	for (auto& p : ans) cout << p.f + 1 << ' ' << p.s + 1 << '\n';
+}
\ No newline at end of file
diff --git a/2017/day1/palindrome.cpp b/2017/day1/palindrome.cpp
new file mode 100644
index 0000000..dbf5fd6
--- /dev/null
+++ b/2017/day1/palindrome.cpp
@@ -0,0 +1,30 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int N, s[100001], dp[100001][606];
+inline int & get(int i, int j) { return dp[i][N - j - i + 301]; }
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> s[i];
+
+	memset(dp, '?', sizeof dp);
+	get(0, N) = 0;
+	for (int i = 0; i < N; ++i) {
+		for (int j = min(N - i + 300, N); j >= max(N - i - 300, i); --j) {
+			get(i + 1, j) = min(get(i, j) + 1, get(i + 1, j));
+			get(i, j - 1) = min(get(i, j) + 1, get(i, j - 1));
+			if (s[i] == s[j - 1]) get(i + 1, j - 1) = min(get(i, j), get(i + 1, j - 1));
+		}
+	}
+
+	int ans = 1e9;
+	for (int i = 0; i < N; ++i) {
+		if (N - 2 * i + 301 >= 0 && N - 2 * i + 301 < 606) ans = min(get(i, i), ans);
+		if (N - 2 * i + 300 >= 0 && N - 2 * i + 300 < 606) ans = min(get(i, i + 1), ans);
+	}
+	if (ans <= 300) cout << ans << '\n';
+	else cout << "many\n";
+}
\ No newline at end of file
diff --git a/2017/day2/cookie.cpp b/2017/day2/cookie.cpp
new file mode 100644
index 0000000..d03e72f
--- /dev/null
+++ b/2017/day2/cookie.cpp
@@ -0,0 +1,37 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using pl = pair<ll, ll>;
+
+ll C[5005], D[5005];
+pl DP[5005][5005];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	ll N, T, RA, RB;
+	cin >> N >> T >> RA >> RB;
+	for (int i = 0; i < N; ++i) cin >> C[i];
+	for (int i = 0; i < N; ++i) cin >> D[i];
+	
+	memset(DP, 63, sizeof(DP));
+	DP[0][0] = pl(0, 0);
+	ll ans = T;
+	for (int i = 0; i <= N; ++i) {
+		for (int j = 0; j <= N; ++j) {
+			ll r = 1 + i * RA + j * RB;
+			if (i < N) {
+				ll t = max((C[i] + DP[i][j].s + r - 1) / r, 0ll);
+				DP[i + 1][j] = min(pl(DP[i][j].f + t, -t * r + C[i] + DP[i][j].s), DP[i + 1][j]);
+			}
+			if (j < N) {
+				ll t = max((D[j] + DP[i][j].s + r - 1) / r, 0ll);
+				DP[i][j + 1] = min(pl(DP[i][j].f + t, -t * r + D[j] + DP[i][j].s), DP[i][j + 1]);
+			}
+			ans = min(DP[i][j].f + max((T + DP[i][j].s + r - 1) / r, 0ll), ans);
+		}
+	}
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2017/day2/lazybubblesort.cpp b/2017/day2/lazybubblesort.cpp
new file mode 100644
index 0000000..8395298
--- /dev/null
+++ b/2017/day2/lazybubblesort.cpp
@@ -0,0 +1,20 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int A[100001];
+
+int main() {
+	int N, K; cin >> N >> K;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+	multiset<int> S;
+	vector<int> ans;
+	for (int i = 0; i < N; ++i) {
+		if (S.size() < K || A[i] > *begin(S)) {
+			if (S.size() == K) ans.push_back(*begin(S)), S.erase(begin(S));
+			S.insert(A[i]);
+		}
+		else ans.push_back(A[i]);
+	}
+	while (S.size()) ans.push_back(*begin(S)), S.erase(begin(S));
+	for (auto& x : ans) cout << x << '\n';
+}
\ No newline at end of file
diff --git a/2017/day3/balancing.cpp b/2017/day3/balancing.cpp
new file mode 100644
index 0000000..c5fa7c6
--- /dev/null
+++ b/2017/day3/balancing.cpp
@@ -0,0 +1,23 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	string S; cin >> S;
+	int N = S.size(), cnt = 0;
+	if (count(begin(S), end(S), 'G') << 1 != N) {
+		cout << "NO\n";
+		return 0;
+	}
+	unordered_set<int> M[2];
+	for (int i = 0; i < N; ++i) {
+		if (S[i] != S[(i-1+N)%N]) M[S[i] == 'G'].insert(cnt);
+		cnt += (S[i] == 'G' ? 1 : -1);
+		if (S[i] != S[(i+1)%N] && M[S[i] == 'G'].find(cnt - (S[i] == 'G' ? 1 : -1)) != end(M[S[i] == 'G'])) {
+			cout << "YES\n";
+			return 0;
+		}
+	}
+	cout << "NO\n";
+	return 0;
+}
\ No newline at end of file
diff --git a/2017/day3/timeline.cpp b/2017/day3/timeline.cpp
new file mode 100644
index 0000000..a6b8e30
--- /dev/null
+++ b/2017/day3/timeline.cpp
@@ -0,0 +1,41 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ii = pair<int, int>;
+
+int dist[5005];
+vector<ii> G[5005];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+	int N, M, C; cin >> N >> M >> C;
+	for (int u = 1; u <= N; ++u) {
+		int s, t; cin >> s >> t;
+		G[u].emplace_back(-s, 0);
+		G[0].emplace_back(t, u);
+	}
+	while (C--) {
+		int a, b, x; cin >> a >> b >> x;
+		G[a].emplace_back(-x, b);
+	}
+	memset(dist, '?', sizeof dist);
+	dist[0] = 0;
+	for (int i = 0; i < N; ++i) {
+		for (int u = 0; u <= N; ++u) {
+			for (auto& v : G[u]) {
+				if (dist[u] + v.f < dist[v.s]) dist[v.s] = dist[u] + v.f;
+			}
+		}
+	}
+	for (int u = 0; u <= N; ++u) {
+		for (auto& v : G[u]) {
+			if (dist[u] < 0 || dist[u] > M || dist[u] + v.f < dist[v.s]) {
+				cout << "impossible\n";
+				return 0;
+			}
+		}
+	}
+	for (int u = 1; u <= N; ++u) cout << dist[u] << '\n';
+	return 0;
+}
\ No newline at end of file
diff --git a/2017/day4/knights.cpp b/2017/day4/knights.cpp
new file mode 100644
index 0000000..784abfc
--- /dev/null
+++ b/2017/day4/knights.cpp
@@ -0,0 +1,91 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+constexpr ll INF = 1e12;
+ 
+int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
+int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
+char A[101][101];
+ 
+template<int V, class T = ll> class max_flow {
+	struct edge {
+		int t, rev;
+		T cap, f;
+	};
+	vector<edge> adj[V];
+	int dist[V];
+	int ptr[V];
+	bool bfs(int s, int t) {
+		memset(dist, -1, sizeof dist);
+		dist[s] = 0;
+		queue<int> q({ s });
+		while (!q.empty() && dist[t] == -1) {
+			int n = q.front();
+			q.pop();
+			for (auto& e : adj[n]) {
+				if (dist[e.t] == -1 && e.cap != e.f) {
+					dist[e.t] = dist[n] + 1;
+					q.push(e.t);
+				}
+			}
+		}
+		return dist[t] != -1;
+	}
+	T augment(int n, T amt, int t) {
+		if (n == t) return amt;
+		for (; ptr[n] < adj[n].size(); ptr[n]++) {
+			edge& e = adj[n][ptr[n]];
+			if (dist[e.t] == dist[n] + 1 && e.cap != e.f) {
+				T flow = augment(e.t, min(amt, e.cap - e.f), t);
+				if (flow != 0) {
+					e.f += flow;
+					adj[e.t][e.rev].f -= flow;
+					return flow;
+				}
+			}
+		}
+		return 0;
+	}
+public:
+	void add(int u, int v, T cap = 1, T rcap=0) {
+		adj[u].push_back({ v, (int) adj[v].size(), cap, 0 });
+		adj[v].push_back({ u, (int) adj[u].size() - 1, rcap, 0 });
+	}
+	T calc(int s, int t) {
+		T flow = 0;
+		while (bfs(s, t)) {
+			memset(ptr, 0, sizeof ptr);
+			while (T df = augment(s, INF, t)) flow += df;
+		}
+		return flow;
+	}
+	void clear() {
+		for (int n = 0; n < V; n++) adj[n].clear();
+	}
+};
+ 
+int main() {
+	int R, C; 
+	cin >> R >> C;
+	int ans = R * C;
+	for (int i = 0; i < R; ++i) {
+		for (int j = 0; j < C; ++j) cin >> A[i][j];
+	}
+ 
+	max_flow<101*101> MF;
+	for (int i = 0; i < R; ++i) {
+		for (int j = 0; j < C; ++j) {
+			if (A[i][j] == '#') { --ans; continue; }
+			if (i + j & 1) {
+				MF.add(10000, i * C + j, (A[i][j] == 'C' ? INF : 1));
+				for (int d = 0; d < 8; ++d) {
+					int x = i + dx[d], y = j + dy[d];
+					if (x < 0 || x >= R || y < 0 || y >= C || A[x][y] == '#') continue;
+					MF.add(i * C + j, x * C + y, INF);
+				}
+			}
+			else MF.add(i * C + j, 10001, (A[i][j] == 'C' ? INF : 1));
+		}
+	}
+	cout << ans - MF.calc(10000, 10001) << '\n';
+}
\ No newline at end of file
diff --git a/2017/day4/stock_trading.cpp b/2017/day4/stock_trading.cpp
new file mode 100644
index 0000000..c2aa679
--- /dev/null
+++ b/2017/day4/stock_trading.cpp
@@ -0,0 +1,21 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N, L;
+	cin >> N >> L;
+
+	multiset<ll> S;
+	ll ans = 0;
+	for (int i = 0, b, s; i < N; ++i) {
+		cin >> b >> s;
+		ans = max(ans - (i >= L ? *begin(S) : 0) + s, ans);
+		S.insert({ b, s });
+		if (i >= L) S.erase(begin(S)), S.erase(prev(end(S)));
+	}
+	for (auto it = S.begin(); L; ++it, --L) ans -= *it;
+	cout << ans << endl;
+}
\ No newline at end of file
diff --git a/2017/day4/tuning.cpp b/2017/day4/tuning.cpp
new file mode 100644
index 0000000..d2bddd9
--- /dev/null
+++ b/2017/day4/tuning.cpp
@@ -0,0 +1,22 @@
+#include <bits/stdc++.h>
+using namespace std;
+ 
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+ 
+	int N;
+	cin >> N;
+	int ans = 1, cnt = 1;
+	for (int i = 2; i < N; ++i) {
+		if (cnt) {
+			cout << ans << ' ' << i << endl;
+			string s; cin >> s;
+			s[0] == 'S' ? ++cnt : --cnt;
+		}
+		else {
+			ans = i;
+			++cnt;
+		}
+	}
+	cout << (cnt ? ans : N) << endl;
+}
\ No newline at end of file
diff --git a/2017/day5/trip.cpp b/2017/day5/trip.cpp
new file mode 100644
index 0000000..35ded67
--- /dev/null
+++ b/2017/day5/trip.cpp
@@ -0,0 +1,41 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+vector<ii> G[100001];
+unordered_map<int, ll> A[100001], B[100001];
+ 
+ll dfs(int u, int p) {
+	sort(begin(G[u]), end(G[u]));
+	ll ret = 0, sa = 1, tmp = 0, l = -1;
+	++A[u][0], ++B[u][1e9+7];
+	for (auto& v : G[u]) {
+		if (v.s != p) {
+			ret += dfs(v.s, u);
+			ll ca = 0, cb = 0;
+			for (auto& x : A[v.s]) {
+				if (x.f < v.f) ca += x.s, A[u][v.f] += x.s;
+			}
+			for (auto& x : B[v.s]) {
+				if (x.f > v.f) cb += x.s, B[u][v.f] += x.s;
+			}
+			ret += cb * sa, sa += ca;
+			if (v.f != l) l = v.f, tmp = ca;
+			else ret -= cb * tmp, tmp += ca;
+		}
+	}
+	return ret + sa - 1;
+}
+ 
+int main() {
+	int N;
+	cin >> N;
+	for (int i = 1, a, b, e; i < N; ++i) {
+		cin >> a >> b >> e;
+		G[a].emplace_back(e, b), G[b].emplace_back(e, a);
+	}
+	cout << dfs(1, 0) << '\n';
+}
\ No newline at end of file
diff --git a/2018/day1/fanfiction.cpp b/2018/day1/fanfiction.cpp
new file mode 100644
index 0000000..82c06c1
--- /dev/null
+++ b/2018/day1/fanfiction.cpp
@@ -0,0 +1,85 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+int N, T, c[2552], f[2552], g[2552][26], G[2552][26];
+ll out[2552], dp[2552][2552];
+string B, S[2552];
+
+int aho_corasick() {
+	memset(g, -1, sizeof g), memset(out, 0, sizeof out);
+	int nodes = 1;
+	for (int i = 0; i < N; i++) {
+		int cur = 0;
+		for (int j = 0; j < S[i].size(); j++) {
+			if (g[cur][S[i][j] - 'a'] == -1) g[cur][S[i][j] - 'a'] = ++nodes;
+			cur = g[cur][S[i][j] - 'a'];
+		}
+		++out[cur];
+	}
+	for (int ch = 0; ch < T; ch++) {
+		if (g[0][ch] == -1) g[0][ch] = 0;
+	}
+	memset(f, -1, sizeof f);
+	queue<int> q;
+	for (int ch = 0; ch < T; ch++) {
+		if (g[0][ch] != 0) {
+			f[g[0][ch]] = 0;
+			q.push(g[0][ch]);
+		}
+	}
+	while (!q.empty()) {
+		int state = q.front();
+		q.pop();
+		for (int ch = 0; ch < T; ch++) {
+			if (g[state][ch] == -1) continue;
+			int fail = f[state];
+			while (g[fail][ch] == -1) fail = f[fail];
+			f[g[state][ch]] = g[fail][ch];
+			out[g[state][ch]] += out[g[fail][ch]];
+			q.push(g[state][ch]);
+		}
+	}
+	return nodes;
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	cin >> N >> T;
+	for (int i = 0; i < N; ++i) cin >> S[i];
+	cin >> B;
+	int L = B.size();
+	for (int i = 0; i < L; ++i) cin >> c[i];
+
+	int M = aho_corasick();
+
+	for (int i = 0; i < M; ++i) {
+		for (int j = 0; j < T; ++j) {
+			int k = i;
+			while (g[k][j] == -1) k = f[k];
+			G[i][j] = g[k][j];
+		}
+	}
+
+	memset(dp, '?', sizeof dp);
+	dp[0][0] = 0;
+	for (int i = 0; i < L; ++i) {
+		for (int j = 0; j < M; ++j) {
+			if (!out[j]) {
+				for (int k = 0; k < T; ++k) {
+					dp[i + 1][G[j][k]] = min(dp[i][j] + c[i] * (k != B[i] - 'a'), dp[i + 1][G[j][k]]);
+				}
+			}
+		}
+	}
+
+	ll ans = 1e18;
+	for (int i = 0; i < M; ++i) {
+		if (!out[i]) ans = min(dp[L][i], ans);
+	}
+	cout << (ans < 1e18 ? ans : -1) << '\n';
+}
\ No newline at end of file
diff --git a/2018/day1/grazing.cpp b/2018/day1/grazing.cpp
new file mode 100644
index 0000000..dcc8a79
--- /dev/null
+++ b/2018/day1/grazing.cpp
@@ -0,0 +1,62 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+typedef vector<int> vi;
+typedef vector<ii> vii;
+
+const int dx[] = { 1, 0, -1, 0 };
+const int dy[] = { 0, 1, 0, -1 };
+
+int N, M, A[11][11], vis[11][11];
+vi G[11][11];
+vii S;
+
+bool valid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; };
+
+void dfs(int i, int j) {
+	vis[i][j] = -1;
+	for (auto& d : G[i][j])
+		if (!vis[i + dx[d]][j + dy[d]]) dfs(i + dx[d], j + dy[d]);
+	vis[i][j] = 1;
+	S.emplace_back(i, j);
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+
+    cin >> N >> M;
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < M; ++j) cin >> A[i][j];
+	}	
+
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < M; ++j) {
+			for (int d = 0; d < 4; ++d) {
+				if (valid(i + dx[d], j + dy[d]) && A[i + dx[d]][j + dy[d]] <= A[i][j])
+					G[i][j].push_back(d);
+			}
+		}
+	}
+
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < M; ++j) {
+			if (!vis[i][j]) dfs(i, j);
+		}
+	}
+
+	memset(vis, 0, sizeof vis);
+	int ans = 0;
+	for (int i = S.size() - 1; i >= 0; --i) {
+		ii p = S[i];
+		ans += A[p.f][p.s];
+		for (int d = 0; d < 4; ++d) {
+			if (valid(p.f + dx[d], p.s + dy[d]) && vis[p.f + dx[d]][p.s + dy[d]])
+				ans += A[p.f + dx[d]][p.s + dy[d]];
+		}
+		vis[p.f][p.s] = 1;
+	}
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2018/day1/tastyhay.cpp b/2018/day1/tastyhay.cpp
new file mode 100644
index 0000000..8ef6d42
--- /dev/null
+++ b/2018/day1/tastyhay.cpp
@@ -0,0 +1,32 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+int t[100001];
+map<int, ll> cnt, pre;
+
+int main() {
+    int N, Q;
+	cin >> N >> Q;
+	for (int i = 0; i < N; ++i) cin >> t[i];
+
+	unordered_map<int, int> m;
+	for (int i = N - 1; i >= 0; --i) {
+		unordered_map<int, int> tmp;
+		for (auto x : m) tmp[__gcd(t[i], x.f)] += x.s;
+		++tmp[t[i]];
+		swap(tmp, m);
+		for (auto& x : m) cnt[x.f] += x.s;
+	}
+	for (auto& x : cnt) pre[x.f] = x.s + (pre.size() ? pre.rbegin()->s : 0);
+	
+	while (Q--) {
+		int a, b;
+		cin >> a >> b;
+		auto ia = pre.upper_bound(a - 1), ib = pre.upper_bound(b);
+		cout << (ib != pre.begin() ? prev(ib)->s : 0) - (ia != pre.begin() ? prev(ia)->s : 0) << '\n';
+	}
+}
\ No newline at end of file
diff --git a/2018/day2/cowcliquer.cpp b/2018/day2/cowcliquer.cpp
new file mode 100644
index 0000000..fc7f9e9
--- /dev/null
+++ b/2018/day2/cowcliquer.cpp
@@ -0,0 +1,39 @@
+#include "grader.h"
+#include <bits/stdc++.h>
+#define par first
+#define sz second
+using namespace std;
+using ii = pair<int, int>;
+constexpr int INF = 2e9;
+ 
+int cnt;
+unordered_map<string, int> s;
+vector<pair<int, ii>> m[200002];
+
+inline void alloc(string cow) { if (s.find(cow) == end(s)) s[cow] = ++cnt, m[cnt].emplace_back(0, ii(cnt, 1)); }
+
+inline ii & get(int i, int timestamp) {	return prev(upper_bound(begin(m[i]), end(m[i]), make_pair(timestamp, ii(INF, 0))))->second; }
+
+int find_set(int i, int timestamp) {
+	int & p = get(i, timestamp).par;
+	return (p == i) ? i : (p = find_set(p, timestamp));
+}
+ 
+void add_friend(string cow1, string cow2, int timestamp) {
+	alloc(cow1), alloc(cow2);
+	int i = find_set(s[cow1], timestamp), j = find_set(s[cow2], timestamp);
+	if (i == j) return;
+	ii x = get(i, timestamp), y = get(j, timestamp);
+	if (x.sz < y.sz) swap(i, j);
+	m[i].emplace_back(timestamp, ii(i, x.sz + y.sz)), m[j].emplace_back(timestamp, ii(i, 0));
+}
+ 
+bool check_friend(string cow1, string cow2, int timestamp) {
+	alloc(cow1), alloc(cow2);
+	return find_set(s[cow1], timestamp) == find_set(s[cow2], timestamp);
+}
+ 
+int get_number_of_friends(string cow, int timestamp) {
+	alloc(cow);
+	return get(find_set(s[cow], timestamp), timestamp).sz;
+}
\ No newline at end of file
diff --git a/2018/day2/grader.h b/2018/day2/grader.h
new file mode 100644
index 0000000..bbe8639
--- /dev/null
+++ b/2018/day2/grader.h
@@ -0,0 +1,55 @@
+#include <iostream>
+
+/*
+ * You need to implement the following functions:
+ */
+
+void add_friend(std::string cow1, std::string cow2, int timestamp);
+bool check_friend(std::string cow1, std::string cow2, int timestamp);
+int get_number_of_friends(std::string cow, int timestamp);
+
+// Commands have the following format:
+// A c1 c2 t
+//  - Calls "add"friend" on cows "c1" and "c2" at timestamp t. You are
+//    guaranteed that successive calls to A will have increasing values of t.
+// C c1 c2 t
+//  - Calls "check_friend" on cows "c1" and "c2" at timestamp t.
+// N c t
+//  - Calls "get_number_of_friends" on cow "c" at timestamp "t".
+
+// You don't need to read or understand any of the code below,
+// but it may be helpful.
+
+int main() {
+  int num_commands;
+  std::cin >> num_commands;
+
+  for (int i = 0; i < num_commands; ++i) {
+    std::string command_type;
+    std::cin >> command_type;
+
+    if (command_type == "A") {
+      std::string cow1, cow2;
+      int timestamp;
+      std::cin >> cow1 >> cow2 >> timestamp;
+
+      add_friend(cow1, cow2, timestamp);
+    } else if (command_type == "C") {
+      std::string cow1, cow2;
+      int timestamp;
+      std::cin >> cow1 >> cow2 >> timestamp;
+
+      std::string responses[] = {"FALSE", "TRUE"};
+      std::cout << responses[check_friend(cow1, cow2, timestamp)] << std::endl;
+    } else if (command_type == "N") {
+      std::string cow;
+      int timestamp;
+      std::cin >> cow >> timestamp;
+
+      std::cout << get_number_of_friends(cow, timestamp) << std::endl;
+    } else {
+      std::cout << "Invalid command type: " << command_type << std::endl;
+      exit(1);
+    }
+  }
+}
diff --git a/2018/day2/sweetgrass.cpp b/2018/day2/sweetgrass.cpp
new file mode 100644
index 0000000..96380bf
--- /dev/null
+++ b/2018/day2/sweetgrass.cpp
@@ -0,0 +1,66 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int N, idx[100001];
+bitset<100001> vis, ans;
+vector<int> path;
+unordered_set<int> G[100001];
+
+void solve() {
+	vis.reset();
+	for (int i = 0; i < path.size() - 1; ++i) {
+		G[path[i]].erase(path[i + 1]);
+	}
+	memset(idx, -1, sizeof idx);
+	for (int i = 0; i < path.size(); ++i) idx[path[i]] = i;
+	int m = 0;
+	ans.set();
+	for (int i = 0; i < path.size() - 1; ++i) {
+		m = max(i + 1, m);
+		queue<int> q;
+		q.push(path[i]);
+		while (q.size()) {
+			int u = q.front();
+			q.pop();
+			if (vis[u]) continue;
+			vis[u] = 1;
+			if (u != path[i] && idx[u] != -1) {
+				for (int j = m; j < idx[u]; ++j)
+					ans[j] = 0;
+				m = max(idx[u], m);
+				continue;
+			}			
+			for (auto& v : G[u]) {
+				if (!vis[v]) q.push(v);
+			}
+		}
+	}
+	vector<int> out;
+	for (int i = 1; i < path.size() - 1; ++i)
+		if (ans[i]) out.push_back(path[i]);
+	sort(begin(out), end(out));
+	cout << out.size() << '\n';
+	for (auto& x : out) cout << x << '\n';
+}
+
+void dfs(int u) {
+	vis[u] = 1;
+	path.push_back(u);
+	if (u == N) {
+		solve();
+		exit(0);
+	}	
+	for (auto& v : G[u]) {
+		if (!vis[v]) dfs(v);
+	}
+	path.pop_back();
+}
+
+int main() {
+	int M; cin >> N >> M;
+	while (M--) {
+		int a, b; cin >> a >> b;
+		G[a].insert(b);
+	}
+	dfs(1);
+}
\ No newline at end of file
diff --git a/2018/day5/cowmooting.cpp b/2018/day5/cowmooting.cpp
new file mode 100644
index 0000000..86f6460
--- /dev/null
+++ b/2018/day5/cowmooting.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+vector<pair<ii, int>> G[101];
+ll dist[101][10001];
+
+int main() {
+	int B, M, N; cin >> B >> M >> N;
+	while (M--) {
+		int a, b, t, c; cin >> a >> b >> t >> c;
+		G[a].emplace_back(ii(t, c), b), G[b].emplace_back(ii(t, c), a);
+	}
+	memset(dist, '?', sizeof dist);
+	dist[0][0] = 0;
+	priority_queue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> pq;
+	pq.emplace(0, ii(0, 0));
+	while (!pq.empty()) {
+		ll d = pq.top().f; ii u = pq.top().s;
+		pq.pop();
+		if (d > dist[u.f][u.s]) continue;
+		for (auto& v : G[u.f]) {
+			if (u.s + v.f.f < 1e4 && d + v.f.s < dist[v.s][u.s + v.f.f]) {
+				dist[v.s][u.s + v.f.f] = d + v.f.s;
+				pq.emplace(dist[v.s][u.s + v.f.f], ii(v.s, u.s + v.f.f));
+			}
+		}
+	}
+	int ans = 0;
+	while (ans < 1e4 && dist[1][ans] > B) ++ans;
+	cout << (ans < 1e4 ? ans : -1) << '\n';
+}
\ No newline at end of file
diff --git a/2018/day5/mootube.cpp b/2018/day5/mootube.cpp
new file mode 100644
index 0000000..b146b56
--- /dev/null
+++ b/2018/day5/mootube.cpp
@@ -0,0 +1,78 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+constexpr ll p1 = 19, p2 = 29, p3 = 53;
+constexpr ll MOD = 1e9+7;
+
+template<int D, typename T> struct vec_nd : public vector<vec_nd<D - 1, T>> {
+  static_assert(D >= 1, "Vector dimension must be greater than zero!");
+  template<typename... Args> vec_nd(int n = 0, Args... args) : vector<vec_nd<D - 1, T>>(n, vec_nd<D - 1, T>(args...)) { }
+};
+template<typename T> struct vec_nd<1, T> : public vector<T> { vec_nd(int n = 0, const T& val = T()) : vector<T>(n, val) { } };
+
+int pw(int base, int exp) {
+	int res = 1;
+	while (exp) {
+		if (exp & 1) res = (ll)base * res % MOD;
+		exp >>= 1, base = (ll)base * base % MOD;
+	}
+	return res;
+}
+
+int inv(int x) { return pw(x, MOD - 2); }
+
+int main() {
+	int T1, R1, C1; cin >> T1 >> R1 >> C1;
+	vec_nd<3, ll> A(T1, R1, C1);
+	for (int i = 0; i < T1; ++i) for (int j = 0; j < R1; ++j) for (int k = 0; k < C1; ++k) cin >> A[i][j][k];
+	
+	int T2, R2, C2; cin >> T2 >> R2 >> C2;
+	vec_nd<3, ll> B(T2, R2, C2);
+	for (int i = 0; i < T2; ++i) for (int j = 0; j < R2; ++j) for (int k = 0; k < C2; ++k) cin >> B[i][j][k];
+	
+	ll h = 0;
+	ll pw1 = 1; for (int i = 0; i < T1; ++i) {
+		ll pw2 = 1; for (int j = 0; j < R1; ++j) {
+			ll pw3 = 1; for (int k = 0; k < C1; ++k) {
+				h = (A[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 + h) % MOD;
+			pw3 = p3 * pw3 % MOD; }
+		pw2 = p2 * pw2 % MOD; }
+	pw1 = p1 * pw1 % MOD; }
+
+	vec_nd<3, ll> S(T2, R2, C2);
+	pw1 = 1; for (int i = 0; i < T2; ++i) {
+		ll pw2 = 1; for (int j = 0; j < R2; ++j) {
+			ll pw3 = 1; for (int k = 0; k < C2; ++k) {
+				S[i][j][k] = B[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 % MOD;
+				if (i) S[i][j][k] += S[i - 1][j][k];
+				if (j) S[i][j][k] += S[i][j - 1][k];
+				if (k) S[i][j][k] += S[i][j][k - 1];
+				if (i && j) S[i][j][k] -= S[i - 1][j - 1][k];
+				if (i && k) S[i][j][k] -= S[i - 1][j][k - 1];
+				if (j && k) S[i][j][k] -= S[i][j - 1][k - 1];				
+				if (i && j && k) S[i][j][k] += S[i - 1][j - 1][k - 1];
+				S[i][j][k] = (S[i][j][k] + MOD * MOD) % MOD;
+			pw3 = p3 * pw3 % MOD; }
+		pw2 = p2 * pw2 % MOD; }
+	pw1 = p1 * pw1 % MOD; }
+
+	ll ans = 0;
+	pw1 = 1; for (int i = 0; i <= T2 - T1; ++i) {
+		ll pw2 = 1; for (int j = 0; j <= R2 - R1; ++j) {
+			ll pw3 = 1;	for (int k = 0; k <= C2 - C1; ++k) {
+				ll h2 = S[i + T1 - 1][j + R1 - 1][k + C1 - 1];
+				if (i) h2 -= S[i - 1][j + R1 - 1][k + C1 - 1];
+				if (j) h2 -= S[i + T1 - 1][j - 1][k + C1 - 1];
+				if (k) h2 -= S[i + T1 - 1][j + R1 - 1][k - 1];
+				if (i && j) h2 += S[i - 1][j - 1][k + C1 - 1];
+				if (i && k) h2 += S[i - 1][j + R1 - 1][k - 1];
+				if (j && k) h2 += S[i + T1 - 1][j - 1][k - 1];				
+				if (i && j && k) h2 -= S[i - 1][j - 1][k - 1];
+				h2 = (h2 + MOD * MOD) % MOD;
+				h2 = h2 * inv(pw3) % MOD * inv(pw2) % MOD * inv(pw1) % MOD;
+				if (h2 == h) ++ans;
+			pw3 = p3 * pw3 % MOD; }
+		pw2 = p2 * pw2 % MOD; }
+	pw1 = p1 * pw1 % MOD; }
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2019/day1/out b/2019/day1/out
new file mode 100644
index 0000000..67f3f23
--- /dev/null
+++ b/2019/day1/out
@@ -0,0 +1 @@
+270
diff --git a/2019/day1/palindrometer.cpp b/2019/day1/palindrometer.cpp
new file mode 100644
index 0000000..65914fa
--- /dev/null
+++ b/2019/day1/palindrometer.cpp
@@ -0,0 +1,22 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int P[2][100001];
+
+int main() {
+	string S; cin >> S;
+	int N = S.size();
+	for (int i = 0; i < 2; ++i) {
+		for (int j = 0, l = 0, r = 0; j < N; ++j) {
+			int k = (j > r ? !i : min(P[i][l + r - j + i], r - j + 1));
+			while (j - k - i >= 0 && j + k < N && S[j - k - i] == S[j + k]) ++k;
+			P[i][j] = k--;
+			if (j + k > r) l = j - k - i, r = j + k;
+		}
+	}
+
+	ll ans = 0;
+	for (int i = 0; i < N; ++i) ans += P[0][i] + P[1][i];
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2019/day1/retemordnilap.cpp b/2019/day1/retemordnilap.cpp
new file mode 100644
index 0000000..991bc78
--- /dev/null
+++ b/2019/day1/retemordnilap.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int main() {
+	char s[10] = "MMOOMO";
+	int K;
+	cin >> K;
+	if (K == 5) {
+		cout << "impossible";
+		return 0;
+	}
+	if (K == 1) { cout << "O"; return 0; }
+	if (K == 2) { cout << "MO"; return 0; }
+	if (K == 3) { cout << "MM";	return 0; }
+	if (K == 7) { cout << "MMMO"; return 0; }
+	if (K == 9) { cout << "MOMOM"; return 0; }
+	if (K % 2 == 0 && K / 2 <= 1e5) {
+		for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
+		return 0;
+	}
+	ll sq = sqrt(8ll * K + 1) + 0.5;
+	if (sq * sq == 8ll * K + 1) {
+		int t = (sq - 1) / 2;
+		for (int i = 0; i < t; ++i) cout << "O";
+		return 0;
+	}
+	/*if (K > 1e8 && K % 2 == 1) {
+		cout << "M";
+		--K;
+	}*/
+	int t = sqrt(2 * K);
+	while ((((K - t * (t + 1) / 2) - 2) % 2) || K - t * (t + 1) / 2 - 2 < 6) --t;
+	for (int i = 0; i < t; ++i) cout << "O";
+	int ans = t;
+	//cout << t << '\n';
+	K += - t * (t + 1) / 2 - 2;
+	for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
+	ans += K / 2;
+	assert(ans <= 1e5);
+	//cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2019/day1/test.sh b/2019/day1/test.sh
new file mode 100644
index 0000000..3b4f3f1
--- /dev/null
+++ b/2019/day1/test.sh
@@ -0,0 +1,9 @@
+for i in {6..1000}
+do
+	echo $i >> in
+    .vscode/3 < in | .vscode/1 > out
+    if !(cmp -s in out); then
+		echo $i
+	fi
+	rm in
+done
\ No newline at end of file
diff --git a/2019/day1/treedist.cpp b/2019/day1/treedist.cpp
new file mode 100644
index 0000000..a2c83ae
--- /dev/null
+++ b/2019/day1/treedist.cpp
@@ -0,0 +1,44 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+#define eb emplace_back
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MAXN = 100001;
+constexpr ll INF = 1e9;
+
+int N, Q, H[MAXN];
+bitset<MAXN> ans;
+vector<ii> G[3 * MAXN];
+unordered_map<ll, int> vis;
+
+void solve(int u, int p, int d) {
+	if (d && u <= N) ans[u] = 1;
+	if (d < 0) d = -1;
+	if (vis.find(INF * u + p) != vis.end()) {
+		if (vis[INF * u + p] != d) d = -1;
+		else return;
+	}
+	vis[INF * u + p] = d;
+	for (auto & v : G[u]) if (v.s != p) solve(v.s, u, d - v.f);
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	cin >> N >> Q;
+	iota(H, H + N + 1, 0);
+	int l = N + 1;
+	for (int i = 1, a, b; i < N; ++i) {
+		cin >> a >> b;
+		G[H[a]].eb(0, l), G[l].eb(0, H[a]), H[a] = l++;
+		G[H[b]].eb(0, l), G[l].eb(0, H[b]),	H[b] = l++;
+		G[H[a]].eb(1, H[b]), G[H[b]].eb(1, H[a]);
+	}
+	while (Q--) {
+		int a, b; cin >> a >> b;
+		solve(a, 0, b);
+	}
+	cout << N - ans.count() << '\n';
+	for (int i = 1; i <= N; ++i) if (!ans[i]) cout << i << '\n';
+}
\ No newline at end of file
diff --git a/2019/day2/mana.cpp b/2019/day2/mana.cpp
new file mode 100644
index 0000000..7fad64b
--- /dev/null
+++ b/2019/day2/mana.cpp
@@ -0,0 +1,31 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ii = pair<int, int>;
+
+vector<ii> S[101];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+
+	int M, R, N;
+	cin >> M >> R >> N;
+	for (int i = 0, a, c, d; i < N; ++i) {
+		cin >> a >> c >> d;
+		S[d].emplace_back(a, c);
+	}
+	int T = M + 100 * R;
+	vector<int> dp(T + 1, -1e9);
+	dp[0] = 0;
+	for (int d = 0; d <= 100; ++d) {
+		int g = M + d * R;
+		for (auto& p : S[d]) {
+			int a = p.f, c = p.s;
+			for (int i = g - c; i >= 0; --i) dp[i + c] = max(dp[i] + a, dp[i + c]);
+		}
+	}
+	int ans = 0;
+	for (auto& x : dp) ans = max(x, ans);
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2019/day2/themepark.cpp b/2019/day2/themepark.cpp
new file mode 100644
index 0000000..2582eb3
--- /dev/null
+++ b/2019/day2/themepark.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+constexpr int MAXN = 100001;
+
+int c[MAXN];
+vector<int> G[MAXN];
+
+int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN];
+stack<int> s;
+bitset<MAXN> ins;
+
+void tarjan(int u) {
+	low[u] = in[u] = cnt++;
+	s.push(u);
+	ins[u] = 1;
+	for (int v : G[u]) {
+		if (in[v] == -1) tarjan(v), low[u] = min(low[u], low[v]);
+		else if (ins[v]) low[u] = min(low[u], in[v]);
+	}
+	if (low[u] == in[u]) {
+		++scc_num;
+		while (1) {
+			int x = s.top(); s.pop();
+			scc[x] = scc_num, ins[x] = 0;
+			if (x == u) break;
+		}
+	}
+}
+
+int main() {
+	int N, M, K; cin >> N >> M >> K;
+	while (M--) {
+		int a, b; cin >> a >> b;
+		G[a].push_back(b);
+	}
+
+	memset(scc, -1, sizeof scc), memset(in, -1, sizeof in);
+	for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(u);
+
+	if (scc_num < K) cout << "impossible\n";
+	else for (int u = 1; u <= N; ++u) cout << min(scc[u], K) << '\n';	
+}
\ No newline at end of file
diff --git a/2020/day1/repl.cpp b/2020/day1/repl.cpp
new file mode 100644
index 0000000..6b0a301
--- /dev/null
+++ b/2020/day1/repl.cpp
@@ -0,0 +1,43 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+#define pb push_back
+#define eb emplace_back
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+using vi = vector<int>;
+using vii = vector<ii>;
+
+vi G[100001];
+
+bool test(int x, vector<int> & ch) {
+	ll tmp = 1;
+	for (auto& c : ch) {
+		if (c > x || !tmp) return 0;
+		tmp = min(tmp * (1 << min(x - c, 20)) - 1, 100001ll), x = c;	
+	}
+	return tmp;
+}
+
+int dfs(int u, int p) {
+	vi ch;
+	for (auto& v : G[u]) if (v != p) ch.push_back(dfs(v, u));
+	if (ch.empty()) return 0;
+	sort(begin(ch), end(ch), greater<int>());
+	int l = ch[0] + 1, r = 100001;
+	while (l < r) {
+		int m = (l + r) / 2;
+		test(m, ch) ? r = m : l = m + 1;
+	}
+	return l;
+}
+
+int main() {
+	int N; cin >> N;
+	for (int i = 1; i < N; ++i) {
+		int a, b; cin >> a >> b;
+		G[a].push_back(b), G[b].push_back(a);
+	}
+	cout << dfs(1, 0) + N - 1 << '\n';	
+}
\ No newline at end of file
diff --git a/2020/day1/tri.cpp b/2020/day1/tri.cpp
new file mode 100644
index 0000000..a28df48
--- /dev/null
+++ b/2020/day1/tri.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+#define pb push_back
+#define eb emplace_back
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+using vi = vector<int>;
+using vii = vector<ii>;
+
+ii E[100001];
+vi G[100001];
+bitset<100001> vis, oc;
+
+int main() {
+	int N, M;
+	cin >> N >> M;
+	for (int i = 0; i < M; ++i) {
+		cin >> E[i].f >> E[i].s;
+		G[E[i].f].pb(E[i].s), G[E[i].s].pb(E[i].f);
+	}
+
+	vi v;
+	for (int i = 1; i <= N; ++i) v.push_back(i);
+	sort(begin(v), end(v), [](int a, int b) { return G[a].size() < G[b].size(); });
+
+	ll ans = 0;
+	for (auto& u : v) {
+		vis[u] = 1;
+		for (auto& v : G[u]) oc[v] = 1;
+		vi tmp;
+		for (auto& v : G[u]) {
+			if (vis[v]) tmp.pb(v);
+		}
+		for (auto& v : tmp) {
+			for (auto& w : G[v]) ans += oc[w];
+		}
+		for (auto& v : G[u]) oc[v] = 0;
+	}
+	cout << ans / 3 << '\n';
+}
\ No newline at end of file
diff --git a/2020/day2/meet.cpp b/2020/day2/meet.cpp
new file mode 100644
index 0000000..4f37159
--- /dev/null
+++ b/2020/day2/meet.cpp
@@ -0,0 +1,32 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+
+int a[303];
+vector<int> G[303];
+
+void dfs(int u, int p) {
+	for (auto& v : G[u]) {
+		dfs(v, u);
+		
+	}
+
+
+}
+
+int main() {
+	int N;
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> a[i];
+	for (int i = 1; i < N; ++i) {
+		int u, v;
+		cin >> u >> v;
+		G[u].push_back(v), G[v].push_back(u);
+	}
+
+	dfs(1, 0);
+
+}
\ No newline at end of file
diff --git a/2020/day2/meet_slow.cpp b/2020/day2/meet_slow.cpp
new file mode 100644
index 0000000..99d8b21
--- /dev/null
+++ b/2020/day2/meet_slow.cpp
@@ -0,0 +1,97 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+
+int a[303], cost[303][303], dp[303][303];
+vector<int> G[303];
+
+int main() {
+	int N;
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> a[i];
+	for (int i = 1; i < N; ++i) {
+		int u, v;
+		cin >> u >> v;
+		--u, --v;
+		G[u].push_back(v), G[v].push_back(u);
+	}
+	if (N <= 20) {
+		int ans[22];
+		fill(ans, ans + N + 1, 1e9);
+		for (int m = 1; m < (1 << N); ++m) {
+			int dist[22];
+			queue<ii> q;
+			for (int i = 0; i < N; ++i) {
+				if (1 & (m >> i)) {
+					dist[i] = 0;
+					q.emplace(i, 0);
+				}
+				else dist[i] = 1e9;
+			}
+			while (!q.empty()) {
+				int u = q.front().f, d = q.front().s;
+				q.pop();
+				if (d > dist[u]) continue;
+				for (auto& v : G[u]) {
+					if (d + 1 < dist[v]) {
+						dist[v] = d + 1;
+						q.emplace(v, dist[v]);
+					}
+				}
+			}
+			int sum = 0;
+			for (int i = 0; i < N; ++i) sum += a[i] * dist[i];
+			ans[__builtin_popcount(m)] = min(sum, ans[__builtin_popcount(m)]);
+		}
+		for (int i = 1; i <= N; ++i) cout << ans[i] << ' ';
+	}
+	else {
+		int s;
+		for (int i = 0; i < N; ++i) {
+			if (G[i].size() == 1) s = i;
+		}
+		vector<int> v(N);
+		int p = -1;
+		for (int i = 0; i < N; ++i) {
+			v[i] = a[s];
+			if (i < N - 1) {
+				int tmp = s;
+				s = (G[s][0] == p ? G[s][1] : G[s][0]);
+				p = tmp;
+			}
+		}
+		memset(cost, '?', sizeof cost);
+		for (int i = 0; i < N; ++i) {
+			for (int j = i; j < N; ++j) {
+				int cnt = 0, sum = 0;
+				for (int k = i; k <= j; ++k) {
+					cnt += v[k];
+					sum += (k - i) * v[k];
+				}
+				cnt -= v[i];
+				cost[i][j] = min(sum, cost[i][j]);
+				int tmp = 0;
+				for (int k = i + 1; k <= j; ++k) {
+					tmp += v[k - 1];
+					sum -= cnt;
+					sum += tmp;
+					cnt -= v[k];
+					cost[i][j] = min(sum, cost[i][j]);
+				}
+			}
+		}
+		memset(dp, '?', sizeof dp);
+		dp[0][0] = 0;
+		for (int i = 0; i < N; ++i) {
+			for (int j = 0; j <= i; ++j) {
+				for (int k = 0; k <= i; ++k) {
+					dp[i + 1][j + 1] = min(dp[k][j] + cost[k][i], dp[i + 1][j + 1]);
+				}
+			}
+		}
+		for (int i = 1; i <= N; ++i) cout << dp[N][i] << ' ';
+	}
+}
\ No newline at end of file
diff --git a/2020/day2/reopen.cpp b/2020/day2/reopen.cpp
new file mode 100644
index 0000000..0d64e84
--- /dev/null
+++ b/2020/day2/reopen.cpp
@@ -0,0 +1,29 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int n, a, b;
+	string r;
+	cin >> n >> a >> b >> r;
+	
+	if (r == "1/2") {
+		for (int i = 0; i < n / 2; ++i) cout << b * i << ' ' << 0 << '\n';
+		for (int i = n / 2; i < n; ++i) cout << b * i + a << ' ' << 0 << '\n';
+	}
+	else {
+		int d = a * (b + 1) / 2 % b;
+		for (int i = 0; i < n; ++i) {
+			int x = d + (i / 4) * b, y = 0;
+			if (i % 2 == 1) swap(x, y);
+			if (i % 4 == 2) x = -x;
+			if (i % 4 == 3) y = -y;
+			cout << x + 500000000 << ' ' << y + 500000000 << '\n';
+		}
+	}
+}
\ No newline at end of file
diff --git a/2020/day2/triangles.cpp b/2020/day2/triangles.cpp
new file mode 100644
index 0000000..c30cbc7
--- /dev/null
+++ b/2020/day2/triangles.cpp
@@ -0,0 +1,45 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+constexpr ll MOD = 1e9+7;
+
+ii P[2002];
+
+int main() {
+	ifstream cin("triangles.in");
+	ofstream cout("triangles.out");
+
+	int N;
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s;
+	sort(P, P + N);
+
+	ll ans = 0;
+	for (int i = 0; i < N; ++i) {
+		ii p = P[i];
+		vector<ii> l, r;
+		for (int j = 0; j < i; ++j) l.push_back(P[j]);
+		for (int j = i + 1; j < N; ++j) r.push_back(P[j]);
+		sort(l.begin(), l.end(), [&p](const ii& a, const ii& b) {
+			int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f);
+			if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s);
+			return x < 0;
+		});
+		sort(r.begin(), r.end(), [&p](const ii& a, const ii& b) {
+			int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f);
+			if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s);
+			return x < 0;
+		});
+
+		for (int j = 0, k = 0; j < i; ++j) {
+			while (k < N - i - 1 && (l[j].f - p.f) * (r[k].s - p.s) - (l[j].s - p.s) * (r[k].f - p.f) <= 0) ++k;
+			ans += (ll)(2 * j + N - 2 * i - 2 * k) * (p.s + l[j].s) * (p.f - l[j].f) + MOD * MOD;
+			ans %= MOD;
+		}
+	}
+
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2020/day2/triangles_gen.cpp b/2020/day2/triangles_gen.cpp
new file mode 100644
index 0000000..fec17ae
--- /dev/null
+++ b/2020/day2/triangles_gen.cpp
@@ -0,0 +1,24 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+
+int M = 10000;
+
+int main() {
+	ofstream cout("triangles.in");
+
+	int N = 100;
+	cout << N << '\n';
+	srand(time(0));
+	vector<ii> v;
+	for (int i = 0; i < N; ++i) {
+		ii x;
+		do {
+			x.f = (rand() % (2 * M)) - M, x.s = (rand() % (2 * M)) - M;
+		} while (find(v.begin(), v.end(), x) != v.end());
+		v.push_back(x);
+		cout << x.f << ' ' << x.s << '\n';
+	}
+}
\ No newline at end of file
diff --git a/2020/day3/treemst.cpp b/2020/day3/treemst.cpp
new file mode 100644
index 0000000..ad4bae2
--- /dev/null
+++ b/2020/day3/treemst.cpp
@@ -0,0 +1,44 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+int h[100001], p[100001], d[100001], l[100001], r[100001];
+ll ans;
+set<ii> S;
+vector<int> G[100001];
+
+void dfs(int u, int p) {
+	d[u] = d[p] + 1;
+	l[u] = r[u] = 2e9;
+	S.emplace(h[u], u);
+	for (auto& v : G[u]) {
+		if (v != p) dfs(v, u);
+	}
+	S.erase(ii(h[u], u));
+	if (u == 1) return;
+	
+	auto it = S.lower_bound(ii(h[u], u));
+	if (it != begin(S)) l[u] = min(h[u] - prev(it)->f, l[u]);
+	if (it != end(S)) r[u] = min(it->f - h[u], r[u]);
+	ans += min(l[u], r[u]);
+	int m = max(l[u], r[u]);
+	if (m < 2e9) {
+		int y = prev(it)->s, z = it->s;
+		d[y] > d[z] ? r[y] = min(m, r[y]) : l[z] = min(m, l[z]);
+	}
+}
+
+int main() {
+	int N;
+	cin >> N;
+	for (int i = 1; i <= N; ++i) cin >> h[i];
+	for (int i = 2; i <= N; ++i) {
+		cin >> p[i];
+		G[p[i]].push_back(i);
+	}
+	dfs(1, 0);
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2020/day4/extra.cpp b/2020/day4/extra.cpp
new file mode 100644
index 0000000..360fa67
--- /dev/null
+++ b/2020/day4/extra.cpp
@@ -0,0 +1,30 @@
+#include <bits/stdc++.h>
+using namespace std;
+constexpr int MOD = 1e9+7;
+
+int lcp[5005][5005], dp[5005][5005];
+
+int main() {
+	string s;
+	cin >> s;
+	int n = s.size();
+	for (int i = n - 1; i >= 0; --i) {
+		for (int j = n - 1; j >= i; --j) {
+			if (s[i] == s[j]) lcp[i][j] = 1 + lcp[i + 1][j + 1];
+		}
+	}
+
+	dp[0][0] = 1;
+	for (int i = 0; i < n; ++i) {
+		for (int j = i + 1; j <= n; ++j) {
+			dp[i][j] += dp[i][j - 1], dp[i][j] %= MOD;
+			int len = min(lcp[i][j], j - i);
+			if (i + len >= n || (len < j - i && s[i + len] > s[j + len])) continue;
+			dp[j][j + len + 1] += dp[i][j], dp[j][j + len + 1] %= MOD;
+		}
+	}
+
+	int ans = 0;
+	for (int i = 0; i < n; ++i) ans += dp[i][n], ans %= MOD;
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2020/day6/cowputing b/2020/day6/cowputing
new file mode 100644
index 0000000..f15e67a
--- /dev/null
+++ b/2020/day6/cowputing
@@ -0,0 +1,29 @@
+# g++ grader.cc && cp solution output && ./a.out
+
+# Blank lines and comment lines (start with '#') are allowed
+
+# TASK 1
+# Your machine is given as lines of rules. Each rule has the form:
+# STATE SYMBOL -> NEW_STATE WRITE_SYMBOL ACTION
+# STATE can be any string. The Cowputer always starts in state "0".
+# SYMBOL can be any alphanumeric character (A-Z,a-z,0-9).
+# ACTION is one of L(eft) R(ight) S(tay) H(alt)
+# If your program encounters a state it has no rule for, that's WA.
+# With these rules, the Cowputer will go left until it finds an 'X' and then halt.
+# It won't change the array at all, because on every step it just writes whatever symbol
+# was already there.
+0 1 -> 0 1 L
+# ^"If you are in state 0 and see symbol '1', go to state 0, write a '1' and move left"
+# This means that the state stays the same, it writes a one on the current index
+# in the array, and moves to index-1 in the array
+0 0 -> 0 0 L
+# ^"If you are in state 0 and see symbol '0', go to state 0, write a '0' and move left"
+0 X -> 0 X H
+# ^"If you are in state 0 and see symbol 'X', go to state 0, write an 'X', and halt"
+
+# TASK 2
+# You should submit all your programs in one file. Programs are separated by '# TASK <N>' lines.
+# You would put your rules for TASK 2 here.
+# This submission for TASK 2 just halts immediately. Unfortunately, that does not solve task 2.
+0 0 -> 0 0 H
+0 1 -> 0 1 H
\ No newline at end of file
diff --git a/2020/day6/friend.cpp b/2020/day6/friend.cpp
new file mode 100644
index 0000000..6a9fdec
--- /dev/null
+++ b/2020/day6/friend.cpp
@@ -0,0 +1,29 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+constexpr ll MOD = 1e9+7;
+
+int a[100001], b[100001];
+map<ii, ll> f, g;
+
+int main() {
+	int N;
+	cin >> N;
+	f[ii(1, 2)] = 1;
+	for (int i = 3; i <= N; ++i) {
+		cin >> a[i] >> b[i];
+		f[ii(a[i], i)] = f[ii(b[i], i)] = 1;
+	}
+	g = f;
+	int ans = 0;
+	for (int i = N; i >= 3; --i) {
+		ii x(a[i], i), y(b[i], i), z(a[i], b[i]);
+		ans = (g[x] * f[y] % MOD * f[z] + f[x] * g[y] % MOD * f[z] + f[x] * f[y] % MOD * g[z] + ans) % MOD;
+		g[z] = (f[x] * g[y] + g[x] * f[y] + g[z]) % MOD;
+		f[z] = (f[x] * f[y] + f[z]) % MOD;
+	}
+	cout << 2 * ans % MOD << '\n';
+}
\ No newline at end of file
diff --git a/2020/day6/grader.cc b/2020/day6/grader.cc
new file mode 100644
index 0000000..b1c32c0
--- /dev/null
+++ b/2020/day6/grader.cc
@@ -0,0 +1,467 @@
+#include <iostream>
+#include <vector>
+#include <cassert>
+#include <cstdlib>
+#include <set>
+#include <map>
+#include <csignal>
+#include <cstdio>
+#include <fstream>
+#include <cmath>
+#include <sstream>
+#include <functional>
+#include <random>
+#include <tuple>
+#include <deque>
+
+int TRACE = -1;
+
+using ll = long long;
+using namespace std;
+
+ostream& operator<<(ostream& o, const deque<char>& ARRAY) {
+  for(int i=0; i<ARRAY.size(); i++) {
+    o << ARRAY[i];
+  }
+  return o;
+}
+ll r(ll lo, ll hi) {
+  static default_random_engine RNG(0);
+  return uniform_int_distribution<ll>(lo,hi)(RNG);
+}
+
+void fassert(bool b, const string& msg) {
+  if(!b) {
+    cerr << msg << endl;
+    cout << "W" << endl;
+    assert(false);
+  }
+}
+
+// STATE CHARACTER -> NEW_STATE NEW_CHARACTER {L(EFT),R(IGHT),S(TAY),H(ALT)}
+using Cowputer = map<string,map<char,tuple<string,char,char>>>;
+constexpr ll LIMIT = static_cast<ll>(1e6);
+
+set<char> symbols(const Cowputer& M) {
+  set<char> ans;
+  for(auto& kv : M) {
+    for(auto& kv2 : kv.second) {
+      string new_state; char new_char; char action;
+      std::tie(new_state, new_char, action) = kv2.second;
+      ans.insert(kv2.first);
+      ans.insert(new_char);
+    }
+  }
+  return ans;
+}
+
+struct State {
+  State(Cowputer m, deque<char>& START, bool trace_) : RULES(m), ARRAY(START), pos(0), state("0"), time(0), tle(false), trace(trace_) {
+    if(ARRAY.size() == 0) {
+      ARRAY.push_back('X');
+    }
+  }
+  deque<char>& ARRAY;
+  int pos;
+  string state;
+  int time;
+  Cowputer RULES;
+  bool tle;
+
+  bool trace;
+
+  bool run() {
+    if(trace) {
+      cerr << "TRACE: STARTING ARRAY=" << ARRAY << endl;
+    }
+    while(!step(trace)) {}
+    if(trace) {
+      cerr << "TRACE: ENDING ARRAY=" << ARRAY << endl;
+    }
+    return tle;
+  }
+
+  bool step(bool trace) {
+    if(time == LIMIT) {
+      tle = true;
+      return true;
+    }
+    if(trace) { cerr << "TRACE: " << show() << endl; }
+    fassert(0<=pos && pos<ARRAY.size(), "INTERNAL ERROR pos="+std::to_string(pos)+" ARRAY.size="+std::to_string(ARRAY.size()));
+    char seen = ARRAY[pos];
+    fassert(RULES.count(state)==1, "MISSING RULE FOR state="+state+" seen="+std::string(1, seen));
+    fassert(RULES[state].count(seen)==1, "MISSING RULE FOR state="+state+" seen="+std::string(1, seen));
+    string new_state; char new_char; char action;
+    std::tie(new_state, new_char, action) = RULES[state][seen];
+    ARRAY[pos] = new_char;
+    state = new_state;
+    if(action == 'H') {
+      return true;
+    } else if(action == 'L') {
+      pos--;
+    } else if(action == 'R') {
+      pos++;
+    } else {
+      assert(action == 'S');
+    }
+    if(pos == -1) {
+      ARRAY.push_front('X');
+      pos = 0;
+    }
+    if(pos == ARRAY.size()) {
+      ARRAY.push_back('X');
+    }
+    time++;
+    return false;
+  }
+
+  string show() {
+    stringstream o;
+    o << "t=" << time << " state=" << state << " ";
+    for(int i=0; i<ARRAY.size(); i++) {
+      if(i == pos) {
+        o << "[";
+      }
+      o << ARRAY[i];
+      if(i == pos) {
+        o << "]";
+      }
+    }
+    return o.str();
+  }
+};
+
+deque<char> ll_to_array(ll n) {
+  deque<char> ARRAY;
+  ll tmp = n;
+  while(tmp > 0) {
+    ARRAY.push_front(static_cast<char>('0'+(tmp%2)));
+    tmp /= 2;
+  }
+  return ARRAY;
+}
+
+// Trim X off left and right
+string read_array(const deque<char>& ARRAY) {
+  stringstream ans;
+  ll start = 0;
+  while(start<ARRAY.size() && ARRAY[start]=='X') { start++; }
+  ll end = ARRAY.size()-1;
+  while(end>=0 && ARRAY[end]=='X') { end--; }
+  for(ll i=start; i<=end; i++) {
+    ans << ARRAY[i];
+  }
+  return ans.str();
+}
+
+// Reads the first integer in binary on the array
+ll from_binary(const string& S) {
+  ll ans = 0;
+  for(ll i=0; i<S.size(); i++) {
+    if(S[i]=='0') {
+      ans = ans*2;
+    } else if(S[i]=='1') {
+      ans = ans*2+1;
+    } else {
+      fassert(false, "Expected binary answer, got S="+S);
+    }
+  }
+  return ans;
+}
+
+// Times Two
+ll task1(const Cowputer& RULES, bool trace) {
+  for(int t=0; t<100; t++) {
+    ll n = r(1, 1000);
+    deque<char> ARRAY = ll_to_array(n);
+    bool tle = State(RULES, ARRAY, trace).run();
+
+    ll ret = from_binary(read_array(ARRAY));
+    if(tle) {
+      cerr << "TLE TASK 1 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+      return 0;
+    }
+    if(ret != 2*n) {
+      cerr << "WA TASK 1 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+      return 0;
+    }
+  }
+  return 5;
+}
+
+// Add1
+ll task2(const Cowputer& RULES, bool trace) {
+  for(int t=0; t<100; t++) {
+    ll n = r(1, 1000);
+    deque<char> ARRAY = ll_to_array(n);
+    bool tle = State(RULES, ARRAY, trace).run();
+
+    ll ret = from_binary(read_array(ARRAY));
+    if(tle) {
+      cerr << "TLE TASK 2 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+      return 0;
+    }
+    if(ret != n+1) {
+      cerr << "WA TASK 2 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+      return 0;
+    }
+  }
+  return 10;
+}
+
+// Swap - swap every pair of bits
+ll task3(const Cowputer& RULES, bool trace) {
+  for(ll t=0; t<100; t++) {
+    deque<char> ARRAY;
+    ll len = r(1,100)*2;
+    for(ll i=0; i<len; i++) {
+      ARRAY.push_back(r(0,1)==0?'0':'1');
+    }
+    if(trace) {
+      cerr << "STARTING ARRAY: " << ARRAY << endl;
+    }
+
+    deque<char> GOAL;
+    for(ll i=0; i<ARRAY.size(); i+=2) {
+      GOAL.push_back(ARRAY[i+1]);
+      GOAL.push_back(ARRAY[i]);
+    }
+
+    bool tle = State(RULES, ARRAY, trace).run();
+    string GOT = read_array(ARRAY);
+    if(tle) {
+      cerr << "TLE TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+      return 0;
+    }
+    if(GOT.size() != GOAL.size()) {
+      cerr << "WA TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+      return 0;
+    }
+    for(ll i=0; i<GOT.size(); i++) {
+      if(GOT[i]!=GOAL[i]) {
+        cerr << "WA TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+        return 0;
+      }
+    }
+  }
+  return 10;
+}
+
+
+// Reverse
+ll task4(const Cowputer& RULES, bool trace) {
+  for(int t=0; t<100; t++) {
+    ll len = r(1,20);
+    deque<char> ARRAY;
+    for(ll i=0; i<len; i++) {
+      ARRAY.push_back(r(0,1)==0 ? '0' : '1');
+    }
+    if(trace) {
+      cerr << "STARTING ARRAY: " << ARRAY << endl;
+    }
+
+    deque<char> GOAL;
+    for(ll i=0; i<ARRAY.size(); i++) {
+      GOAL.push_front(ARRAY[i]);
+    }
+
+    bool tle = State(RULES, ARRAY, trace).run();
+
+    string GOT = read_array(ARRAY);
+    if(tle) {
+      cerr << "TLE TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+      return 0;
+    }
+    if(GOT.size() != GOAL.size()) {
+      cerr << "WA TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+      return 0;
+    }
+    for(ll i=0; i<GOT.size(); i++) {
+      if(GOT[i]!=GOAL[i]) {
+        cerr << "WA TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+        return 0;
+      }
+    }
+  }
+  return 15;
+}
+
+// Add
+ll task5(const Cowputer& RULES, bool trace) {
+  for(int t=0; t<100; t++) {
+    ll a = r(1,1000);
+    ll b = r(1,1000);
+    deque<char> ARRAY = ll_to_array(a);
+    ARRAY.push_front('S');
+    deque<char> B = ll_to_array(b);
+    ARRAY.push_back('S');
+    for(ll i=0; i<B.size(); i++) {
+      ARRAY.push_back(B[i]);
+    }
+    ARRAY.push_back('S');
+
+    bool tle = State(RULES, ARRAY, trace).run();
+
+    ll c = a+b;
+    ll got = from_binary(read_array(ARRAY));
+    if(tle) {
+      cerr << "TLE TASK 5 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+      return 0;
+    }
+    if(c != got) {
+      cerr << "WA TASK 5 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+      return 0;
+    }
+  }
+  return 20;
+}
+
+// Multiply
+ll task6(const Cowputer& RULES, bool trace) {
+  for(int t=0; t<100; t++) {
+    ll a = r(1,1000);
+    ll b = r(1,1000);
+    deque<char> ARRAY = ll_to_array(a);
+    ARRAY.push_front('S');
+    deque<char> B = ll_to_array(b);
+    ARRAY.push_back('S');
+    for(ll i=0; i<B.size(); i++) {
+      ARRAY.push_back(B[i]);
+    }
+    ARRAY.push_back('S');
+
+    bool tle = State(RULES, ARRAY, trace).run();
+
+    ll c = a*b;
+    ll got = from_binary(read_array(ARRAY));
+    if(tle) {
+      cerr << "TLE TASK 6 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+      return 0;
+    }
+    if(c != got) {
+      cerr << "WA TASK 6 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+      return 0;
+    }
+  }
+  return 35;
+}
+
+ll task7(const Cowputer& RULES, bool trace) {
+  if(RULES.size() > 5) {
+    cerr << "Only 5 states are allowed for task 7" << endl;
+    return 0;
+  }
+  set<char> syms = symbols(RULES);
+  if(syms.size() > 3) {
+    cerr << "Only 3 characters allowed for task 7" << endl;
+  }
+
+  deque<char> ARRAY;
+  State START(RULES,ARRAY,trace);
+  bool tle = START.run();
+  if(tle) {
+    cerr << "TLE TASK 7" << endl;
+    return 0;
+  }
+  ll score = START.time;
+  if(trace) {
+    cerr << "TASK 7: TOOK " << score << " steps" << endl;
+  }
+  if(score >= 10000) {
+    return 5;
+  } else if(score >= 1000) {
+    return 4;
+  } else if(score >= 500) {
+    return 3;
+  } else if(score >= 100) {
+    return 2;
+  } else if(score >= 20) {
+    return 1;
+  } else {
+    return 0;
+  }
+}
+
+int main() {
+  ifstream in;
+  in.open("output");
+  if (!in) {
+    cerr << "No \"output\" file" << endl;
+    cout << "W" << endl;
+    exit(0);
+  }
+  using Checker = std::function<ll(const Cowputer&,bool)>;
+  vector<Checker> TASKS{
+    {task1},
+    {task2},
+    {task3},
+    {task4},
+    {task5},
+    {task6},
+    {task7},
+  };
+
+  map<ll,Cowputer> MS;
+  Cowputer RULES;
+  ll task = -1;
+  while(!in.eof()) {
+    string line;
+    getline(in, line);
+    string PREFIX = "# TASK";
+    if(line.find(PREFIX)==0) {
+      stringstream ss(line);
+      if(task != -1) {
+        fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task));
+        MS[task] = RULES;
+        RULES.clear();
+      }
+      string hash; string label; ll new_task;
+      ss >> hash >> label >> new_task;
+      fassert(hash == "#", "TASK LINE must start with '# TASK' line="+line);
+      fassert(label == "TASK", "TASK LINE must start with '# TASK' line="+line);
+      fassert(1<=new_task && new_task<=TASKS.size(), "Unknown TASK="+std::to_string(new_task));
+      task = new_task-1;
+    }
+    bool isempty = true;
+    for(ll i=0; i<line.size(); i++) {
+      if(!isspace(line[i])) {
+        isempty = false;
+      }
+    }
+    if(isempty || line[0]=='#') { continue; }
+    fassert(task!=-1, "Must have '# TASK' line before any rules task="+std::to_string(task));
+
+    stringstream ss(line);
+    string state; char seen; string arrow; string new_state; char write; char action;
+    ss >> state >> seen >> arrow >> new_state >> write >> action;
+    fassert(('A'<=seen && seen<='Z') || ('a'<=seen && seen<='z') || ('0'<=seen && seen<='9'), "SYMBOL must be alphanumeric got="+std::string(1,seen));
+    fassert(('A'<=write && write<='Z') || ('a'<=write && write<='z') || ('0'<=write && write<='9'), "new SYMBOL must be alphanumeric got="+std::string(1,write));
+    fassert(arrow == "->", "BAD ARROW line="+line+" arrow=" + arrow);
+    assert(arrow == "->");
+    if(RULES.count(state)==0) {
+      RULES[state] = map<char,tuple<string,char,char>>{};
+    }
+    fassert(set<char>{'L', 'R', 'S', 'H'}.count(action)==1, "Action must be one of L(EFT) R(IGHT) S(TAY) H(ALT) got="+std::to_string(action));
+    fassert(RULES[state].count(seen)==0, "Duplicate rule detected state="+state+" char="+std::string(1, seen));
+    RULES[state][seen] = make_tuple(new_state, write, action);
+  }
+  if(task != -1) {
+    fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task));
+    MS[task] = RULES;
+  }
+
+  ll score = 0;
+  for(auto& kv : MS) {
+    ll task; Cowputer M;
+    std::tie(task, M) = kv;
+    if(M.size() > 1000) {
+      cerr << "You used more than 1000 internal states for task=" << task << endl;
+      continue;
+    }
+    Checker check = TASKS[task];
+    ll points = check(M, TRACE==task+1);
+    score += points;
+    cerr << "Task " << (task+1) << ": " << points << endl;
+  }
+  cout << score << endl;
+}
diff --git a/2020/day6/milkvisits.cpp b/2020/day6/milkvisits.cpp
new file mode 100644
index 0000000..d18c457
--- /dev/null
+++ b/2020/day6/milkvisits.cpp
@@ -0,0 +1,61 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+
+vector<int> G[100001];
+
+vector<int> path16[17][17];
+ii ans16[17];
+void dfs16(int r, int u, int p) {
+	path16[r][u] = path16[r][p], path16[r][u].push_back(u);
+	for (auto& v : G[u]) if (v != p) dfs16(r, v, u);
+}
+
+int main() {
+	int N, M;
+	cin >> N >> M;
+	for (int i = 1; i < N; ++i) {
+		int a, b;
+		cin >> a >> b;
+		G[a].push_back(b), G[b].push_back(a);
+	}
+
+	if (N <= 16) {
+		pair<ii, char> Q[17];
+		fill(ans16 + 1, ans16 + N + 1, ii(-1, 0));
+		for (int i = 0; i < M; ++i) cin >> Q[i].f.f >> Q[i].f.s >> Q[i].s;
+		for (int u = 1; u <= N; ++u) dfs16(u, u, 0);
+		for (int y = 0; y < (1 << N); ++y) {
+			int m = 2 * y;
+			bool pass = 1;
+			for (int i = 0; i < M && pass; ++i) {
+				bool flag = 0;
+				for (auto& x : path16[Q[i].f.f][Q[i].f.s]) {
+					if ((1 & (m >> x)) == (Q[i].s == 'G')) flag = 1;
+				}
+				if (!flag) pass = 0;
+			}
+			if (pass) {
+				for (int i = 1; i <= N; ++i) {
+					if (ans16[i].f == -1) ans16[i].f = (1 & (m >> i));
+					else if ((1 & (m >> i)) != ans16[i].f) ans16[i].s = 1;
+					ans16[i].f = (1 & (m >> i));
+				}
+			}
+		}
+		if (ans16[1].f == -1) {
+			cout << "NO\n";
+		}
+		else {
+			cout << "YES\n";
+			for (int i = 1; i <= N; ++i) cout << (ans16[i].f ? 'G' : 'H') << (ans16[i].s ? '?' : '!') << '\n';
+		}
+	}
+	else {
+		
+
+
+	}
+}
\ No newline at end of file
diff --git a/2020/practice/babynames.cpp b/2020/practice/babynames.cpp
new file mode 100644
index 0000000..42a5629
--- /dev/null
+++ b/2020/practice/babynames.cpp
@@ -0,0 +1,93 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+constexpr int M1 = 8191, M2 = 1e9+7;
+
+string s[10001];
+vector<int> h[10001];
+int r[10001], hs[2][10001];
+
+inline void print(int x, int d) {
+	cout << "MOO ";
+	for (int i = 0; i < d; ++i) cout << (1 & (x >> i));
+	cout << endl;
+}
+
+inline int read(int d) {
+	int x = 0;
+	for (int i = 0; i < 16; ++i) {
+		char c;
+		cin >> c;
+		if (c == '1') x |= (1 << i);
+	}
+	return x;
+}
+
+inline int hsh(string& s, int m) {
+	ll x = 0;
+	for (auto& c : s) x *= 31, x += c - 'a', x %= m;
+	return x;
+}
+
+int main() {
+	ofstream debug("debug");
+
+	int c, n[2];
+	cin >> c >> n[0];
+	for (int i = 0; i < n[0]; ++i) {
+		cin >> s[i];
+		hs[0][i] = hsh(s[i], M1);
+		hs[1][i] = hsh(s[i], M2);
+	}
+	if (c) {
+		print(n[0], 16);
+		debug << 1 << ' ' << n[1];
+		n[1] = read(16);
+
+		for (int i = 0; i < n[0]; ++i) {
+			print(hs[0][i], 13);
+			bool b;
+			cin >> b;
+			if (b == 1) {
+				print(hs[1][i], 30);
+				cin >> b;
+				if (b == 1) {
+					cout << "RETURN " << s[i] << endl;
+					return 0;
+				}
+			}
+		}
+	}
+	else {
+		n[1] = read(16);
+		debug << 0 << ' ' << n[1];
+		print(n[0], 16);
+		
+		for (int i = 0; i < n[0]; ++i) {
+			h[hs[0][i]].push_back(i);
+		}
+		for (int i = 0; i < n[1]; ++i) {
+			r[i] = read(13);
+			if (h[r[i]].empty()) {
+				print(0, 1);
+			}
+			else {
+				print(1, 1);
+				int x;
+				x = read(30);
+				bool ans = 0;
+				for (auto& y : h[r[i]]) {
+					if (hs[1][y] == x) {
+						ans = 1;
+						cout << "RETURN " << s[y] << endl;
+						print(1, 1);
+						return 0;
+					}
+				}
+				if (!ans) {
+					print(0, 1);
+				}
+			}
+		}
+	}
+}
\ No newline at end of file
diff --git a/2020/practice/cowforce.cpp b/2020/practice/cowforce.cpp
new file mode 100644
index 0000000..71ef087
--- /dev/null
+++ b/2020/practice/cowforce.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+ll t[303][303], dp[303][303][303];
+
+int main() {
+	int N, M, K;
+	cin >> N >> M >> K;
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < M; ++j) cin >> t[i][j];
+	}
+
+	memset(dp, '?', sizeof dp);
+	memset(dp[0], 0, sizeof dp[0]);
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < M; ++j) {
+			for (int k = 0; k < M; ++k) {
+				if (j != k) dp[i + 1][j][k] = min(dp[i][j][k] + t[i][j] + t[i][k], dp[i + 1][j][k]);
+			}
+		}
+		for (int j = 0; j < M; ++j) {
+			for (int k = 0; k < M; ++k) {
+				if (j > 0 && j - 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j - 1][k] + K, dp[i + 1][j][k]);
+				if (k > 0 && j != k - 1) dp[i + 1][j][k] = min(dp[i + 1][j][k - 1] + K, dp[i + 1][j][k]);
+			}
+		}
+		for (int j = M - 1; j >= 0; --j) {
+			for (int k = M - 1; k >= 0; --k) {
+				if (j < M - 1 && j + 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j + 1][k] + K, dp[i + 1][j][k]);
+				if (k < M - 1 && j != k + 1) dp[i + 1][j][k] = min(dp[i + 1][j][k + 1] + K, dp[i + 1][j][k]);
+			}
+		}
+	}
+	ll ans = 1e18;
+	for (int i = 0; i < M; ++i) {
+		for (int j = 0; j < M; ++j) {
+			if (i != j) ans = min(dp[N][i][j], ans);
+		}
+	}
+	cout << ans << '\n';
+}
\ No newline at end of file
diff --git a/2020/practice/data b/2020/practice/data
new file mode 100644
index 0000000..85ab75d
--- /dev/null
+++ b/2020/practice/data
@@ -0,0 +1,10 @@
+0 3
+candice
+mark
+john
+1 5
+paul
+qq
+tjhance
+candice
+bob
\ No newline at end of file
diff --git a/2020/practice/debug b/2020/practice/debug
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/2020/practice/debug
diff --git a/2020/practice/guess.cpp b/2020/practice/guess.cpp
new file mode 100644
index 0000000..a9ff0e0
--- /dev/null
+++ b/2020/practice/guess.cpp
@@ -0,0 +1,6 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int main() {
+	cout << 42 << '\n';
+}
\ No newline at end of file
diff --git a/2020/practice/test_grader.cpp b/2020/practice/test_grader.cpp
new file mode 100644
index 0000000..b7d9162
--- /dev/null
+++ b/2020/practice/test_grader.cpp
@@ -0,0 +1,264 @@
+#include <iostream>
+#include <vector>
+#include <sstream>
+#include <cassert>
+#include <set>
+#include <algorithm>
+#include <cstring>
+#include <cstdio>
+#include <sstream>
+
+#include <errno.h>
+#include <signal.h>
+#include <sys/select.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <unistd.h>
+
+using namespace std;
+
+#define L 1000000000000000LL
+
+#define RETRY(x) ({                     \
+  int _r = (x);                         \
+  while (_r == -1 && errno == EINTR) {  \
+    _r = (x);                           \
+  }                                     \
+  _r;                                   \
+})
+
+template<typename T>
+string to_string(const T& x) {
+  ostringstream sout;
+  sout << x;
+  return sout.str();
+}
+
+pid_t start_instance(int argc, char** argv, int* pipes) {
+  int pipe_a[2];
+  int pipe_b[2];
+  if (pipe(pipe_a) == -1 || pipe(pipe_b) == -1) {
+    perror("pipe");
+    return -1;
+  }
+
+  pid_t pid = fork();
+  if (pid == -1) {
+    perror("fork");
+    return -1;
+  } else if (pid == 0) {
+    close(0);
+    close(1);
+    dup2(pipe_b[0], 0);
+    dup2(pipe_a[1], 1);
+    close(pipe_a[0]);
+    close(pipe_a[1]);
+    close(pipe_b[0]);
+    close(pipe_b[1]);
+
+    char** args = (char**)malloc(sizeof(char*) * (argc + 2));
+    args[0] = strdup("stdbuf");
+    args[1] = strdup("-oL");
+    for (int i = 1; i < argc; i++) {
+      args[1 + i] = argv[i];
+    }
+    args[argc + 1] = NULL;
+    execvp("stdbuf", args);
+    perror("execvp");
+    exit(1);
+  }
+
+  close(pipe_a[1]);
+  close(pipe_b[0]);
+  pipes[0] = pipe_a[0];
+  pipes[1] = pipe_b[1];
+  return pid;
+}
+
+int main(int argc, char** argv) {
+  if (argc == 1) {
+    cout << "USAGE:" << endl;
+    cout << argv[0] << " ./test_program" << endl;
+    return 0;
+  }
+  if (signal(SIGPIPE, SIG_IGN)) {
+    perror("signal");
+    return 1;
+  }
+
+  int nfds = 1;
+  char buf[1024];
+  int rfd[2];
+  int wfd[2];
+  pid_t pids[2];
+  bool alive[2] = {true, true};
+  bool returned[2] = {false, false};
+  string return_val[2] = {"", ""};
+  for (int i = 0; i < 2; i++) {
+    int pipe_tmp[2];
+    pids[i] = start_instance(argc, argv, pipe_tmp);
+    if (pids[i] == -1) {
+      cerr << "failed to start solution program" << endl;
+      return 1;
+    }
+
+    rfd[i] = pipe_tmp[0];
+    wfd[i] = pipe_tmp[1];
+    nfds = max(nfds, max(rfd[i], wfd[i])) + 1;
+  }
+
+  int ign;
+  vector<string > names[2];
+  string in[2];
+  string out[2];
+
+  set<string> names_set[2];
+  for (int i = 0; i < 2; i++) {
+    int sz;
+    cin >> ign >> sz;
+    names[i].resize(sz);
+
+    out[i] = to_string(i) + " " + to_string(sz) + "\n";
+    for (int j = 0; j < sz; j++) {
+      cin >> names[i][j];
+      assert(0 <= names[i][j].size() && names[i][j].size() <= 100);
+      for(int k = 0; k < names[i][j].size(); k++){
+        assert('a' <= names[i][j][k] && names[i][j][k] <= 'z');
+      }
+
+      if (j) out[i] += ' ';
+      out[i] += names[i][j];
+    }
+    out[i] += '\n';
+
+    names_set[i] = set<string>(names[i].begin(), names[i].end());
+    assert(names_set[i].size() == names[i].size());
+  }
+  vector<string> intersection;
+  for(auto it = names_set[0].begin(); it != names_set[0].end(); ++it){
+    if(names_set[1].count(*it)){
+      cerr << "COMMON NAME: " << *it << endl;
+      intersection.push_back(*it);
+    }
+  }
+  assert(intersection.size() == 1);
+  string answer_val = intersection[0];
+
+  int total_bits = 0;
+  for (; alive[0] || alive[1]; ) {
+    fd_set rfds;
+    fd_set wfds;
+    FD_ZERO(&rfds);
+    FD_ZERO(&wfds);
+    for (int i = 0; i < 2; i++) {
+      if (!alive[i]) {
+        continue;
+      }
+      FD_SET(rfd[i], &rfds);
+      if (out[i].size()) {
+        FD_SET(wfd[i], &wfds);
+      }
+    }
+
+    if (RETRY(select(nfds, &rfds, &wfds, NULL, NULL)) == -1) {
+      perror("select");
+      cout << "E" << endl;
+      return 0;
+    }
+
+    for (int i = 0; i < 2; i++) {
+      if (FD_ISSET(rfd[i], &rfds)) {
+        ssize_t amt = RETRY(read(rfd[i], buf, sizeof(buf)));
+        if (amt <= 0) {
+          close(rfd[i]);
+          close(wfd[i]);
+          alive[i] = false;
+          cerr << "Cow " << i << " communication closed" << endl;
+          continue;
+        }
+        in[i] += string(buf, amt);
+        cerr << "COW[" << i << "]: " << string(buf, amt) << endl;
+
+        for(;;) {
+          int nline = in[i].find('\n');
+          if (nline == -1) {
+            break;
+          }
+          string line = in[i].substr(0, nline);
+          in[i] = in[i].substr(nline + 1);
+
+          istringstream sin(line);
+          string cmd; sin >> cmd;
+          if (cmd == "MOO") {
+            string data; sin >> data;
+            for (int j = 0; j < data.size(); j++) {
+              if (data[j] != '0' && data[j] != '1') {
+                cerr << "Cow " << i << " tried to moo non-binary" << endl;
+                return 1;
+              }
+            }
+            out[1 - i] += data + "\n";
+            total_bits += data.size();
+          } else if (cmd == "RETURN") {
+            string val;
+            sin >> val;
+            if (returned[i]) {
+              cerr << "Same cow cannot return twice" << endl;
+              return 1;
+            } else {
+              returned[i] = true;
+              return_val[i] = val;
+            }
+          } else {
+            cerr << "Unknown command from cow " << i << endl;
+            return 1;
+          }
+        }
+        if (in[i].size() > 7000000) {
+          cerr << "Line too long from cow " << i << endl;
+          return 1;
+        }
+      }
+      if (FD_ISSET(wfd[i], &wfds)) {
+        // cerr << "TO COW[" << i << "]: " << out[i] << endl;
+        ssize_t amt = RETRY(write(wfd[i], out[i].data(), out[i].size()));
+        if (amt <= 0) {
+          close(rfd[i]);
+          close(wfd[i]);
+          alive[i] = false;
+          cerr << "Cow " << i << " communication closed" << endl;
+          continue;
+        } else {
+          out[i] = out[i].substr(amt);
+        }
+      }
+    }
+  }
+  for (int i = 0; i < 2; i++) {
+    int status = 0;
+    if (RETRY(waitpid(pids[i], &status, 0)) == -1) {
+      perror("waitpid");
+      return 1;
+    }
+    if (WIFSIGNALED(status)) {
+      cerr << "Cow " << i << " crashed" << endl;
+      return 1;
+    }
+  }
+
+  for (int i = 0; i < 2; i++) {
+    if (returned[i] && return_val[i] != answer_val) {
+      cerr << "Cow " << i << " returned the wrong value" << endl;
+      return 1;
+    }
+  }
+  if (!returned[0] && !returned[1]) {
+    cerr << "Neither cow returned a value" << endl;
+    return 1;
+  }
+
+  cerr << "Found correct name " << answer_val << " using " <<
+          total_bits << " total bits." << endl;
+
+  return 0;
+}
diff --git a/README.md b/README.md
index 8b2bceb..5f5538c 100644
--- a/README.md
+++ b/README.md
@@ -1,2 +1,3 @@
 # USACO-Camp
-Short, concise solutions for problems from the USACO camp
+
+Short, concise solutions for problems from the USACO camp. You won't find any problems here, just solutions.