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 | |||
| Zunpet | 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;
}
ProofByACForces :)
Proof by magic :)
Problem d2
can any one explain the why this if statement is used to find max and how we will using it. I dont get the idea of why we storing.
I created video editorial for D1 and D2
Note: This is not a detailed video editorial. Instead, I walk you through my thought process using which I arrived at the solution. Use it as a supplement to the official editorial.
Update: I also added commentary for the DP Mindset require to solve the easy version of F.
Bang on whatta explaination realy, but still I miss the fact what with the if statement. If you free pm me lets discuss this approach more thoroughly
great as always .
Thanks for fast editorial.
Thanks for the amazing contest :) What topics should I learn To solve D2?
I think DSU and some concept of DP will do
Any good resource for DSU?
You can learn about DSU in the cp handbook https://cses.fi/book/book.pdf in the section named "Union-find Structure"
check in the “edu” section
dfs
topological sorting.
i panicked and got 2 WAs on A, and then got 2 unnecessary WAs on D1 with some spaghetti code. fml
I found problem A very easy to misread as well. I wish the sample tests were better.
Same here, i didn't read For all i < j
very nice problem set.
enjoyed solving problem $$$D$$$.
the worse case of input is already O(n^2)? Is my understanding wrong?
if you read the problem statement it clearly says something along the lines of "sum of all l[i] across all testcases does not exceed 2e5"
got it, thanks.
Amazing contest and GREAT IDEAs !!!
In my solution to F, the probability of not obtaining the optimal solution is $$$(\dfrac{5!-1}{5!})^{600} = 6 \cdot 10^{-3}$$$ which is actually not very good. But there are only 65 tests so I passed pretests :)
Upd: Passed System test, seems that I'm lucky :)
U Rainboy's alt or what dude
In problem C solution:
Why is this optimal? Why not just alternate most frequent character not only with the second most frequent, but with others as well? The rest is obvious but this part is just an assumption basically.
Going further, does the order of frequencies really matter? Don't we just need to alternate characters in lexicographical order until there are no more left?
This does indeed work, because consider this algorithm:
At the first position place any character. At the $$$i$$$-th position place any character that is different from the one that you placed at $$$i-1$$$-th position. This algorithm will stop only if you exhausted all characters, or if you have left only characters of one kind $$$c$$$. Then place all the remaining $$$c$$$'s at the end.
In this way you will have at most 1 segment of the same characters of length more than 1 (at the end). I think this is the same result the editorial solution gets.
I tried alternate most frequent character with all others, it passed pretests.
It's not so hard. There's something much easier than this solution.
Just sort the string then print them in an order like $$$1,n,2,n-1,3,n-2,\dots$$$, and that's all.
But I just can't prove it.
I did the same thing. I wasn't too sure about my solution so I proved it and that made me submit the problem after one hour.
I guess it works because you don't actually care too much about the characters themselves, but only about the changes.
Define a change as the number of $$$i$$$ such that $$$s_{i}\neq s_{i+1}$$$.
- If in a given substring you only have zero changes, then the first character is equal to the last and that is good.
- If you have only one change then your substring looks like "aa...aabb...bb". Let $$$i$$$ be the only change, the only index such that $$$s_{i}\neq s_{i+1}$$$, you have that $$$s_{i}=s_{l}$$$ and $$$s_{i+1}=s_{r}$$$ (where $$$l$$$ and $$$r$$$ are the first and the last character of the substring), so $$$(l,r)$$$ isn't a good pair.
- If there is more than one change it's good. If there are three or more different type of characters you can obviously find a change such that $$$s_{i}\neq s_{l}$$$ or $$$s_{i+1}\neq s_{r}$$$. If it is made only of two type of characters the substring has a block of characters of the first type, then a block of the second type, a block of the first, and so on... So if you take look at the second change you'll have that $$$s_{i}$$$ is of the second type and is different from $$$s_{l}$$$, and $$$s_{i+1}$$$ is of the first type so it is different from $$$s_{i}$$$. Note that it doesn't matter if $$$s_{i+1}=s_{r}$$$ because you know that $$$s_{i}\neq s_{l}$$$.
Now, sorting the string as you said is optimal because you minimize the number of $$$i$$$ such that $$$s_{i}=s_{i+1}$$$ so you maximize the changes in every substring. And in particular there will be zero such indices unless there is a type of characters which occurs more than $$$\frac{n}{2}$$$ times, case in which you can't do better.
In this sorting every substring will have one change only if the size of the substring is 2. Here you know you can't do better because in a substring with only two elements you can have zero or one changes, but having zero instead of one won't increase the number of good indices because regardless of the sorting, there are $$$x$$$ characters of that type and the substring with that character in the first and last position will always be $$$\frac{x(x-1)}{2}$$$.
Hope that helps :))
I don't think this is true. Using order 1, n, 2, n-1, ... does not maximize the changes.
Imagine the sequence 1, 2, 2, 2, 3. Using the order 1, n, 2, n-1, ... we would get 1, 3, 2, 2, 2. This is two changes. We can get five changes with the sequence 2, 1, 2, 3, 2.
Doesn't this not work for initial string "baa" which makes the new string "aba" which has less pairs than the original?
OK, so I've thought about it, here's a better proof at least for me to understand. Let's just alternate characters, it's optimal because of the sum we need to minimize. If the most frequent character appears less than n/2 times in the string then we can alternate easily. Otherwise we can cap the most frequent character occurrence by n/2 and build an alternating string, but then we will have a block of the same characters left that we need to insert in the string somewhere. We can insert it only at the beginning or the end, because there it's going to be calculated in the sum only once.
Pretty good problem actually, if you think about it, thanks.
Super fast Editorial...
btw problems were good <3
Anyone has a solution for F without using randomization? I tried to using some kind of meet in the middle, but it's too hard to merge the answer
Here's a deterministic solution:
Let's refer to elements with the same $$$b_i$$$ as a "class".
Loop through all possible values of $$$2^{nd}$$$ and $$$4^{th}$$$ numbers and check the validity of the pair. Now, we have three more elements to fill: the one to the left, between two numbers, and the one to the right. For each of these, we know the range of possible values of $$$a$$$.
Notice that if we consider the five best classes of elements of a set (with the highest maximum cost of elements belonging to that class), then the best element to select in this set will always be among those 5 (the other ones can ban at most 4 classes). So, we need the five best classes for all prefixes with $$$a$$$ bounded from above by the next element, and for all suffixes with $$$a$$$ bounded from below by the previous element. This can be precalculated easily in $$$O(n^2)$$$.
The interesting part is what to do with the middle elements (they have both upper and lower bounds for $$$a_i$$$). We can maintain a segment tree that works sort of like a merge sort tree, but only stores the 5 best classes. The "key" will be the value of $$$a$$$. The segment tree is cleared for each new value of second element, and as we iterate over the fourth elements, we add all the stuff that we already passed to the segtree. So, we can get the middle elements in $$$O(5 \log n)$$$.
Finally, we just have to merge the three groups of $$$5$$$ values using $$$5^3$$$ time.
The final time complexity is $$$O(n^2 \log n + n^2 5^3)$$$, or $$$O \left( n^{\lfloor \frac{m}{2} \rfloor} \left( m \log n + m^{\lceil \frac{m}{2} \rceil} \right) \right)$$$ in the general case, which is (barely) good enough.
P. S. Please excuse my usage of numbers inside $$$O()$$$ notation here, it was just too convenient to write it like that :)
I think this meet-in-the-middle solution works in $$$O(24 * n^2)$$$: 278171336.
I maintain the top 3 answers for pairs ending at i as L[i], and for pairs starting at i as R[i]. Since all pairs ending at an index have the color of that index, we need to store the best 3 pairs of different second color. So L[i] would have answers with (x, b[i]), (y, b[i]), (z, b[i]).
Now we can brute-force the 3rd element $$$i$$$ (when k = 5) and merge it with the best 1st and 2nd element across all L[j] (j<i) (there are at most $$$3\times (i-1)$$$ options stored). The only difference is that in this merge, we need to maintain the top 4 answers ignoring the color of $$$i$$$ itself. For example, if (x, y) are the colors of the best 1st and 2nd elements, we need to store the top answer for each of these 4 combinations: {includes x or not} $$$\times$$$ {include y or not}. This is because the best 4th and 5th elements may need x, y, or both of them.
Finally we do the same but to the right, and then merge the left and right answers at each 3rd element $$$i$$$ and maximize.
I got the same idea and had a bad time inplementing that :)
The constant factor is too large for the segtree part and I can only store the 2 biggest values. Beside that some optimizations on the constant factor is also needed for me.
Anyway the data was weak enough for that to pass 278190335
The technique in Problem F can be directly derandomized.
We need a family of hash functions $$$\mathcal{H} = \{ h_i \colon [n] \to [k] \}$$$ such that for any subset $$$S \subseteq [n]$$$ of cardinality $$$k$$$, there exists a hash function $$$h_i$$$ in $$$\mathcal{H}$$$ that satisfies $$$h_i(S) = [k]$$$. This is known as an $$$(n,k,k)$$$-splitter. Once we have such a splitter, we can solve the problem by trying each hash function $$$h_i$$$ from this family.
Randomly selecting a hash function is likely sufficient with high probability when $$$|\mathcal{H}|$$$ is sufficiently large. Note that for each $$$S$$$, the probability that none of the $$$h_i$$$ splits $$$S$$$ is
there are $$$n^k$$$ many such subsets, so we need
is much smaller than $$$1$$$. We need to take $$$|\mathcal H| \geq \frac{k^k}{k!} \cdot k\log n$$$.
The difference between the analysis above and the official solution is that, once you generates a good $$$\mathcal H$$$, it doesn't only works correctly for a current test case, it universally works for all test cases! One practical solution is to hardcode a random seed in your program that has been verified to generate a splitter $$$\mathcal{H}$$$.
BTW, the explicit construction of an $$$(n,k,k)$$$-splitter is theoretically nearly settled by the paper "Splitters and Near-Optimal Derandomization". The authors show how to construct a family of size $$$e^k k^{O(\log k)} \log n$$$. Note that the probabilistic method gives $$$\frac{k^k}{k!} \cdot k\log n$$$, and since $$$\frac{k^k}{k!} \approx e^k k^{1/2}$$$, the explicit construction is quite close to the probabilistic bound.
How Elegia's mind works
I like the idea and firmly believe such splitters exist, but how to verify that the constructed $$$\mathcal{H}$$$ is indeed a $$$(n, k, k)$$$-splitter? Is there a deterministic approach or just checking a lot of subsets is enough? How many subsets should I check to verify that it is a splitter with 99.9999% probability?
Good question, I'm not sure is there any algorithm significantly better than checking all the $$$k$$$-subsets...
Thanks for your help, I have got AC using some kind of MITM :). Feel free to hack my submission!
I have tried to uphack my submission which editing the magic constant
MAX_HOLDinto $$$15$$$ or $$$20$$$ but not successful. Can anyone help me to hack this and this, or prove that is enough for solving this problem? Thanks!In the problem C, can we just rotate the character of array and just print it?? or missing something!?
what do you mean by "rotate"? because if it means reversing the string then no, if so then the number of good pairs would remain the same.
moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"
well, if you passed this problem, then this solution might as well be right, but otherwise i don't really think so, as the increment of good pairs count can't be more than n-1
yes, it failed in test-case 2 Can you tell -What's does this means- wrong answer Participant's answer is worse than jury's: jans = 6, pans = 5. (test case 18) link — 278153049
i think it means whilst your answer consists of 5 good pairs (pans means participant's answer), the jury's answer has 6 of them
It wouldn't work. If you have, for example, "edddfg", you rotate and get "gedddf", but "gefddd" is better.
D1 was nice :)
D2 is even nicer. Problem looks difficult. but all you have to do is, travel from left to right, and right to left. and keep propagating the maximum. that's it.
got TLE on D at the last minute by using loop from 0->m :)
terrible contest! D is much easier then C, B can only be guessed, not solved.
Also I got RE26 on D2 using c++20 and WA30 using c++17, how can this be?
Sorry to bother, could D2 be solved by using union-set to get maximal for each vertex?
Idk, I used only dp
also used dp and got rt, make sure that u are initializing dp to the longest size of l_i read
B can be reframed that the person trying to minimise removes the largest number possible, and the person maximising tries removing the lowest number possible.. so in the end, after they cut off all of the numbers from both ends turn by turn.. only thing remaining is the median of the sorted array..
Exactly
how can C and B (or D) be guessed
My first contest with AC on div2C. ThankyouThankyouThankyouThankyou!
W contest!
It seems that the "In this version of the problem, you can choose the same integer twice or more" suggests the hint "choose the same integer twice" obviously. But D2 is a good problem for Codeforces div2 D. I guess the difficulty of it is *2000.
I want to mention that I do too much guesswork in this round. Especially B and C. Although it doesn't matter that this round is a good round for me. Thanks.
:D
Problem D is really cool!
Weak system tests for C.
My code: 278099825
A very stupid mistake, I forgot to sort the characters by how often they occur in s, as a result for the test:
1
4
ddbc
My code outputs: bcdd (which has 2 good pairs: (0; 2); (0; 3))
One of the correct answers: dbcd (which has 3 good pairs: (0; 2); (0; 3); (1; 3))
Despite this, my code has passed the system tests and got AC
you shouldn't count (0, 3) in dbcd since it's the same character so it wont count in the additional good pairs
You code output has also one more good pair : (2,3)
Yes, you are right. Thank you. I am sorry. I didn't notice that there exists pairs with len of 2 that can be a good pair
I think it's harder to find the right strategy in C than in D1.
Thanks for D2. It was fun
(And yes, I will finally turn blue)
Alternate solution to E1 :
Lemma 1 : Every interval must have either exactly 1 0, or exactly 1 1(where the definition of 0s and 1s are same as editorial)
Proof : The optimum solution must be a local minimum. Fix the other segments and vary the number of 0s and 1s in one segment, it is a quadriatic function with central maxima. Hence, it is minimized at the ends of allowed ranges.
Lemma 2 : Some prefix of intervals will have 1 1, and some suffix will have 1 0, proof is left as an exercise
Just brute the prefix, and find cost to get O(m^2). Extending to E2 is trivial as left as an exercise. This can probably be extended to get a near-linear solution by computing cost(prefix + 1) — cost(prefix) fast, but i am too lazy to work out the details.
Here's a $$$\mathcal{O}(m)$$$ solution for E1 278231107
It's quite obvious that it's efficient to have all 1s in $$$[1, l_1 - 1]$$$, one 0 in $$$[l_1, r_1]$$$, all 0s in $$$[r_m + 1, n]$$$ and one 1 in $$$[l_m, r_m]$$$ no matter what numbers are used in $$$[r_1 + 1, l_m - 1]$$$. Since the numbers in the interval $$$[r_1 + 1, l_m - 1]$$$ can be chosen independently from those which are in it's complement, induction can be applied.
in problem F, why is the probability of getting the optimal solution in one attempt is $$$\frac{m!}{m^m}$$$ ?
Consider a set S = {s[1],s[2],...,s[m]} of all distinct b[i] in an optimal answer. To be able to get this answer from bitmask dp, all f(s[i]) must be distinct, where f(x) is mapping from x to a random number in [1,m]. The number of such mappings is m!*(m^(n-m)), m! is because f(s[i]) must form a permutation, m^(n-m) is because for any b[i] not included in S ,f(b[i]) can be any number and it doesn't affect answer. Number of all possible mappings is m^n, since for each b[i] there are m possibilities. Then, the probability of finding a mapping, where we can get an optimal answer is m!*(m^(n-m))/m^n = m!/m^m .
Hi, please check this 2 submissions, they have mostly the same code, the only difference is that the vectors are global in the first one. The second code gives TLE and by a big margin. Is this a bug or what? https://mirror.codeforces.com/contest/2003/submission/278156729 https://mirror.codeforces.com/contest/2003/submission/278156524
top 3 reason for depression
breakup
Substance Abuse
WA in div2 A
I solved F deterministically in $$$\mathcal{O}(n^2 * k^3)$$$:
Let’s say we compute $$$dp(i,j)$$$ = answer if we have to take $$$j$$$ elements from the suffix of the array starting at position $$$i$$$. In order to avoid repeating some values from $$$b$$$, we also store the vector of chosen values (let’s call it $$$V$$$).
The issue is that choosing exactly those values may “block” you later. To prevent this, we also compute the best answer if we avoid using each of the values from $$$V$$$ separately. It’s easy to see that one of these $$$k+1$$$ candidates will be optimal.
Although my code’s complexity is $$$\mathcal{O}(n^2 * k^3)$$$, I believe it can be improved to $$$\mathcal{O}(n^2 * k^2)$$$. Given that I got AC in the last 12 seconds of the contest, I didn’t have time to even think about optimizing anything.
Here is my submission: 278149543 :)
Hacked with this test case:
When you get to the suffix starting with b = 4, you'll only keep {4, 2} and {4, 3} as options for your b-values. But you actually need to use {4, 1} because of the 2 and 3 on the left.
Good catch! I’m surprised that there are over 60 testcases and none of them cover scenarios like this one you describe
Bad setting imo, this problem needed multitests
I really can't get this: the first player can remove a number adjacent to a larger number, while the second player can remove a number adjacent to a smaller number.
You can think of it as. 1 player can pick any 2 numbers and remove the smaller one, and the other player can pick any 2 numbers and remove the bigger one
Hey everyone, does anyone have any advice for coming up with proofs for problems (apart from solving more problems or working with smaller cases)? I have realized that I can often think of the solution, but can't prove it, so I don't end up implementing it. Any help would be greatly appreciated! :D
well I think it's fine to try and implement a solution even if you haven't completely proved it. while implementing it, you might actually notice the flaw and then you can correct it, or start coming up with a new solution. this can waste a lot of time, if you're not efficient at implementing, but it's a decent approach if you find yourself not being able to prove easy problems
What topics should I learn to solve D1 and D2?
dp — ad hoc?
I got compilation error twice in B, when I was using g++20, but the same code got accepted in g++17. Why did this happen?
Compilation error 1 : https://mirror.codeforces.com/contest/2003/submission/278061013
Compilation error 2 : https://mirror.codeforces.com/contest/2003/submission/278072152
Pretests passed : https://mirror.codeforces.com/contest/2003/submission/278078881
delayed my submission from 8 mins to 22 mins :(
I guessed B and C
Can anyone please explain, how, in example 1 for problem D1, f(4) = 4
just dont do anything? x is 4 and you can leave it be
Oops!! I got it now.. We can do zero operations to get max value of x as 4 itself.
it took me about 10 mins to understand why f(4)=4 :(
can someone help me with problem D1?
the result of mex(x,ai,1,ai,2,…,ai,li) for every sequence is only two possible mex!
for example a0= {0, 1, 3, 4} the mex of this sequence is {2, 5}
if(x == 2) mex = 5, else mex = 2. and since i can choose every sequence multiple times, then whatever the value of x is, i can get 5 (f(2) --> 5, f(number != 2) --> 2 --> f(2) --> 5)
so calculate each two mex for all sequence and choose the max_mex then the result is
(max_mex * numbers_less_than_or_equal_to_max_mex) + (max_mex + 1) + (max_mex + 2) + .... + m
278173974 (D2) I think the approach is similar to the editorial sol but I have no clue why it's failing, can someone help?
I made a big mistake of starting to code problem D before working the example cases to ensure i understood the problem. Too bad I missed a crucial part even after the notification during contest that we can pick multiple sequence and moreover we can pick the same sequence any number of times. This misunderstanding led me to solve a completely different problem.
E1 (Edit: and E2) can be solved in O(n) time:
The key observation is that after sorting 0's ("small" numbers) and 1's ("big" numbers) in descending order (separately), the number of inversions of form (i, j), where the j-th number is "small", is equal to the sum of indices of all "small" numbers (using 0-indexing). That is because for a given "small" number, it is smaller than any previous number, since 1) all previous "small" numbers are greater because we sorted them in decreasing order, 2) it it smaller by every previous "big" number, by definition. So the total number of inversions is equal to $$$\frac{b(b-1)}{2} + \sum_{}^{}i_0$$$, where $$$b$$$ is number of "big" numbers, and $$$i_0$$$ is a set of indices of "small" numbers.
Let's define a gap interval like this: for any adjacent pair of intervals $$$(l_x, r_x)$$$ and $$$(l_{x+1}, r_{x+1})$$$, $$$(r_x+1, l_{x+1}-1)$$$ is gap interval. Additionally, the border ones: $$$(1, l_1-1)$$$ and $$$(r_m+1, n)$$$ are also gap intervals. Now, another observation is that for any non-empty gap interval in an optimal permutation, it can be split into 2 parts, such that the left part consists of only "big" numbers and the right one consists of only "small" numbers (note that some part can be empty, so the whole gap interval may be filled with number of one type). That is because it is always optimal to sort the interval by decreasing order. So, we can sort of "extend" each normal interval to the left adding some "small" numbers, or to the right, adding some "big" numbers.
The solution is greedy: First assume that the permutation contains as many "big" numbers as possible, so for every interval, only the first element is "small" and we extend each interval to the right, so each element in a gap interval is "big". Now, we will gradually extend "small" numbers by extending intervals to the left (while shrinking the previous interval's right border) or, for a given interval, assuming that k+1 first elements are "small", instead of k. Now, what happens with our answer when we switch the i-th element from "big" to "small"? Basing on the first formula and doing a little bit of math, it turns out that the answer increases by $$$i+1-b$$$ (this number can be negative, so the answer can actually decrease), also note that after the operation, the value of $$$b$$$ decreases by one. Is is quite intuitive and easy to prove that we want to first expand the "small" numbers into largest indices, that way our answer will increase the most. So we expand in the following order: first, expand from the right border as much as we can. Then, expand the last interval into the right as much as possible, then to the left. Next, take the second last interval and do the exact same thing, and so on. Keep track of the answer in each point in time, and the final answer to the problem is the maximum one.
(Read the solution for E1 first)
The idea is pretty much the same as in E1, but additionally we need to check whether a solution exists, and if so, for every $$$i$$$ check if the i-th element must be "small", must be "big" or can be any (let's call the third case the free elements). We first assume all free elements are "big" and just like we did previously, we will increase the number of "small" elements by expanding them into free elements (starting from the largest indeces, same as in E1).
Implementation for E1 is very straightforward: 278182451. E2 is a little messier, but still not that bad: 278261466
Thank you for interesting problem.I've got +64!
Can someone help me with my solution of d2,which got WA on 27?
278147838
Thanks
Take a look at Ticket 17496 from CF Stress for a counter example.
Got it,thank you.
In problem D2, how is the answer to the 3rd test case 1281?
Test case:
2 50
2 1 2
2 1 2
Answer: 1281
In my calculation, only 0 is the only value on which an operation can be made to get the 3. For other values (1 — 50), just take the value itself to get a better answer. So, it's the same as: 1+2+3+...+50. And, we'll get 1275 and +3 (that we got from the value 0). Then in total, it'll be 1278.
But I didn't understand how the answer was 1281. Where is this extra 3 coming from?
For x = 1, 2. First apply the operation for i = 1. So x = mex(x, 1, 2) = 0. Now, you can apply the operation for i = 2, x = mex(0, 1, 2) = 3. So, optimal value for x = 0, 1, 2 is 3.
For values 1 and 2 you can use the first sequence to get x=0, and then use the zero with the second sequence to get x=3.
https://mirror.codeforces.com/contest/2003/submission/278211183
this is my submission can anyone help me which case i am missing ??
if(expected==(int)het.size()&&flag==1){ expected++; } Just update this
thanks
Can someone tell me why my code Wrong on C test3
wrong answer Participant's answer isn't a permutation of the given string. (test case 267)
278220017
I find it...
char s[N], n;
char s[N]; int n;
The solution of D1 was O(n * l) and 1 ≤ n ≤ 2⋅10^5, 1 ≤ l ≤ 2⋅10^5 then why it does not give TLE
sum of $$$l_i$$$ in all test cases dont exceed $$$2 \cdot 10^5$$$
I need some help with debugging my code, I seem to have every edge case covered, yet I find myself with a WA on Test 27 :( https://mirror.codeforces.com/contest/2003/submission/278263899
Solution to E1/E2 was a little hard to understand, so I'll write mine
Separation of numbers into small/big parts was also very hard to understand, so I'll write the explanation too
Consider the border of $$$max\ a_i = A$$$. Now, for some optimal answer convert every number into $$$0$$$ if $$$\leq A$$$ and $$$1$$$ otherwise. It's guaranteed by construction, that all numbers in the left parts are $$$0$$$ and right parts are $$$1$$$. On the other hand, if we have some 01 coloring, we can provide an answer greedily. That's why the iff (if and only if) statement is true.
Now let's solve the whole problem. What do we want the segments to comply with in a 01 coloring? The leftmost element must be $$$0$$$, the rightmost element must be $$$1$$$ and the numbers in the segment must be non-decreasing, or in the other words for each $$$i$$$ in $$$(l, r]$$$ $$$c_{i - 1} \leq c_i$$$ must be true.
Let's try and build some DP, in which checking this would be easy. We want to be able to check the previous number and update the total number of inversions. I think the most straightforward DP to try here is $$$dp[prefix][count\ of\ 1][last element] = \text{the max number of inversions on a prefix with given number of ones}$$$. The transitions are easy. If we add a $$$0$$$, it's the smallest number amongst the prefix, so we need to add $$$prefix$$$. If we add a $$$1$$$, it's the smallest number amongst ones, so we add $$$count\ of\ 1$$$.
Now, how do we check the conditions on the segments? Just don't iterate over states and transitions that are impossible. If the current number is fixed, just iterate over it. If we should check index $$$i$$$ to be not less than $$$i - 1$$$, do that. That's it.
Solution 278270951
Can anyone please explain to me how the following tc answer is 16 for D2? 3 4 2 0 2 3 2 3 3 4 7 0 1 5 isn't here f(0)=3, f(1)=3, f(2)= 2, f(3)=3, f(4)=4? and total is 15.
O(N) solution for E1. The logic is based on examples and reasoning, despite not a complete and rigorous proof. https://mirror.codeforces.com/contest/2003/submission/278303362
The idea is to assign value 0 or 1 to a signature array that can be used to uniquely yield the optimal permutation (similar to the concept in tutorial). There are 2 separate passes. In the first pass, we handle intervals in head and tail and meet in the middle, and maintain counters for number of 0 in prefix and number of 1s in suffix. It is optimal to place 0111...1 in head if pre0 <= suf1 and otherwise place 00...01 in tail. In the second pass, we handle indexes not within any interval. In this phase, it is optimal to have value 1 at the index if pre0 < suf1 and 0 otherwise.
Hi, this is my first comp, but had a little trouble understanding q A. The editorial says, the answer is just comparing the first and last letters of the string, but couldn't you split the string up in such away, that substrings 1st and last letters would be different without the first and last letters being the same? For example the string "AABA", though the first and last letters do not match, cant we divide the string like this? — "A", "AB" and "A", such that i can just choose t0 to be "A" and t1 to be "AB", The first and last being different? Maybe I didn't properly understand qA?
U are right but T1=AB and T2=A, so the first and last character match for i=1 and j=2.
As for the solution, it's standard greedy solution. If the first and last characters donot match, we can split the string in 2 parts. First part has all characters except the last one and second part has the last character from s.
Love the rating predictions! Would love to see those on more editorials
Can someone tell me why my solution of D1 is not Working?
https://mirror.codeforces.com/contest/2003/submission/278484674
I doing exactly The same thing as the editorial aren't i?
the first number on every sequence is it's size not an elements in it
problem D1 and D2 are beast... D1+D2 cost me 3 hours to upsolve it. DP on graphs are sure tough one.
In the editorial solution for D2, why are we allowed run a loop from $$$0-\min(m,k)$$$? I think I am missing something obvious, but according to the constraints the maximum value for $$$m$$$ is $$$10^9$$$. $$$k$$$ from the editorial is the $$$mex$$$ so theoretically they can reach the similar range for $$$a_i$$$ which is also $$$10^9$$$. Would it not result it TLE?
nice problem
"Otherwise, for $$$m≥2$$$, it can be inductively proven that ..." (Editorial for C)
I did the proof as an extra exercise, and it was not that easy. Considering that the problem is rated 1200, maybe the solution is easy to guess... but I think the real difficulty (including the proof) would be around 1600.
E1/E2 can be easily solved without DP: 331319759