Codeforces Round 968 (Div. 2) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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	800	800	1200	1500	2100	2600	2700	2800

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