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
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 :)
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$$$.
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 :)
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?
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.
nice solution.
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 :))
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.
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.
j guess by rotating they meant moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"
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..
I tried constructing solution of B the way the game is played(now realized it wasn't optimal)still where has my solution gone wrong 278140256 .
Also can you guys suggest resources to build logic and concepts to solve upto div2 C,thanks in advance!
My first contest with AC on div2C. ThankyouThankyouThankyouThankyou!
W contest!
It was a great contest, and I'll soon achieve the "pupil" rank. The first three questions were easy, and I figured out the correct logic for the fourth one. I got a TLE on test 3, and I initially thought it was because I used a set, but later realized it was actually due to m being >= 1e9. Overall, it was a fantastic contest, and I'm looking forward to more like this in the future.
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!
solved A and B quite fast but C went right over my head, and the tutorial doesn't help either. I'll keep trying though, ain't no way I'm moving forward without an AC in problem C
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 0, and some suffix will have 1 1, proof is left as an exercise
Just brute the prefix, and find cost to get O(mn). 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.
This my first Div2 contest I solved 3 problems :)
in problem F, why is the probability of getting the optimal solution in one attempt is $$$\frac{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
Definitely not a bug. You're creating vectors of size 2e5 for every test case. It's a common mistake.
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 :)
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.
In D1 first test case
how is f(4) = 4, can someone explain? thanks
Perform zero operations on x
yea thanks got it
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?