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
The first character of $$$t_1$$$ isn't equal to the last character of $$$t_k$$$.
Solution
Tutorial is loading...
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
Try to rephrase the operations of both players.
Solution
Tutorial is loading...
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;
}
Hint
You should understand what is a good pair.
Solution
Tutorial is loading...
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
Choose the same integer twice.
Solution
Tutorial is loading...
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
Construct a directed graph and rephrase the operation.
Solution
Tutorial is loading...
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
Divide all numbers into small numbers and large numbers.
Hint 2
Use DP.
Solution
Tutorial is loading...
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
Try to handle overlapping intervals.
Solution
Tutorial is loading...
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
There exists a $$$O(n + m)$$$ solution to this problem.
2003F - Turtle and Three Sequences
Hint 1
What will you do if the number of possible values for $$$b_i$$$ is small?
Hint 2
Try some randomized algorithms, like color-coding.
Solution
Tutorial is loading...
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;
}
