I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers.
Hint 1
You can always bruteforce $$$X$$$ and $$$Y$$$, and check every pair of $$$(X, Y)$$$ separately, but there is a tRiCkY solution that involves zero implementation.
Hint 2
Have you ever watched a game of tennis, a game of volleyball, e.t.c?
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
cout << s.back() << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Everything is symmetrical, so you can fix beforehand any exact two conditions you are aimed to satisfy.
Hint 2
You need to not satisfy $$$3$$$rd condition, so it doesnt really make sense to color any elements that not used in satisfying conditions $$$1$$$ and $$$2$$$ in colors $$$b_i = 2, b_i = 3$$$. And to satisfy conditions $$$1$$$ and $$$2$$$ one element is enough.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(n, 1);
vector<vector<int>> inds(N + 1);
for (int i = 0; i < n; i++) {
inds[a[i]].push_back(i);
}
int k = 2;
for (int x = 1; x <= N; x++) {
if ((int) inds[x].size() >= 2) {
b[inds[x][0]] = k;
k++;
if (k > 3) {
break;
}
}
}
if (k <= 3) {
cout << "-1\n";
} else {
for (int i = 0; i < n; i++) {
cout << b[i] << ' ';
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
How to rollback one operation? Is rollback uniquely determined?
Hint 1.1
Of course it is.
Hint 2
After performing operation $$$a_x = x$$$ always becomes a last element of array.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
k = min(k, n);
int last = n - 1;
for (int _ = 0; _ < k; _++) {
if (a[last] > n) {
cout << "No\n";
return;
}
last += n - a[last];
if (last >= n) {
last -= n;
}
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Lower bound for answer: $$$LIS(a)$$$
Hint 2
Upper bound for answer: $$$LIS(a)+1$$$, you can insert $$$b$$$'s in decreasing order anywhere. When you can't achieve $$$LIS(a)$$$?
Hint 3
Solve for $$$m = 1$$$
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m), c(n + m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
sort(rall(b));
merge(all(a), all(b), c.begin(), greater<int>());
for (int i = 0; i < n + m; i++) {
cout << c[i] << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
It makes sense to try to solve case $$$m = 1$$$ first, to get general understanding of the problem, some observations will be usefull in full solution.
Hint 1.1
What size can a multiset $$$X$$$ have?
Hint 1.2
If $$$r - l > n$$$, the answer to the problem is $$$0$$$. Now we are left in the case of $$$r - l \leq n$$$. So we can iterate over all sizes from $$$l$$$ to $$$r$$$, for each of them find the minimum anti-beauty that can have a set of this size, and take the minimum of all this for the answer.
Hint 2
For bigger $$$m$$$ you need to find a fast enough way to count minimal anti-beauty with fixed size, everything else remains the same.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define all(x) x.begin(), (x).end()
using namespace std;
void solve() {
int m;
cin >> m;
vector<int> n(m), l(m), r(m);
vector<vector<int>> a(m);
vector<vector<int>> c(m);
vector<int> sumc(m);
int suml = 0, sumr = 0, sumn = 0;
for (int i = 0; i < m; i++) {
cin >> n[i] >> l[i] >> r[i];
sumn += n[i];
suml += l[i];
sumr += r[i];
a[i].resize(n[i]);
for (int j = 0; j < n[i]; j++) {
cin >> a[i][j];
}
c[i].resize(n[i]);
for (int j = 0; j < n[i]; j++) {
cin >> c[i][j];
sumc[i] += c[i][j];
}
}
if (sumr - suml > sumn) {
cout << "0\n";
return;
}
map<int, int> sumr_a;
map<int, vector<pair<int, int>>> indexes;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n[i]; j++) {
sumr_a[a[i][j]] += r[i];
indexes[a[i][j]].pb({i, j});
}
}
int ans = (int) 2e18;
for (int len = suml; len <= sumr; len++) {
int xsize = 0, must_len = 0;
xsize += sumr - sumr_a[len];
for (auto &[i, pos] : indexes[len]) {
int cnt_not_len = sumc[i] - c[i][pos];
if (cnt_not_len < l[i]) {
xsize += l[i];
must_len += l[i] - cnt_not_len;
} else {
xsize += min(cnt_not_len, r[i]);
}
}
ans = min(ans, must_len + max(0LL, len - xsize));
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hints: Natural Way
Hint 1
Solve the problem if $$$s_i = d_i$$$ for all $$$i$$$.
Hint 1.1
Simple greedy should work.
Hint 2
Solve the problem if $$$s_i = 2 \cdot d_i$$$ for all $$$i$$$.
Hint 3
Solve the problem if $$$d_i$$$ divides $$$s_i$$$ for all $$$i$$$.
Hint 4
You can treat remainder $$$(s_i \mod d_i)$$$ separately, as an individual shelf.
Hints: Believers Way
Hint -1
What is the most obvious greedy you can do?
Hint -2
What is the second most obvious greedy you can do?
Hint -3
What is the third most obvious greedy you can do?
Hint -4
It's probably correct at this point, just proof by AC!
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> s(m), d(m);
for (int i = 0; i < m; i++) {
cin >> s[i];
}
for (int i = 0; i < m; i++) {
cin >> d[i];
}
vector<int> cnt(n + 1);
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
}
set<pair<int, int>> cubes;
for (int x = 1; x <= n; x++) {
if (cnt[x] == 0) continue;
cubes.insert({cnt[x], x});
}
vector<vector<int>> ans(m);
for (int i = 0; i < m; i++) {
ans[i].assign(s[i], 0);
for (int j = 0; j < s[i]; j++) {
if (j >= d[i]) {
if (cnt[ans[i][j - d[i]]] > 0) {
cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
}
}
if (cubes.empty()) {
cout << "-1\n";
return;
}
ans[i][j] = (*cubes.rbegin()).second;
cubes.erase(*cubes.rbegin());
cnt[ans[i][j]]--;
}
for (int j = s[i]; j < s[i] + d[i]; j++) {
if (cnt[ans[i][j - d[i]]] > 0) {
cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < s[i]; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Cacti is a trap, don't think about it for now, it will help later.
Hint 2
Well, you need to make some observations. Start with observations about determining edges weights, it seems reasonable because edge always have exactly $$$2$$$ adjacent vertices.
Hint 3
Edge is good <=> Exactly one of the adjacent vertexes have a same weight as an edge.
Hint 4
Direct edges, such that every edge goes from vertex with same weight as edge to another vertex. In this reality try to find easier equivalent condition for ``vertice is good``.
Hint 5
Vertex is good <=> InDegree of vertex is an odd integer.
Hint 6
Now you just have two separate problems: 1) Direct all edges, such that InDegree of each vertex is odd; 2) Color all vertexes in 3 colors such that any 2 adjacent vertexes have different color. Time to remember about cacti.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
using namespace std;
const int M = 998244353;
const int N = 500500;
vector<pair<int, int>> g[N];
set<int> bridgesV[N];
bitset<N> used;
int h[N], d[N];
ll bridges = 0;
ll solo = 0;
int binpow(ll a, ll x) {
ll ans = 1;
while (x) {
if (x % 2) {
ans *= a;
ans %= M;
}
a *= a;
a %= M;
x /= 2;
}
return (int) ans;
}
void dfs(int v, int p = -1) {
if (p != -1) {
d[v] = h[p] + 1;
h[v] = h[p] + 1;
}
used[v] = true;
for (auto &[u, w] : g[v]) {
if (u == p) continue;
if (!used[u]) {
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] < d[u]) {
bridgesV[v].insert(u);
bridgesV[u].insert(v);
bridges += w + 1;
solo += w;
}
} else {
d[v] = min(d[v], h[u]);
}
}
}
int calc_dp(ll n) {
n %= (M - 1);
if (n == 1) return 3;
if (n == 2) return 0;
int val = binpow(2, n);
if (n % 2 == 1) {
val += M - 2;
} else {
val += 2;
}
val %= M;
return val;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
a--;
b--;
g[a].pb({b, w});
g[b].pb({a, w});
}
if (n % 2 != m % 2) {
cout << "0\n";
return 0;
}
dfs(0);
used.reset();
ll ans = 1;
for (int v = 0; v < n; v++) {
if (!used[v]) {
ll cs = 0;
vector<int> q = {v};
used[v] = true;
while (!q.empty()) {
int u = q.back();
q.pop_back();
for (auto &[uu, w] : g[u]) {
if (bridgesV[u].find(uu) != bridgesV[u].end()) continue;
cs += w + 1;
if (!used[uu]) {
used[uu] = true;
q.pb(uu);
}
}
}
cs /= 2;
cs = max(cs, 1LL);
ans *= calc_dp(cs);
ans %= M;
}
}
ans *= binpow(3, solo);
ans %= M;
int w = (2 * binpow(3, M - 2)) % M;
ans *= binpow(w, bridges);
ans %= M;
int cycles = (m + 1) - n;
ans *= binpow(2, cycles);
ans %= M;
cout << ans << '\n';
}
Nice contest and fast editorial, A was tricky
Why is this getting downvotes, someone please explain.
Because questions were not that difficult. Like you would be able to solve d just by simple sorting
there actually is a builtin function in c++ to solve that problem, it's called merge. 231958618
Ohh... Thanks, I didn't know that
I took this comment as a hint, and implemented the merge logic manually... And I got AC!
Really nice div 2 contest and fast editorial. Thanks a lot!!!
C and D div 2 was nice
too easy at this place.
Well,may be it's different for different people.As a div1 contestant,div1A and div1B (div2C and div2D) were really not easy for me that I spent nearly 45 minutes to solve them,but what shocked me was that div1C and div1D were very easy to come up with for me...
Could anyone help me figure out why my code can pass 1B? I can't prove my solution is right qwq. my 1B submission
Div1D way too EZ
Problem A is true observation, I even didn't know how I got AC by that code lmao
I'd like to know how sevlll777 created the sample input. I think it's more difficult than solving the problem.
It seems that just make random strings with $$$\text{the number of }\mathtt{A} \ne \text{the number of }\mathtt{B}$$$ is ok. In this case you can choose $$$X=\max(cnt_A, cnt_B),Y=1$$$.
validator is like: bruteforce all $$$X$$$ and $$$Y$$$
The performances of participants who solved $$$3$$$ tasks range from CM to IGM (in Div. 1). I believe that the coordination is really incredible :)
Man, the first problem is the same problem that errichto said in the interview with the Joma Tech (available on youtube) right??
div1 B>C>A>D
What a fast editorial)
A was too bad, B and C were nice.
A solution doesn't take into account inputs of type "AB" or "ABAB" right? Which should be reported as "?" since there is no clear winner. Except if we consider the string fed to us is always correct?
From the statement (in bold):
"It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of $$$X$$$ and $$$Y$$$."
Intuitive understanding of the correctness of the full greedy algorithm for D :
When filling a shelf, we select the $$$d$$$ most present colors and take one of each, and repeat until the shelf is full (taking the $$$d$$$ colors in the right order as to keep the condition).
It breaks only if there are less than $$$d$$$ different colors left. Hence, if we have to choose between two colors, we want to use the most present one, as to avoid being left with only one of them in the future. And if we have to choose between all of them we want the most present one.
This gives a simple solution that can be implemented with a priority queue (see my submission https://codeforces.net/contest/1893/submission/231786809)
And congratulations to the author for the amazing problems ! I really enjoyed the round !
Ty @Errichto for explaining Problem A 4 years ago
https://www.youtube.com/watch?v=F4rykKLcduI
In Div2-A If the input was "AB" should not the output be '?' since there is no winner?
The string "AB" is not a valid game scenario and since the input is guaranteed to be a valid one...
wtf where's the proof of greedy in D? like 80+% of AC's used that greedy
Why does the editorial need to post an editorial for an alternative solution? If there are so many people who solved it by greedy, maybe at least one of them should know enough to explain it here
You can read it in my comment here: https://codeforces.net/blog/entry/122075#comment-1083884
Didn't solve D1C because 1e17+1 is not (ll)1e17+1...... and in test case 3 where sum(r[i])==1e17, my solution took it as sum(r[i])>=(ll)1e17+1
Div2 ABCD are so trivial in implementation that I just hesitated to submit them, was sure that missed something in problem description, and overcomplicated D to the point where it's finally got wrong. I'd prefer more emphasis on implementation than deciphering descriptions.
Can anyone please help me to find out what's wrong in this code? (https://codeforces.net/contest/1894/submission/231802454) I got AC just by changing the condition in while loop. AC submission: (https://codeforces.net/contest/1894/submission/231828401) But what's the difference between this two?
Submission
Changed cnt <= mini to cnt < mini
Thanks a lot. Now I have got it. I actually am checking for k+1 times where the last checking is making it wrong.
For Div2 A :
testcase : 4 , aabb
how can answer be B?
For what x and y is answer going to be B
This is an invalid test case.
This test case is not valid because no such pair $$$(X,Y)$$$ that leads to the results.
I noticed the solution for problem A quickly. And waited 15 minutes rereading the statement then submitted a more complicated solution. That was a bad statement. Otherwise the other problems were nice.
Div-2 C was good ... i was able to make major part of the logic but wasn't confident enough to implement
(Div2-A) That makes sense. But there won't be any "?" output (either A or B). Also X,Y are considered redundant. All in all, it was weirdo :/
To add some more weirdness to it, a problem statement as short as 1 page with 1 line of code solution caused 2 announcements during tournament.
In question B , there is also another way to insert the elements of b in the array a . In array a , we can look for the starting point of the lis of array a such that the point is to the left as possible if there are more starting indices of same length lis . Let the element at the starting position is elem.Then we can insert all the elements greater than the elem to the start of the array in decreasing fashion and all elements less or equal to the elem after elem in decreasing fashion . The problem is how to find this elem(starting position with above requirements in given time constraints) . Can we find this out (basically we have to find the leftmost index of lis of array)?
Great idea, but it needs to be fixed. Consider this case: A:2 2 3 4 B:1 if you insert 1 after the first 2，the result will not be best. About your question, simple dp runs in O(n^2) and there exists a binary search trick to make it O(nlogn) .
Yeah i see , the idea requires handling rhis case also . In this case we can insert after the 2nd 2 .The n2 approach will give me the starting point of the lis but it is not within time constraint.The nlogn thing afaik it gives me the length of lis bit not the elements. Can we modify it to find if not all but the 1st element
Consider this case,A[7 8 9 4 5 6]， B[3]，the leftmost element is 7，but you need to insert 3 after 4， not after 7. Also, the nlogn solution gives you same result in each step as n^2 solution, not only the final lis length. You can find this point by comparing these two solutions in each step.
Even though people dislike A problem thanks for the fast and high quality tutorial, with hints and the possibility to rate each problem.
I'm writing this text because I was deeply affected by some comments about the contest and some personal messages received on cf. And I feel an urgent need to explain how the contest was created, why these particular problems were chosen, what was the idea behind the problemset. And to show that I care about each problem, and about the contest as a whole.
I will focus on the Div1 part of the round, because it was Div1 that was the main goal, it was Div1 that had most of the effort and thought put into it.
The main things I wanted to show to people in this contest were the author's solutions to problems B, D, E and their proofs (for B, D), and the solution process (for E). (I'll talk about A and C later, but, spoiler, these problems were not chosen "from what was available", and there is a strict motivation behind both of them, but more on that later). Seriously, I recommend everyone to read the editorial of problems B, D, E and understand the authors' solutions and their proofs. I find them very beautiful, and these are the ideas I wanted to convey in this contest for the general audience, it was the basis for the creation of the contest. More details about these tasks:
B: I'm still amazed by the fact that you can insert any numbers into any array in such a way that the LIS doesn't change, in my opinion it's just marvelous. The statement itself sounds like this is a well known problem, but surprisingly it is not. The first version of the problem had $$$m = 1$$$, that is, you had to insert one number, and in this version the problem does not reach its full potential, not all the beauty is seen in such a formulation. And the surprising thing is that such a simple and familiar algorithm leads to the solution: merge two arrays with two pointers. And I find the proof of this very beautiful. The author's solution is unironically: input + 2 lines + output. Seriously, isn't that fascinating?
D: I really like the author's solution and his proof, that such a simple and trivial necessary condition suddenly turns out to be sufficient, and it's not difficult to prove, it's a very simple construction. And now the problem, which at first sight is impossible to combine for $$$m$$$ different arrays suddenly splits and becomes so simple, familiar and understandable~-- just split into arrays of different numbers for given lengths, and further solution is just a matter of technique. Seriously, isn't that fascinating?
E: Kind of the opposite of problem D. I really like that the solution consists of a few tiny ideas and observations. And at some point, after some number of observations, it is suddenly revealed that the problem breaks up into 2 independent and standard-sounding problems. What I like about this problem is that the statement has some stupid formulation and some incomprehensible constraints taken from the sky, but in the end the solution turns out to be very natural. And in the flow of solving the problem, everything falls into place, strange constraints are revealed, and their meaning becomes clear. And the moment when the problem breaks up into 2 independent, familiar and understandable tasks is the peak, the catharsis of this problem. Again, I really like the resulting structure of the solution, starting from some random conditions we step by step approach closer and closer to something understandable, it does not happen at once, first one observation, then the second, third, etc., and at some point the problem falls under the rush, and disintegrates into two simple and so familiar combinatorial problems. Seriously, isn't that fascinating?
As it happens, one story happened to all B and D and E: the moment they transformed from ideas in my head to actual competetive programming problems, art and magic chastically collapsed, due to alternative solutions. About alternative solutions:
B: there are VERY many alternative solutions to this problem. VERY. There is, also quite beautiful, an alternative solution based on a deep understanding of the algorithm for finding the LIS for O(n log n) using DP with binary search. But there are many others. And this is something I can't control. I can't force all participants to come up with a 2-line solution, and even if I could, it would be bad, "you can't force someone to enjoy the art", you know. That's why I, as an author, put up with a lot of alternative solutions, in order to bring my idea of an author's solution to the general audience.
D: there is one alternative solution here. And yes, it is horrible and disgusting. Stupid stupid stupid greed. I was not originally aware of this solution. This solution was found by the testers. In fact, in this problem I had many ideas and options how to change the statement to break the greed. For example, a version where you don't have to recover the answer, but there are q queries "add a cube of color X, s[i] += 1". But that makes the task ugly. It spoils the picture by spilling some black paint on it. The purest diamond would have a dark spot. I don't like that. Absolutely not. When choosing between two evils, I'll always choose the alternative solution. But I won't spoil the task, I won't spill paint on my beautiful solution. And that's where I'm probably wrong about making a contest for a wide audience. Maybe I should have compromised, and "messed up" the author's solution to cut the alternative solution. Perhaps.
E: there is also one alternative solution here. Nightmare dp on cacti with 100500 parameters and recalculation with matrices. This sort of thing is usually dealt with by choosing constraints, and yes, this is why problem E is the only one with n = 5e5. But it was all useless, since it was not possible to cut off this solution completely. I tried to spoil the life of those who wrote this solution as much as possible, but so that those who wrote the author's solution would get the AC as freely as possible. Here also the duration of the contest set at 120 minutes played a role. In this problem I also considered the option of adding queries, a-la "+X vertices appeared on edge E". Perhaps I was wrong, and I should have compromised by adding ugly queries. Perhaps.
Now I will tell you about tasks A and C. Formally, these tasks are "fillers", but I still put my soul into them, and now I will explain it.
A: The first task of the contest. The apitizer task. A task that should not be too difficult, but not too trivial. It should contain a minimal idea, which is nice to find by yourself. A task that should entice you into the contest, and set you up for a further two hours of brainstorming. That's my philosophy for the perfect div1A. And I'm confident that this task A almost fully satisfies that philosophy. But there is a small problem. The main idea of the task is rather "hidden in the statement", lying out in the open, rather than requiring some great idea. The problem requires observation in the truest sense of the word. And yes, this problem was not perfect, but I still consider it more than worthy for a contest opener.
C: The task that got the most hate after the contest. This task contains some cute and funny ideas, which lead to the fact that a rather dumb bruteforce turns out to be very fast. I find the idea part of the task cute, but certainly not at Div1C level, more like Div1A level. The big challenge here is really a neat implementation of the solution, fast and bug-free. And yes, that's why the task made it to the contest. Its purpose was to mix the full-of-idea tasks B and D with some implementation, and to bring variety into the contest. That's why from my point of view it was a perfect-fit, adding to the contest a test of another part of a competetive programmer's skill: fast and accurate implementation. That was the idea. And it failed miserably, and it seems, because of alternative solutions for B and D. Or maybe not, and I just overestimated the interest of the idea part of this problem, and in fact it is Div2A level. I don't know. I don't know...
I doubt anyone will actually read this text. I would never post something like this publicly, but I really want to show that I really cared about the contest at worst. And at best, to explain my philosophy of problemsetting. Sorry if the text turned out to be messy and crumpled. And thank you.
First of all, thanks for preparing the contest! I liked thinking about B and D. Still, and it seems like you agree, the contest does have it's flaws. I'd like to share a couple of thoughts I had during testing and after reading you comment, maybe someone will find them useful)
A: What I didn't like about this problem is how contrived the statement felt. Too many things had to be satisfied to make it work. Maybe most of the competitors felt the same way.
C: Again, the statement feels pretty contrived. The solution is almost hidden behind the statement, so after parsing it, only implementation is left. I felt mostly ok with that, but it seems like quite a lot of people disagree. Personally, I wouldn't be ok with putting this in my contest without trying to come up with something better, but well, that's just my opinion).
B and D (and maybe E?): I think that even if a problem's intended solution is very interesting, for a contest, you have to consider what participants are more likely to stumble upon. If with a high enough probability that turns out to be some undesirable solutions (from your point of view), and you can't cut them off in a pleasant way, maybe you should reconsider using the problem in the contest, at least in it's current form.
That being said, trying to estimate what participants will come up with is sometimes very hard) Though in most cases, I feel like the miscalculations are due to either the author and coordinator being not up to date with the community as a whole or the tester pool being not representative of it (sometimes both). Fortunately, it's possible to reduce mistakes from these sources, though I feel like not enough effort is put into doing that (I've been guilty of this a couple of times myself, but hopefully, I've been learning from my mistakes...).
Side note: problems are sometimes surprisingly resilient to giving up their core idea even after pretty significant changes, though I feel like that mostly happens when you have a simple statement)
Thanks for the comment! Just in case, I want to ensure you, that I didn't ignore your feedback during testing, btw, TLs were increased because of your suggestion. You were not the only tester who not liked A and C, but there also were testers who liked both of them, and afterall I decided to trust my inner feeling and leave both problems in their places.
Obviously, spoiling beautiful problems for cut some muddy solutions is a bad idea. I think everyone could learn something from this competition. For example, that sometimes you can believe in some kind of unprovable greedy (D). For me, an important lesson was that before you rush to write code, you should think a little more, and not shove two different subtasks into one dp (E).
Anyway, thanks for the contest! People are designed in such a way that they would rather blame the author than try to find their mistakes and learn SomethingNew) I will be waiting for new contests from you!
Thanks for the comment!
I did find problem B fun to think about. The observation that LIS stays constant felt a bit obvious when you're given this much freedom of where to insert the new element, but still finding the right strategy is very much not obvious.
Personally, D is also fine as is, because the greedy solution to D is magical to me, it's surprising that such a simple solution works for what is a problem with a lot of moving parts. I don't hate the greedy solution as much as most people, but I do hate whoever submitted it without proving it. Shame on you.
But in general I'm not opposed to adding more details to a problem to "force" an observation if it's a beautiful one, that is done quite often in e.g. problems where you're asked to count number of some configuration (to force you to find observations that make it easier to count).
Now, the part where I think you're mistaken, is that C would be bad regardless of the rest of the round. The statement is very hard to understand for what seems to be no good reason -- why introduce 998244353 variables when you could have written something like "You're given n arrays $$$a_1, a_2, ..., a_n$$$ and you must select at least $$$l_i$$$ and at most $$$r_i$$$ elements from array $$$a_i$$$"? And then, after you spend a lot of time to understand the statement, you spend no time solving it because, as you admitted yourself, there is only one extremely simple idea and it's at most a div1A in terms of difficulty and should never be 1C.
This could have been a fun round with some adjustments, remove C because it's fun for no one and add something else to actually bridge the difficulty gap in the middle. Still B and D had some cool ideas and I have faith that you can make a better received round in the future. Just maybe ask for a better coordinator.
Thanks for the comment!
Thanks for the well problems and the preparation of the contest.
Actually I was annoyed by the implementation of 1B and 1C (I write very sophisticated code for 1B, around 160 lines) and had no time to read 1D. 1B is my fault, but I think it better to remove 1C.
However when I read the statement today I immediately came up with a same solution with the author(divide a shelf to several $$$len=k$$$ parts and a $$$s\bmod k$$$ part) and when I read the ultra greedy solution, I found both beautiful. But whichever solution one chooses, the difficulty is only 1B/1C while not 1D.
So a good solution is removing 1C, placing 1D at 1C, and adding a more 1D and 1F.
Thanks for the comment! By the way, 1D was indeed in 1C spot at the start of the testing. But many testers had difficulties with this problem, thats why it ended up in 1D spot.
this contest too bad !!
In Div 2-A 6th example test case —
13 AAAABABBABBAB
here if x=1,y=13 then A is winning more, but not in the last slot, and if x=13,y=1 then A is winning as A won more matches in the slot. then how B is the winner here? can anyone explain, please!!
x=3,y=2 is a legal explanation.
And actually,the problem says that if one wins y sets,the game will be ended at once. So when the last play ends,the game will be ended.So the winner of the whole play must be the winner of the last play.
There's one thing that one set contains at least x plays,but not only x plays.Maybe you have some misunderstanding of it.
For example,if we set x=3,y=2,the first set is AAA,it stops as A wins 3 times. The second set is ABABB,obviously,it contains 5 plays but not x=3 plays,that's because it stops when B wins 3 times while A wins 2 times at the same time. The third set is ABBAB,the same as the second set.
So B wins y=2 sets,then B wins.
I am curious how the author came up with Div2A, and how you (noone including the coordinator) couldn't find a duplicate problem. It took me less than 5 minutes to find a duplicate from IPSC 2005.
Sadly I failed to debug Div2 E
Just look at this code: https://codeforces.net/contest/1894/submission/231756011
It has Undefined Behavior (Heap-Buffer-Overflow on $$$used$$$) already in example, but passed all tests.
Hint 3 in the solution of Div1 E really confused me. I think it should be InDegree instead of OutDegree.
Yes, you are right, it's fixed now.
Anyone can explain why the time cost of tutorial to div2E can be $$$O(\Sigma n_i)$$$, from the code, i think it is $$$O(\Sigma n_i)*O(\Sigma r_i-\Sigma l_i)$$$,at most $$$10^{10}$$$
No because sum of the indexes length is at most n
Damn I hate that I missed the round. Heard that Div1-C,D were really fun.
Nice contest sevlll777, I am a little unclear on why exactly a cycle is created after n reversals [Anonymous Informant], could you please explain in an intuitive way?
Okay I got it after a few minutes of thinking. Here's what I think in case anyone needs it. There are at most n unique shifted arrays for any possible initial array. The next array that we get after a reversal is one of those n unique shifted arrays, and for one array, what comes after a reversal is fixed. Hence the moment one of the array repeats, the whole chain has to repeat. After n reversals, one of the array HAS to repeat (as mentioned before, there are only n unique such arrays possible, for it to not repeat there has to be more than n unique, shifted arrays for an initial array),due to which, the whole chain will repeat too. In many cases, the chain of reversals may start repeating before n.
After n reversals we cannot disprove the anonymous informant anymore.
You can adapt calculation method for LIS to solve D:
Calculation method for LIS in $$$\mathcal{O}(n\log n)$$$: https://cp-algorithms.com/sequences/longest_increasing_subsequence.html
In the method $$$d$$$ is calculated by starting with empty array, incrementally adding the next element of $$$a$$$ and updating $$$d$$$ after each addition. In this problem we can decide if we want to add either the next element of $$$a$$$ or some element of $$$b$$$.
If we add an element that exists inside $$$d$$$, $$$d$$$ does not update (think about it) and thus this element has no effect on LIS. Therefore if at the current step an element of $$$b$$$ appears in $$$d$$$, you should add that element from $$$b$$$.
Otherwise, you are able to choose whether to add next element from $$$a$$$ or some element from $$$b$$$. Due to behavior of LIS its best to add the large elements early and save small elements for later. Thus you should add the largest between: the next element of $$$a$$$, and the largest element of $$$b$$$.
first one still doesn't making sense to me..why don't we take x = max(aCount , bCount) and y = always 1 then we can conclude that A is winner if aCount > bCount , otherwise B and else '?'.. like what is stopping me to do this??
It's a nice realization in C, Iterating the sets that contain $$$s$$$ for all $$$s$$$ is in total simply $$$\sum n$$$ (its like a rearrangement of the matrix given by the multisets) though at first it seems much slower