Codeforces Round 968 (Div. 2) Editorial

#	User	Rating
1	tourist	3947
2	jiangly	3734
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	ecnerwala	3581
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3479

#	User	Contrib.
1	awoo	162
2	maomao90	160
3	nor	156
3	cry	156
5	atcoder_official	155
5	-is-this-fft-	155
7	maroonrk	154
7	adamant	154
9	Petr	146
10	djm03178	145

Thank you for your participation!

Rating Predictions

Person	A	B	C	D1	D2	E1	E2	F
zltzlt	800	1100	1500	1300	2100	2100	2300	2500
WRuperD	800	1200	1400	1800	2300	2400	2600	2800
Ender32k	800	1100	1400	1900	2200
yinhee	900	1200	1600	1500	1900	2400	2500	2700
Jryno1	800	1100	1500	1500	1800
yeminghan	800	900	1500	1400	1900	2700	2800
wutongchun	800	900	1300	1500	1900	2700		3000
small_peter	800	1200	1600	1900	1900
DisconnectedGraph	800	1200	1400	1700	2000	2000	2600
sinsop90	900	1300	1500	1900

	A	B	C	D1	D2	E1	E2	F
Average	820	1120	1470	1630	2000	2383	2560	2750
Actual

2003A - Turtle and Good Strings

Hint

Solution

Code

#include <cstdio>

const int maxn = 110;

int n;
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	puts(s[1] != s[n] ? "Yes" : "No");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003B - Turtle and Piggy Are Playing a Game 2

Hint

Solution

Code

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

const int maxn = 100100;

int n, a[maxn];

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1, greater<int>());
	printf("%d\n", a[(n + 1) / 2]);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003C - Turtle and Good Pairs

Hint

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1000100;

int n;
pii a[99];
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	for (int i = 0; i < 26; ++i) {
		a[i] = mkp(0, i);
	}
	for (int i = 1; i <= n; ++i) {
		++a[s[i] - 'a'].fst;
	}
	sort(a, a + 26, greater<pii>());
	queue<pii> q;
	while (a[0].fst > a[1].fst) {
		putchar('a' + a[0].scd);
		--a[0].fst;
	}
	for (int i = 0; i < 26; ++i) {
		q.push(a[i]);
	}
	while (q.size()) {
		pii p = q.front();
		q.pop();
		if (!p.fst) {
			continue;
		}
		putchar('a' + p.scd);
		--p.fst;
		q.push(p);
	}
	putchar('\n');
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003D1 - Turtle and a MEX Problem (Easy Version)

Hint

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, a[maxn];
bool vis[maxn];

