Codeforces Round 968 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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

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
en10	zltzlt	2024-09-03 02:17:14	38
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