We hope you enjoyed the problems!
Rate the contest!
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
int n,a[109],k;
long long C;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d %lld %d",&n,&C,&k);
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
}
sort(a + 1,a + n + 1);
for(int i = 1; i <= n; i ++){
if(a[i] > C)
break;
int o = min(1ll * k,C - a[i]);
k -= o;
C += a[i] + o;
}
printf("%lld\n",C);
}
}
Rate the problem!
Solution
Tutorial is loading...
Code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)])
Code (C++)
#include<bits/stdc++.h>
using namespace std;
int n,a[5009],bcnt,f1[5009],f2[5009];
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
}
for(int i = n; i >= 1; i --){
f1[i] = f2[i] = 0;
for(int j = i + 1; j <= n; j ++)
f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]);
f1[i] = max(f1[i],f2[i]);
}
for(int i = 1; i < n; i ++)
printf("%d ",f1[i]);
printf("%d\n",f1[n]);
}
}
Rate the problem!
Idea: __baozii__
Solution: __baozii__
Editorial: __baozii__
Solution
Tutorial is loading...
Code (Python)
for _ in range(int(input())):
n = int(input())
ans = -1
for i in range(1, n):
print("?", 2 * i + 1, 2 * i + 2, flush=True)
if int(input()):
ans = 2 * i + 1
break
else:
print("?", 1, 3, flush=True)
if int(input()):
ans = 1
else:
print("?", 1, 4, flush=True)
if int(input()):
ans = 1
else:
ans = 2
print("!", ans, flush=True)
Rate the problem!
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
int t,r,g,b,rb,gb,rg;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d %d %d",&r,&g,&b);
while(((r > 0) + (g > 0) + (b > 0)) >> 1){
if(r <= g && r <= b)
gb ++,g --,b --;
else if(g <= r && g <= b)
rb ++,r --,b --;
else if(b <= r && b <= g)
rg ++,r --,g --;
}
if(g > 0){
putchar('G');
while(rg > 0)
putchar('R'),putchar('G'),rg --;
bool flg = false;
while(gb > 0)
putchar('B'),putchar('G'),gb --,flg = true;
if(flg){
while(rb > 0)
putchar('B'),putchar('R'),rb --;
}
else{
while(rb > 0)
putchar('R'),putchar('B'),rb --;
}
}
else if(r > 0){
putchar('R');
while(rg > 0)
putchar('G'),putchar('R'),rg --;
bool flg = false;
while(rb > 0)
putchar('B'),putchar('R'),rb --,flg = true;
if(flg){
while(gb > 0)
putchar('B'),putchar('G'),gb --;
}
else{
while(gb > 0)
putchar('G'),putchar('B'),gb --;
}
}
else{
if(b > 0)
putchar('B');
while(gb > 0)
putchar('G'),putchar('B'),gb --;
bool flg = false;
while(rb > 0)
putchar('R'),putchar('B'),rb --,flg = true;
if(flg){
while(rg > 0)
putchar('R'),putchar('G'),rg --;
}
else{
while(rg > 0)
putchar('G'),putchar('R'),rg --;
}
}
puts("");
}
}
Rate the problem!
2209E - A Trivial String Problem
Idea: __baozii__
Solution: __baozii__
Editorial: __baozii__
Solution
Tutorial is loading...
Code (Python)
import sys
input = lambda: sys.stdin.readline().strip()
def work(s):
n = len(s)
p = [0] * n
b = [0] * n
for i in range(1, n):
j = p[i - 1]
while j and s[i] != s[j]:
j = p[j - 1]
if s[i] == s[j]:
j += 1
p[i] = j
if j == 0:
b[i] = 0
elif p[j - 1] == 0:
b[i] = j
else:
b[i] = b[j - 1]
ans = 0
for i in range(n):
p[i] = 0
p[i] = p[i - b[i]] + 1
ans += p[i]
return ans
for _ in range(int(input())):
n, q = map(int, input().split())
s = input()
for _ in range(q):
l, r = map(int, input().split())
print(work(s[l - 1:r]))
Rate the problem!
2209F - Dynamic Values And Maximum Sum
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
const int N = 300009;
int n,k,t,a[N],tt[N];
long long b[N],ans[N],sum,mxa;
struct FLONG{
long long val;
int nd;
FLONG(long long v = 0,int d = 0):
val(v),nd(d)
{}
bool operator<(const FLONG &b)const{
return val > b.val || (val == b.val && nd < b.nd);
}
};
set<FLONG>s;
set<FLONG> :: iterator o;
struct pir{
int to,len;
pir(int t = 0,int l = 0):
to(t),len(l)
{}
bool operator<(const pir &b)const{
return len > b.len || (len == b.len && to < b.to);
}
}mn[N],se[N],lf[N];
vector<int>e[N];
void srh(int v,int fa){
mn[v] = pir(v,0);
se[v] = pir(0,~0x3f3f3f3f);
lf[v] = pir(0,~0x3f3f3f3f);
for(unsigned i = 0; i < e[v].size(); i ++){
if(e[v][i] != fa){
srh(e[v][i],v);
pir th = mn[e[v][i]];
th.len ++;
if(th < se[v])
swap(th,se[v]);
if(se[v] < mn[v])
swap(se[v],mn[v]);
}
}
}
void gt1(){
sum = ans[1] = 0;
ans[1] += a[1];
for(int i = 2; i <= n; i ++){
b[mn[i].to] += a[i];
tt[i] = mn[i].to;
//printf("%d %d\n",i,tt[i]);
}
s.clear();
for(int i = 2; i <= n; i ++){
s.insert(FLONG(b[i],i));
}
o = s.begin();
ans[1] += o -> val;
sum += o -> val;
for(int i = 1; i < k - 1; i ++){
o ++;
ans[1] += o -> val;
sum += o -> val;
}
s.insert(FLONG(-1ll,0));
s.insert(FLONG(-2ll,0));
}
void era(int x){
FLONG u = FLONG(b[x],x);
if(!(*o < u)){
o ++;
sum += o -> val;
sum -= b[x];
}
s.erase(u);
//printf("%d %lld\n",x,sum);
}
void ins(int x){
FLONG u = FLONG(b[x],x);
s.insert(u);
if(!(*o < u)){
sum -= o -> val;
sum += b[x];
o --;
}
//printf("%d %lld\n",x,sum);
}
void stp(int x){
era(tt[x]);
b[tt[x]] -= a[x];
ins(tt[x]);
tt[x] = 0;
}
void sett(int x,int ttp){
tt[x] = ttp;
era(tt[x]);
b[tt[x]] += a[x];
ins(tt[x]);
}
void srho(int v,int fa){
//printf(" %d %d\n",v,fa);
if(fa != 0){
stp(v);
era(v);
ins(fa);
sett(fa,lf[fa].to);
ans[v] = sum + a[v];
}
for(unsigned i = 0; i < e[v].size(); i ++){
if(e[v][i] != fa){
pir u = lf[fa];
u.len ++;
if(mn[v].to == mn[e[v][i]].to)
lf[v] = min(u,se[v]);
else
lf[v] = min(u,mn[v]);
srho(e[v][i],v);
}
}
if(fa != 0){
ins(v);
sett(v,mn[v].to);
stp(fa);
era(fa);
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&k);
mxa = 0;
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
mxa = max(mxa,1ll * a[i]);
e[i].clear();
b[i] = 0;
}
for(int i = 1; i < n; i ++){
int u,v;
scanf("%d %d",&u,&v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
if(k == 1){
printf("%lld\n",mxa);
continue;
}
lf[0].len = ~0x3f3f3f3f;
srh(1,0);
gt1();
srho(1,0);
for(int i = 1; i <= n; i ++){
mxa = max(mxa,ans[i]);
//printf("%lld\n",ans[i]);
}
printf("%lld\n",mxa);
}
}
Auto comment: topic has been updated by __baozii__ (previous revision, new revision, compare).
Fast Editorial! Thx
I made video editorial for problem E. A Trivial String Problem.
Thanks for the nice problemset and fastest editorial!!
I wish n q log n for E was allowed to pass lol I was going to do binary search with rolling hashes to find all the prefixes and then dp for each query
(I had IMO a simpler idea, dp[i] is the best way you can split 1...i (where 1 is relative to the start of each query), dp[i] can extend to dp[j] if substring
i+1...jis a prefix; precalculate these (this is where I only thought of the n q log n rolling hash approach but one of my friends did it with Z function in n q) and then use sliding window to keep track of the best one)orz
orz
orz
you are the orz one for finding it lmao
A solution passes for n*q with string hashing without any Binary Search, KMP, or Z-Algo.
Implementation: 367689627
It seems like that it is not O(nq) but O(n^2q) when the string constructed wisely.(tho I don't know if such a string existed.)
D is hard but an excellent problem!
i thought i could do it... was on it for 40 mins.... got the idea in last 10 mins but lost confidence then ..
Simple logic,but long code(if&else) lol.
nice problemset!
A-C S P E E D F O R C E S
true dude
1398 — 1399 I feel your pain
E didn't seem that interesting or fun to me. You just had to know one algorithm and you also had to hope that your $$$O(nq)$$$ solution would just pass even though $$$nq \leq 10^8$$$ which is relatively high. There was almost no hard observation to do which I don't think is appropriate for E. Other problems were fine.
yeah I did a different n*q algorithm with a rolling hash and it doesn't pass in Python :(. I wish the bounds were 10**7 instead
Sadly i think you have to learn C++ to solve some of these problems.
Yeah, I love codeforces so far but that's definitely my main complaint with it :(
I'm more used to ICPC / Kattis style problems where they're lenient enough with time constraints for Python to almost always work, but for a couple contests in a row now here I've been blocked by Python. I can write in C++, I just prefer Python because I think it's far quicker to write, but perhaps I will have to set up a C++ template and always start with C++ for D and up from now on :/
Checkout hints for all the problems on CF Step
Why it's div1 in the title
now there is a chance that they're author of round 1088 lol.
Appreciate the fast editorial, but I'm struggling the solution even after reading it :(
Hi, it feels like I did the same thing as said in editorial for C but it does not pass cases can someone explain to me why?
https://mirror.codeforces.com/contest/2209/submission/367684792
Nevermind I figured out
there were weak test cases for problem 3. Lot of prolems who asked n queries in one loop and one in the last passed . example of one such case is 1002. it is not there where most of the test cases would have failed
Do you mean like randomized algorithms? I thought the interaction was adaptive so if you tried to guess (e.g. for a fixed randomly generated array each query has a 1/4 chance of succeeding) the interactor could adversarially WA you
I don't understand the solution for D, it feels like it is not written in English. Can someone write it more clearly please
I had a different solution, this is mine:
Assume for convenience that R >= G >= B
If R > G + B + 1, then you're not going to be able to use all the Rs, since the most Rs you can pack is RxRxRxRxRxR which requires at least R-1 B/G chars.
Otherwise, let's construct a sequence that uses every character.
First write two sections
GGGGGGGG(possibly empty, since G >= B) andGBGBGBGB.Since R >= G, we can definitely pad the first section
GRGRGRGRGRGRGRGR, and then we'll have some number ofRs left that we need to spend on theGBGBGBGBGBsection.Assume we have an even number of Rs left, if it's odd then we'll put one at the beginning and we're fine.
Then turn
GB GB GB GB GBintoBRGR BRGR GB GB GB; each pair ofRs that you have converts aGBinto aBRGR. We flip it so that the transitionBRGRGBdoesn't break the 2-gap rule.What was the intuition behind this solution? Like how did you approach the problem and end up with this construction? Did you draw small cases?
The first obvious thing was the triangle inequality thing with the
RBRBRBRBRGRGR. And then that gave me the idea to see if it's always possible to use everything in the general case. (At this point I was already suspicious thinking something like alternating letters might let me use all the letters.) However with the general case you might not have enoughRs, so the beginning of the string is going to look likeRxRxRxRxRend of the string is going to have to look likeBGBGBG. So that gave me the idea of splitting the G/B characters into the "solid" sectionBBBBBBand the alternating sectionBGBGBGBG.Then finally the specific construction with the even/odd parity and pairing and stuff comes from playing around with it a bit and trying to formalize something that always works. [This part is not as hard as it looks, it just comes from
BGBGBGBGI'm going to have to pack withRs for the first half so I first try the standardBRGRBRGR BGBGBGbut oh no that violates the every-3 condition, but I can flip the order to keep it straight, now let me just be careful with even/odd parity and write it a little more formally.]In general with constructions I think it can be helpful to prove an upper bound and then see if you can always construct a solution to hit it.
Both your solution and explanation of how you came up with it is awesome :)
It is quite clear if you read the code. Basically you should be thinking in segments of 2, not in segments of 3 as the problem might imply. Cool solution but quite hard to find IMO.
Here's my implementation which is basically same as edi
I was disappointed with B since it allowed
n^2, but C made up for everything.C==CoolI came up with a very clean implementation for D
I believe that problem F is just a simpler version of JOISC 2019 Designated Cities.
I copied and pasted my AC code and made changes in about 20 minutes (I made some bugs in the segtree during the copy-paste), but I was done 4 minutes after the contest ended :((
The Z function can also solve problem E: 367669514
i also tried to solve E with Z function but i couldn't optimize the dp. my solution was in O(qnlogn). could u please share how u optimized the dp?
I think that if you find a $$$O(qnlogn)$$$ solution, you are doing range chmax and dp, which looks like this: 367663534
Then I noticed that the answer only went up by 1 each time, so I changed chmax to amortized.
Or just replace priority queue with stack: 367777401
Oh my,I haven't seen the task before.
Auto comment: topic has been updated by OtterZ (previous revision, new revision, compare).
In problem C, did u forget the test
cuz it has so many early ACs T_T
Yes, I think the adaptive interactor wasn't the best choice, and they probably should have covered the simple case themselves.
For example, my solution like 367690402 passes when it really should not. Realized it was wrong mid-explanation while streaming T-T.
Agreed, my wrong solution also passed
Solved till D much fast but problem E sucked :)
For those who have even the slightest idea about AC automaton or KMP, E should be a absolutely trivial problem. I think the other problems are nice but this one placed at the rather crucial position of problem E really isn't a great one, TBH. It wouldn't be quite possible for those without knowledge of this algorithm to solve it and those who know this may be delayed by the earlier problems C-D and missed this E, such that the problem kinda only tests if one knows about KMP......
However, great contest overall~ thanks for such a thrilling game.
E also has a simple z function solution, but yeah its just a knowledge check
finally the cheating season has begun I guess : (
i came to the same solution to C as the editorial an hour before the contest ended, but gave up 30 minutes later because i wasn't sure whether i could skip (1, 2) or not. what a pity!
I really suck at construction problems, so I would love to read about more constructions for D that work and how did you come up with them
I think this editorial got downvoted because many people can't imple D cleanly.
Thought of some weird idea for D during the contest, like "Pick the letter that currently has the highest available amount that does not violate the conditions. If more than one letter is possible to choose, pick the one that is the longest last time used". Then I thought "naaahhh, must be something else" and failed. Turns out my idea was correct somehow 367693038
I had the same idea! I was so shocked when it passed.
I had the same idea but didn't pass.
I had a solution for E using z-function 367694181
Let $$$dp_i$$$ be the answer for the prefix $$$[0, i)$$$. The solution makes use of the observation that $$$dp_{i + 1} \le dp_i + 1$$$ — if you have a string $$$s$$$ which can be partitioned into $$$k$$$ pieces, then removing the last character of $$$s$$$ gets rid of at most the last prefix, leaving you with $$$k - 1$$$ pieces.
Then you have the transitions $$$dp_j \leftarrow dp_i + 1$$$ for all $$$j \in [i + 1, i + z_i]$$$ (This instantly gives an $$$O(n \log n)$$$ solution using range-update point-query segtree).
Now maintain a set $$$S$$$ of the $$$dp$$$ values as follows.
Instead of using an
std::multisetto maintain $$$S$$$, just maintain a frequency table with a pointer to its largest non-empty value. In each iteration $$$\max(S)$$$ only increments by $$$1$$$ (due to our initial observation) but may decrease by an arbitrary value, giving us an $$$O(n)$$$ per query solution.i did same but instead of dp i greedily solve the it after applying z function. int z function we the the length of the largest substr starting at position , so keep the track of the farthest postion you can go in the prefix substr and in between if come and postion which has z value greater then 0 keep it in the vector and subsequently pop accordingly and ans is sum of length at all position ~~~~~ // this is code void sol(){ int n,q;cin>>n>>q; string s;cin>>s; auto zfun=&{ int n = sz(s); vectorz(n,0); z[0]=n; int l =0,r=0; for(int i=1;i<n;i++){ if(i<=r){ z[i]=min(r-i+1,z[i-l]); } while(i+z[i]<n && s[z[i]]==s[z[i]+i]) z[i]++; if(i+z[i]-1>r){ l = i , r = i+z[i]-1; } } return z; }; for(int i=0;i<q;i++) { int l,r;cin>>l>>r; string t = s.substr(l-1,r-l+1); vector z=zfun(t); int ans=0; vectorend; int len= r-l+1; vectortemp(len,0); for(int i=0;i<len;i++){ if(z[i]>0){ end.pb(i+z[i]-1); } while(!end.empty() && end.back()<i)end.pop_back(); ans+=sz(end); temp[i]=sz(end); } cout<<ans<<endl; } } // ~~~~~
Another method is to replace multiset with stack: 367777401
yeah a monotonic stack sort of giving what i consider ranges of influence for each non zero element of the z array. we pick for index i the latest of all possible which can 'influence' it.
For D i did something different. I ordered the colors as a,b,c such that a>=b>=c. Then i checked how many (a,b,c) triples (say d is the number of times it's removed) should be removed to eventually satisfy the condition a>=(b+c). The triples can be handled in this manner. We can repeat the triple shifted by 1 each time for d iterations. For example if its rgb and d is 3, the string would be (rgb)(gbr)(brg). We observe that it doesn't violate the given conditions.
Now to handle the left over characters, we know a>=b+c now because we removed the triples. We can pair off each b and c with an a, like (ba)...(ba)(ca)...(ca).
If there are any left over 'a's we can just add one 'a' to the start of the string. So the final string would be of the form (a)(ba)...(ba)(ca)...(ca)(cab)(abc)(bca)....
Depending on whether the first part ends with "a" or "ba" or "ca" we can modify the initial triple so that the given condition is not violated.
My implementation: https://mirror.codeforces.com/contest/2209/submission/367693394
Very cool construction! I also thought about using triplets and shifting them but the idea of handling the rest when c>=a+b didn't come to my mind.
my solution for D is as follows:
let's we have $$$r \gt = g \gt = b$$$ we want to maximize size of s in other word we want to minimize no of char we can't place in s so we try to minimize no of wasted $$$r$$$ chars.
if we have $$$r = g \gt = b$$$ then we can always make make $$$s$$$ of size $$$(r + g + b)$$$
now if r > g then we will minimize the difference $$$(r - g)$$$ and the no. of wasted chars will be $$$(r - g)$$$ to minimize $$$(r - g)$$$ we can repeat string $$$brgr$$$ untill we ran out of b.
we can see that for $$$each$$$ $$$b$$$ and $$$g$$$ we are reducing $$$r$$$ by $$$2$$$ so $$$(r - g)$$$ is reduced by $$$1$$$ with each repetation.
unfortunately i couldn't implement the details during round
367699161 I think there is a problem with testcases for the problem C, because this solution wasn't intended to pass all tests, for example if the array stayed unchanged and was 1 0 2 0 it shouldn't work, yet it got an AC.
Is interactor for C deterministic? Could you provide the source code for the interactor?
I'm asking because solutions like 367653743 (Edit: it got hacked after the comment) pass but they're obviously wrong.
BTW good contest, enjoyed the problems.
Hi, here is my solution I almost had it during contest made some small mistakes.
https://mirror.codeforces.com/contest/2209/submission/367703377
So the approach taht I went for is this, there are exactly n elements and n zeroes in the array. I check every pair from 1,2 all the way to last second pair (excluding). If there was a match I would have received output. Now if there is no match I know for sure that among the last 4 elements I have two zeroes and two numbers. So I apply an algorithm to the last three numbers and in 3 checks I can guarantee if there are two zeroes among these three or not in the following way.
(i, i+1) -> if(res==1) solved otherwise either i is number or i+1 is number.
(i+1,i+2) -> if(res==1) solved otherwise either i+1 is number or i+2 is number.
(i,i+2) -> if(res==1) solved otherwise either i is number or i+2 is number.
If somehow I get res==0 in all three operations I can successfully concluce that at least two are numbers among last three. If that is the case then it is guarantee that i-1 is definitely a zero since we already knew that last 4 elements consisted of 2 zeroes and two numbers.
Thanks but I didn't ask for the solution. My main issue is that wrong solution passes due to weak interactor.
Naive randomized solution (367712148) WAs but it takes until test 3.
Maybe their interactor is bugged and/or imperfect. A perfect interactor would probably have to solve the problem "determine if it is possible to put nonzero number at position
i, given the previous results of queries". I think this is doable by putting nonzero at positioni, and then kind of DFSing if you treat the queries as edges to see if you can end up with a valid config. But then you'd have to make sure the total counts are right, etc etc so it could be a lot more complicated.Yeah, randomized solutions are not guaranteed to pass and this is understandable. But Why the randomized interactor? or at least the non-deterministic interactor? Wasn't there a way to make the interactor deterministic? I thought it was possible due to the low constraint on $$$n$$$ and really want to see if testers also noticed this & what was there opinion from a problem setting perspective.
I think we're talking about two different things here.
"randomized solutions are not guaranteed to pass" In this case if the array is fixed from the start, if we assume each query is independent, then we have a 1/4 chance of immediately succeeding when we give a query, so our chance of failure is (3/4)^(n+1) if we make n+1 random queries. At n = 100, that's a $$$10^{-13}$$$ chance of failure.
So, the interactor must be adaptive (I'm not sure if this is what you mean by deterministic vs nondeterministic) and change the array depending on what queries you ask it / what answer you give. In this case, I think the interactor did an okay but not perfect job of changing the array since a fully randomized solution fails but the one you linked is not that much more complex and got accepted.
As you say, from the queries, we can construct a graph with $$$2n$$$ vertices and $$$n+1$$$ edges between pairs of vertices. Then we assign a nonzero value to the $$$k$$$-th vertex (the program's answer) and remove it from the graph, along with any incident edges.
Now we have a graph with exactly $$$2n - 1$$$ vertices and at most $$$n + 1$$$ edges left. To give wrong answer the judge must prove that it can label $$$n$$$ vertices zero such that no pair of zeroes is connected by an edge. This is exactly (the decision problem version of) the maximum independent set problem: given this graph, does an independent set of size at least $$$n$$$ exist?
The independent set problem is NP hard in general, but we can solve it efficiently in this case.
If any component of size $$$s$$$ has $$$s + 1$$$ or more edges, then that leaves $$$2n - 1 - s$$$ vertices and $$$n + 1 - s - 1$$$ edges for the rest of the graph, which means there are at least $$$(2n - 1 - s) - (n + 1 - s - 1) = n - 1$$$ components in the rest of the graph, and at least $$$n$$$ components in total. But since each component can trivially contain one zero, then the problem is solved.
If the problem isn't trivially solved, then a component of size $$$s$$$ must have fewer than $$$s + 1$$$ edges, which means either it has $$$s-1$$$ edges, i.e. it's a tree, which is bipartite, and the optimal solution is to set the vertices in the largest part to 0, or it has exactly $$$s$$$ edges, which means it contains a single cycle. Consider two adjacent vertices on the cycle. At least one of them must be nonzero, so we can try to remove each one from the graph, which will create a tree which we can solve as described above.
If you follow this reasoning a bit further you'll see that the only scenario where we cannot assign at least $$$n$$$ zeros to the graph is when the original graph consists of one complete graph K3, one K1 (which is picked as the answer) and all other components are K2 graphs. That's exactly the graph described in the editorial, of course, but this argument shows that this is the only possible answer.
My post contest discussion stream for ABCDE
Youtube VOD
Twitch VOD
pls never make contests again
ok ok A B E are ok... C and D ragebaited me lul shud hav tried E in contest its kinda ez if u know z fn i guess
My approach to D is different check here https://mirror.codeforces.com/contest/2209/submission/367697380
I did something similar, but more concise https://mirror.codeforces.com/contest/2209/submission/369805411
Please someone explain C in a better and more intuitive way, I'm not able to fully understand the editorial.
Think about this:
1- If you have 4 numbers, at least 2 of them are zeros. Can you determine the position of one of the zeros in 3 or less queries?
If you answered yes, then you can: pick every 2 consecutive numbers in the array exclusively except any 4, say the first 2 and the last 2. this would cost n-2 queries. Then with the remaining queries, you can use the remaining 3 queries to get the position of any zero in the remaining 4.
So the array would be something like this (for $$$n = 5$$$):
1 0 | [2 0 | 3 0 | 4 0] | 5 0or
1 2 | [3 0 | 4 0 | 5 0] | 0 02- Why would the last 4 have at least 2 zeros?
The interactor is adaptive, meaning it want you to lose by answering
0as long as it can. If you pick any 2 consecutive numbers to query them, and the interactor responded with zero, this means either there's a zero and a non-zero value, or both are non-zero values. The former means that every 2 consecutive numbers in the array contains one zero, and we queried n-2 of them, this means there're still 2 zeros left. The latter case is trivial.Now I understood, when you said the interactor is adaptive and it would want me to lose in the worst case by answering 0 as long as it can, and also the point in the editorial where they mentioned how to make the first query of indices 1 and 2 redundant.
Now I fully understand the picture and how amazing the problem was. Loved it.
Thanks for helping me out <3
Using Z-func for E feels way more natural than KMP lowkey.
orz
Auto comment: topic has been updated by OtterZ (previous revision, new revision, compare).
Auto comment: topic has been updated by OtterZ (previous revision, new revision, compare).
Just wanted to share a slightly simpler and more efficient approach for problem F
To maintain the sum of the top $$$k$$$ elements, instead of using a set, you can use two "erasable heaps". This avoids the heavy constant factor of set operations and runs much faster.
For the rerooting DP part, I completely decoupled the logic into 3 separate DFS passes:
Calculate the optimal paths towards the children from a fake_root.
Calculate the optimal paths towards the parent from a fake_root.
Traverse the tree again to fix the actual root and compute the final answers.
a neat trick: to maintain the condition of "{maximum distance, minimum ID}", you can simply use a pair<int, int> storing {dis, -id} and just take the max()
OwO UwU
The tasks were easy to understand, but it was difficult to think about the ideas. I solved 2 problems
are all these downvotes coz of c being interactive?
I guess it is because of the way that B can be solved.
maby mostly D
can not i plus answer aportly,who can reply
well done
Problem D is a bad problem, and it’s harder than Problem E.
Really? Among rated participants, $$$2000+$$$ people solved D and just $$$500-$$$ solved E.
Many people spend a lot of time on D, and didn't have enough time to solve E
Oh god,D rated 1696 on clist is considered hard and E rated 2117 on clist is considered easy.
D seems simple but actually takes a lot of time (E seems difficult, and actually lol), so more people complain about D ,I guess.
There's always a bias for later problems having higher ratings due to people attempting them in order (A->B->C->D...). But, I think the point most people are making is that D was too hard for a regular D, and E was too easy for a regular E (I don't necessarily agree with one or both statements though).
IMO D should probably be a little higher like 1800 or maybe 1900, I think E is a solid 2100, maybe even slightly harder since you had to find the N Q answer with KMP/Z-func/something like that.
Hello Codeforces,
Here is a binary search implementation for D, it is quite messy but I got it to work:
https://mirror.codeforces.com/contest/2209/submission/367805736
I am finding it very difficult to understand the problem statement for 2209B - Array. Specifically, "For each index i , find the maximum number of indices j such that j>i and |ai−k|>|aj−k| , over all possible integer values of k .". The provided modulus inequality cannot be satisfied for all possible integer values of k, ~~~~~ ]-Inf,...,-1,0,1,...Inf[ ~~~~~
. Only few Integer values for k can satisfy the inequality. It seems like, for any integer k that satisfies the provided modulus inequality.
It is asking to find the maximum number of indices j, that satisfy the inequality. It is up to you to choose a single number K from all possible integers for each index i.
I also found it hard to understand at first until I went through the sample cases.
It was clear about the requirement of the maximum number of indices j for which the inequality is satisfied.
Additionally, I thought it was also a requirement that the inequality must be satisfied for all Integer as k where the existence of any such k or Integer is enough.
I could not think in the proper way. I was just confused by the sample case and examples.
I could get the idea about the real requirement from the provided solution. Thanks.
I have a small doubt in B. It says k as all possible integers. Then why do we choose k? Does it say "possible" — to satisfy the condition?
can anyone please find what mistake I have made in problem D, this is my solution.
Take a look at Ticket 17530 from CF Stress for a counter example.
thankyou
Great set of problems!
Auto comment: topic has been updated by OtterZ (previous revision, new revision, compare).
I did a solve for B. in O(nlogn) using a BIT. Could have been a cool problem if it had harder constraints.
Started working honestly and not from AI
Please collect proof and contact Vladosiya.
for problem d i was thinking it of solving using priority queue, can anybody think of a working, optimal approach using priority queue because the one i implemented gives wrong answer on r=g=b cases
~~~~~ void solve() { int r , g , b;
cin >> r >> g >> b; priority_queue<pair<int , char> , vector<pair<int , char>>> pq; if(r > 0) pq.push({r , 'R'}); if(g > 0) pq.push({g , 'G'}); if(b > 0) pq.push({b , 'B'}); string ans = ""; while(!pq.empty()){ vector<pair<int , char>> store; bool placed = false; for(int i = 0 ; i < 3 ; i++){ if(pq.empty()) break; auto ele = pq.top(); pq.pop(); int temp = ans.size(); if(temp > 0 && ans[temp-1] == ele.second) { store.push_back({ele.first , ele.second}); continue; } else if(temp > 2 && ans[temp-3] == ele.second) { store.push_back({ele.first , ele.second}); continue; } else{ ans.push_back(ele.second); placed = true; if(ele.first > 1) store.push_back({ele.first-1 , ele.second}); break; } } for(auto ele : store){ pq.push(ele); } if(!placed) break; } cout << ans << endl;}~~~~~
I wonder why greedy algorithm doesn't work in problem E (WA on test 18).
For each query
l, r, putlinto a stack. Forj=l+1..r, if $$$s_j=s_l$$$，put 'j' into the stack, while $$$s_{stack.top..j}$$$ is not prefix of $$$s_{l..j}$$$, pop it. Finally add the number of elements in the stack to the answer.I have tried the similar approach of using the Stack, But got TLE on TC 8 in JAVA. Can you just provide you solution here for more clarity.
My Submission : https://mirror.codeforces.com/contest/2209/submission/369582055
My code
Time complexity is $$$O(nq)$$$
someone please help me find the bugs in this solution for problem D
I struggle to understand div2D solution. The code and its idea is clear, but the reasoning in solution is not.
How does "When three continuous ghostfires with different colors, the color of the next one must be equal to the second one." lead to observation "Using the feature, it can be proven that the task is the same as pairing two ghostfires with different colors". I assume in "then it's valid to add just a single ball", the ball in this context is a ghostfire, right? "remember to choose the pairs with the same color ghostfires as the first ghostfire to avoid getting wrong on case r=g=b=2" — what is it about, could you explain?
Problem A says he fights monsters in order and solutions seems he can fightin any order
..... for me its battle of english
Even in problem b i didnt even understood the question lol its says for all k what does it even mean for all possible k