void solve() {
	scanf("%lld%lld", &n, &m);
	ll k = 0;
	while (n--) {
		int t;
		scanf("%d", &t);
		for (int i = 0; i <= t + 5; ++i) {
			vis[i] = 0;
		}
		for (int i = 1; i <= t; ++i) {
			scanf("%lld", &a[i]);
			if (a[i] <= t + 4) {
				vis[a[i]] = 1;
			}
		}
		ll mex = 0;
		while (vis[mex]) {
			++mex;
		}
		vis[mex] = 1;
		while (vis[mex]) {
			++mex;
		}
		k = max(k, mex);
	}
	printf("%lld\n", k >= m ? (m + 1) * k : k * k + (m + k) * (m - k + 1) / 2);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003D2 - Turtle and a MEX Problem (Hard Version)

Hint

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, a[maxn], f[maxn];
pii b[maxn];
bool vis[maxn];
vector<int> G[maxn];

inline ll calc(ll l, ll r) {
	return (l + r) * (r - l + 1) / 2;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	ll t = -1, ans = 0, k = 0;
	for (int i = 1, l; i <= n; ++i) {
		scanf("%d", &l);
		for (int j = 1; j <= l; ++j) {
			scanf("%lld", &a[j]);
			if (a[j] < maxn) {
				vis[a[j]] = 1;
			}
		}
		ll u = 0;
		while (vis[u]) {
			++u;
		}
		t = max(t, u);
		ll v = u;
		vis[u] = 1;
		while (vis[v]) {
			++v;
		}
		b[i] = mkp(u, v);
		k = max(k, v);
		vis[u] = 0;
		for (int j = 1; j <= l; ++j) {
			if (a[j] < maxn) {
				vis[a[j]] = 0;
			}
		}
	}
	for (int i = 0; i <= k; ++i) {
		vector<int>().swap(G[i]);
	}
	for (int i = 1; i <= n; ++i) {
		G[b[i].fst].pb(b[i].scd);
	}
	for (int u = k; ~u; --u) {
		f[u] = u;
		for (int v : G[u]) {
			f[u] = max(f[u], f[v]);
		}
		if ((int)G[u].size() >= 2) {
			t = max(t, f[u]);
		}
	}
	for (int i = 0; i <= min(k, m); ++i) {
		ans += max(t, f[i]);
	}
	if (k < m) {
		ans += calc(k + 1, m);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003E1 - Turtle and Inversions (Easy Version)

Hint 1

Hint 2

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 5050;

int n, m, f[maxn][maxn], a[maxn], b[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n + 1; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			f[i][j] = -1e9;
		}
		a[i] = 0;
	}
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		a[l] = r;
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			int p = a[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = f[i - 1][j] + j;
				if (j) {
					f[i][j] = max(f[i][j], f[i - 1][j - 1]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

2003E2 - Turtle and Inversions (Hard Version)

Hint

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 5050;
const int inf = 0x3f3f3f3f;

int n, m, b[maxn], c[maxn], f[maxn][maxn];
struct node {
	int l, r;
} a[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		c[i] = -1;
		b[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].l, &a[i].r);
	}
	if (!m) {
		printf("%d\n", n * (n - 1) / 2);
		return;
	}
	sort(a + 1, a + m + 1, [&](const node &a, const node &b) {
		return a.l < b.l;
	});
	int mnl = a[1].l, mxl = a[1].l, mnr = a[1].r, mxr = a[1].r;
	for (int i = 2; i <= m + 1; ++i) {
		if (i == m + 1 || a[i].l > mxr) {
			if (mxl >= mnr) {
				puts("-1");
				return;
			}
			for (int j = mnl; j < mxl; ++j) {
				c[j] = 0;
			}
			for (int j = mnr + 1; j <= mxr; ++j) {
				c[j] = 1;
			}
			b[mxl] = mnr;
			mnl = mxl = a[i].l;
			mnr = mxr = a[i].r;
		} else {
			mnl = min(mnl, a[i].l);
			mxl = max(mxl, a[i].l);
			mnr = min(mnr, a[i].r);
			mxr = max(mxr, a[i].r);
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			f[i][j] = -inf;
		}
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (b[i]) {
			int p = b[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else if (c[i] == 1) {
			for (int j = 1; j <= i; ++j) {
				f[i][j] = f[i - 1][j - 1];
			}
		} else if (c[i] == 0) {
			for (int j = 0; j < i; ++j) {
				f[i][j] = f[i - 1][j] + j;
			}
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = max(f[i - 1][j] + j, j ? f[i - 1][j - 1] : -inf);
			}
		}
	}
	int ans = -1;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Bonus

2003F - Turtle and Three Sequences

Hint 1

Hint 2

Solution

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 3030;

int n, m, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];

struct BIT {
	int c[maxn];
	
	inline void init() {
		mems(c, -0x3f);
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = -1e9;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
} T[32];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
	}
	mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
	int ans = 0;
	for (int _ = 0; _ < 300; ++_) {
		for (int i = 1; i <= n; ++i) {
			d[i] = rnd() % m;
		}
		for (int i = 1; i <= n; ++i) {
			e[i] = d[b[i]];
		}
		for (int i = 0; i < (1 << m); ++i) {
			T[i].init();
		}
		T[0].update(1, 0);
		for (int i = 1; i <= n; ++i) {
			for (int S = 0; S < (1 << m); ++S) {
				if (S & (1 << e[i])) {
					continue;
				}
				T[S | (1 << e[i])].update(a[i], T[S].query(a[i]) + c[i]);
			}
		}
		ans = max(ans, T[(1 << m) - 1].query(n));
	}
	printf("%d\n", ans > 0 ? ans : -1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Rev.	By	When	Δ	Comment
en9	zltzlt	2024-08-25 19:41:11	0	(published)
en8	zltzlt	2024-08-25 19:40:58	7
en7	zltzlt	2024-08-25 19:40:28	1
en6	zltzlt	2024-08-25 19:39:26	34	Tiny change: '\n\n<spoil' -> 'Thank you for your participation!\n\n<spoil'
en5	zltzlt	2024-08-24 05:04:59	94
en4	zltzlt	2024-08-24 03:43:59	9
en3	zltzlt	2024-08-24 03:42:19	11342
en2	zltzlt	2024-08-20 17:32:51	31
en1	zltzlt	2024-08-20 17:32:15	1335	Initial revision (saved to drafts)

History