Hi everyone!
It's been a while since I set problems for Codeforces competitions, so I hope that you had sufficient opportunity to rest before dealing with my problems again. Oh, no-no, there's nothing to worry about! Probably! I promise!
jeroenodb and adamant (that's me!) are happy to invite you to Codeforces Round 869 (Div. 1) and Codeforces Round 869 (Div. 2) which are going to take place at Apr/29/2023 17:35 (Moscow time). Participants with a rating strictly lower than 1900 will participate in Division 2, while participants with a rating of at least 1900 will participate in Division 1.
All the problems are prepared by us, and we would like to thank:
- dario2994 for rejecting sufficient amount of problems for me to be able to set Oleksandr Kulkov Contest 3, for thorough and dedicated coordination and for suggesting one of the problem ideas for the round.
- izban, gamegame, tfg, fedimser, Endagorion, nor, rivalq, errorgorn, antontrygubO_o, redpanda, Runtime-Terr0r, izhang, Everule, NemanjaSo2005, ak2006, ayhan23, SlavicG, hashman, jqdai0815, willy108, madlogic, LeticiaFCS, tanus_era, nigus, Plurm, mathdude42, SajidZakaria, ace_loves_xq, InternetPerson10, alwyn, -is-this-fft-, DJeniUp and dorijanlendvaj for testing and/or valuable feedback and insights about the problems.
- MikeMirzayanov for Codeforces and Polygon and KAN for all his effort in coordinating coordinators :)
In both divisions, you will have 2 hours and 15 minutes to solve 6 problems.
Score distribution in both divisions: 500 — 1000 — 1250 — 2000 — 2500 — 3000.
Good luck and have fun!
The editorial is out.
Congratulations to the winners!
Div. 1:
Div. 2:
As a tester, I enjoyed testing the round. Good luck to all the participants!
Runtime-Terr0r orz. I hope your rainbow looks sexy.
Runtime-Terr0r orz!
Dukkha Dukkha and rainboy have pretty sexy rainbows
Sometimes I wonder, if Dukkha and rainboy are same person's account.
Here is the man, the myth the legend. THE KAIBOY ...
kaiboy
After seeing the first question, inner me: it's time to die.
Imagine commenting,instead of attempting the problem during contest.
As a tester/problem discusser, I hope the participants like the problems as much as I did.
Yeah i hope so!
As a back-to-back tester, I really enjoyed testing this round! very interesting problems )
Hope everyone will able solve at least 3 problems
As a tester, I saw a twist on one of the problems that I have never seen before!
Now that the contest has ended, I am curious to what you were referring to.
The custom prepared program for Toys is something I have never seen before.
Yeah this is something new for a codeforces contest. However, I witnessed something similar at IEEEXtreme 14.0 about 3 years ago at this problem. They made an entire downloadable game and it strangely includes all testcases. Not sure if you can still download and play it though.
As a tester, Best contest I have ever seen!
writing announcement 4 days before the round -> good round
As a tester, I regret not doing this round officially.
неееееееееет
As an early tester, I'm pretty sure I haven't seen the newer problems but I'm sure they'll be interesting.
As a tester the round has cute problems :DD
before contest, I read this comment, I felt it was sarcastic based on your DP. My prediction was right xD.
As a participant I won't participate
As a participant, I will try my best to participate in the contest. I hope I will give my best.
And also best of luck everyone.
Holy hell, so many testers!
Hope this round is cool
Is it rated for everyone?
Yes. Everyone with < 1900 rating can patricipate in the Div. 2 rated and everyone with rating >= 1900 can participate in the Div. 1 rated.
As a Div 3 tester, this round will be interesting and challenging for Div 3 participants. Good luck and hope you enjoy the round! :)
hi fellow friend. how so good tester. teach me your ways :pleading_face:
As a participant, I will participate. Wish everyone the best of luck and positive delta!
As a first-time Div.1 participant, I hope that I stay at Div.1.
UPD: Mission accomplished somehow.
First time Div 1 here as well! Just turned purple 1 minute ago.
Congrats and good luck
Very early score distributions indeed!! ♥
Clashes with LeetCode Biweekly 103
Codeforces >> Leetcode
:)
Div.1 and Div.2 will both be rated?
This is part of an old Bug Which is reported many times. Here I reported. instead of supporting, people started downvoting, so nobody works on it.
If someone reports bug, and others support the initiative, then bugs could be solved by getting developers attention.
https://codeforces.net/blog/entry/114097
Good Luck for all participants
How many common problems between the divisions? Can't figure out from scores.
Hopefully to reach cyan again!good luck everyone!
I hope to stay cyan :(
Hey if anyone is interested in becoming friendly competitors, you can reply I'll add you and we can compete together during contests.
If you add me, please let me know so that I can add you back!
How to Approach hard problems D, E and F in DIV2
Hoping to solve till Div 1 C today and achieve my first ever rating plus as master, and first ever rank maintainance as a separate Div 1 participant.
Self Jinx. Back to back FSTs after this comment. Sad
Let's make it three in a row!
Good luck to all the participants ;)
It is game time.
people who will realize div2 c twist after contest :( me who got it during contest :) after getting two WA
then it's a :) for me too
What's the twist?
v[r]-v[l] i was doing earlier but v[r]-v[l+1] this was indeed a twist for me atleast
Lmao, I got stuck trying to do it with segment trees. When I switched my approach, there was hardly time left for casework!
Hmm oki
Can you please explain why l+1 is used here with an example?
i am using prefix sum and storing a cnt for the index 2<=i<n v[0]=0,v[1]=0 with condition if(v[i]<=v[i-1] and v[i-1]<=v[i-2])cnt++; v[i]=cnt;
example :- 1 2 4 3 3 5 6 3 2 1 v would look like [0,0,0,0,1,1,1,1,2] and suppose to query is 4 7 then do the casework if(r-l+1<3)cout<<r-l+1<<endl; else { int dif=v[r]-(l+1<n?v[l+1]:0); cout<<r-l+1-dif<<endl; } why l+1? because we have to consider elements from l to r inclusive but for lth index my answer would be stored in l+2th index given the condition above but I have to include my lth so i will substract v[l+1] till which I don't have to consider; here answer for this query will be 4
Thanks <333
you are too day^-1
Many people would have left due to problem A. 17k registrations and only 6k participants
explain C, pls
Use prefix sum. Do casework.
i used prefix sum, but dont casework(
Much casework...
what is wrong in my case
Use this test case
Correct answer is 2. Your code is giving 1.
I need it too. Got WA 3 times. Anyone pls explain.
Store all the important points, i.e., where $$$a[i]>a[i-1]$$$. In this case, $$$i$$$ and $$$i-1$$$ both are important points.
Now for a query just check how many important points are between $$$l$$$ and $$$r$$$. Add $$$1$$$ if $$$a[l]$$$ is not an important point. Similarly, add $$$1$$$ if $$$a[r]$$$ is not an important point.
Think why it's working!
https://codeforces.net/contest/1818/submission/203949170
I have an array of "holes" where i store the indexes where it is bad, aka i >= i+1 >= i + 2
Then I just binary search for the leftmost hole, rightmost hole then the answer is
r - l + 1 - hole_countIt is sort of doing binary search on intervals.
There is some more casework (e.g.
r - l + 1 < 3, if there are no holes, if the leftmost / rightmost hole does not fully cover the left/right portion)Time complexity: O(n + q log n)
Suppose you have three consecutive elements $$$x$$$, $$$y$$$ and $$$z$$$ where $$$x \geq y \geq z$$$. Then for any range that includes $$$x$$$ and $$$z$$$, there is no point in keeping $$$y$$$ in the subsequence, since any subsequence that contains $$$y$$$ must exclude either $$$x$$$ or $$$z$$$, whereas it would have been better to keep both $$$x$$$ and $$$z$$$ instead ($$$x$$$ can have an easier chance of connecting to stuff in the left since it's $$$\geq y$$$ while $$$z$$$ can have an easier chance of connecting to stuff in the right since it's $$$\leq y$$$).
My approach was to mark all such $$$y$$$ as "useless" indices. The non-useless indices (aka useful indices) will already form an almost-increasing subsequence, so we can always include them. We can use a prefix sum to count how many useful indices we have so far. Now, for each query, we can count all the useful indices between $$$\ell$$$ and $$$r$$$. If either of $$$\ell$$$ or $$$r$$$ are useless, we should add it to our subsequence too.
My submission: 203942625 The rem vector marks useless indices.
I'm not a good fisherman bcz I couldn't catch the fish from the graph(problem D xD)...
The webpage with a simulator for problem D was very helpful. Thanks!
No tougher A please, people are simply skipping contest after seeing A.
I think understanding the statement was tough but the implementation was easier.
Can Someone Tell The Idea For Problem C If Instead of Subsequences It Was Subsegment?
Use prefix sum. For each query, do casework on l
Can You Please Elaborate More? It will be Helpful
we can observe that if there is a decreasing sequence of size n( n >= 3), then we must remove n — 2 numbers and don't erase the smallest number
I misread the problem during contest and wasted my time solving "Subsegment" version ;(
I don't know if it have simpler solution but I have a possible solution for "Subsegment" version of Div2C using segment tree in $$$O(n + qlog(n))$$$.
Here is my code
Consider $$$mark[i] = 0$$$ if $$$a[i] \geq a[i+1] \geq a[i+2]$$$ and $$$mark[i] = 1$$$ otherwise
We can compute $$$consec[i]$$$ as number of consecutive ones in $$$mark$$$ starting from position $$$i$$$.
Also we can store $$$head[i]$$$ as position of first of consecutive ones including position $$$i$$$ (and if $$$mark[i] \neq 1$$$ then $$$head[i]=-1$$$)
Now using $$$consec$$$ and $$$head$$$ we can solve it using max query on segment tree. it is important when we making query on $$$[l, r]$$$ we don't consider the ones in $$$mark$$$ which are in the right of our range. so we have to temporarily making a minus something add query on segment tree to decrease consec values on the rightmost of our range. (How we know where it started? remember we stored $$$head[i]$$$)
pseudocode of answering each query:
i was also solving for subsegments initially the problem then essentially reduced to taking max of intersection (l,r) over certain intervals which i was not able to figure out within the time constraints
The demo page really helps a lot when solving div1 D.
Hi, the system verdict my solution was used the edge (2,4) twice while I checked the output, it doesn't seem like that. I don't know what's happen. Is my solution wrong or is there any problem with the verdict system? https://codeforces.net/contest/1818/submission/203958546
You forgot to output the number of edges in your subgraph. Because now all numbers are offset, the checker comment is weird.
Excellent fishy contest
Is it me or C was disgusting to implement?
Nope, check my submission :)
For Div2, difficult A and nice C.
can you explain c?
Solution or problem introduce?
anyone pls explain how to approach b in div2
Write brute force for $$$n\leq{10}$$$ and try to see a pattern... unfortunately that was enough to solve a problem.
If n is odd the there will not be an answer because sum of array = $$$\frac{n(n+1)}{2}$$$ will be divisible by n.
So, now assume n is even. Now consider the permutation p = [1,2,3,4,5,6,7,8,9,10,....] and array a = [2,1,4,3,6,5,8,7,10,9].
If len = r-l+1 is odd. then p[1...len] would have been divisible by len. Also the p modulo len : p[i]%len would be repeating. For example, modulo 3. p = [0,1,2,0,1,2...]. So any subarray of len would be divisible. By making it into array a, we would make sure that in any subarray of len, there is exactly one different element in a than perm.
If len is even. Again p modulo len would be repeating. And for any subarray of len in perm. sum modulo len is $$$\frac{len}{2}$$$. In array a, if subarray starts at odd index(1-based) then set of elements modulo len would be same as in p. But if subarray starts at even index, say l and ends at r(r = l+len-1), the a[l] = perm[l]-1 and a[r] = perm[l]+1. So total sum still remains $$$\frac{len}{2}$$$ modulo len
IN DIV2 D,
We just check for all vertices who have atleast 4 neighbours, whether they are a part of a cycle or not.. Am i missing something?(except implementation)
That's what I did
You have to check if at least 2 more vertices are not part of the cycle.
There are multiple cycles possible from a vertex. If you choose a larger cycle and checking for 2 more vertices return false, it is possible that a smaller cycle exists with 2 more vertices.
I did consider that... IDK what's wrong in my code tho!!
How to solve Div2E/Div1C? UPD: Nevermind, gonna read the editorial
Div1C may not be suitable here. I think Div1C should focus on thinking, and only use basic algorithms like dp or greedy. But this problem is nearly a pure math problem.
Anyway the problem is very nice. Using it in icpc contests may be better.
Isn't Div1C focused on thinking and doesn't use any algorithms at all?
after getting the answer in terms of the coefficients, i think its mostly more knowledge based, both the approaches to compute it (seems to me) you need to know it, or you cant do it.
Well, yeah, you might be right. But I feel like it's a pretty basic math fact. And even though I knew it, when I acquired a formula via coefficients it took me a long time to realize that I could use interpolation to get one coefficient because it was a new angle for me on this. I think I have never before used the interpolating polynomial in competitive programming.
I had never heard of lagrange interpolation before :(, and i consider myself more versed in maths than an average person since i did make our countrys tst.
Ofcourse, its my skill issue, and i learnt something new now, but i think maybe you are biased about it being a basic math fact(for its level). I know a lot of my friends who were in the same boat as me, having got the answer in terms of the coefficients, but no clue on how to proceed.
div1 D was just playing the demo game :sob:
In $$$B$$$ I wrote something weird and it passed. Is it correct?
Iterate over all edges. Fix edge. Let it be in the tail of fish, and let one of its vertices be the center of the fish. Do simple dfs, which will not go into fixed vertice in tail. When in dfs we try to go to center of fish, and there is at least one unused neughbour vertice of center, we found answer. Otherwise continue.
including yourself (member 1) this line should be bold on A (:
This was my first contest! Glad I passed at least pretests on A and B. Then I think I understood how to deal with div2C but my solution was too slow so I don't submitted. I preprocessed the whole array finding the bad triplets for which x >= y >= z. Then basically for each query I would count how many "bad triplets" fall totally into the interval [l, r]. Then I would subtract this number from r — l + 1 which would be the answer if no bad triplets fall inside. Is this approach reasonable? How can this be optimized?
You can store a prefix sum and now count how many are in your range in O(1)
dang I spent too much time thinking how to write d1B knowing the solution
My ideas on d1C
if we knew n-th and n-1-th coefficents of A and B then we know the answer to the problem, and to compute them (lets say we are finding for A) we use interpolation by Newton to gradually build A so that it satisfies first i+1 points and deg(A) <=i; if we modify for point i+1, then lets say P(x) was our previous polynomial, and now P1(x) will be modified P(x) P1(x) = P(x) + (x-0)(x-1)..(x-i)*((y[i+1]-P(i+1))/(i+1)!), and we just need to find P(i+1) to know the largest coefficent of P1(x), and the second largest coefficent of P1(x) will be largest of P(x) + ((y[i+1]-P(i+1))/(i+1)!)*(0+1+..+i), so we can always find two largest coefficents of P1(x) if we can quickly find P(i+1), but P(i+1) can be counted using interpolation by Lagrange, and since x[i]=i it looks like every L[i] is a factorial divided by two factorials and i(maybe (-1) in a certain degree), and if we could somehow update them fastly after each step, we could find P(i+1).
Is my approach correct, and if yes, then how do we finish this?
upd.: i checked the submissions and it loosk like there's something simpler, but I don't know
D1A/D2C: Let [L, R] be a maximal non-increasing block (which means a[i]>=a[i+1] for L<=i<R, L==1 or a[L-1]<a[L], R==n or a[R]<a[R+1]) is min(2, R-L+1). Therefore we can solve the problem by prefix sum, but we need to process for blocks on the boundary of the queried range.
D1B/D2D: We need to find a node u with deg[u]>=4 and a cycle contains u. We can build a spanning tree rooted at u of the component of u, and find an edge connecting nodes in different subtrees of u.
D1C/D2E: If d==1 the problem is simple: Since A(x)=a1*x+a0, a1=A(1)-A(0), and B(x)=A(x+s)=a1*(x+s)+a0=A(x)+a1*s, so s=(B(0)-A(0))/a1. If d>1 we can find the (d-1)-th order difference of A and B, they will be polynomials of degree 1, and solve the problem as d==1.
For array {a[0], a[1], ..., a[n]} we denote it's difference as {a[1]-a[0], a[2]-a[1], ..., a[n]-a[n-1]}. Aussume p is a polynomail of degree d, since the coefficient of x^d of p(x) and p(x+1) is the same, they will be canceled in p(x+1)-p(x), so difference of a polynomial of degree d will be a polynomial of degree d-1. Also we can see that the first term of k-th order difference is sum(0<=i<=k)(a[k]*(-1)^k*C(k,i)). So by calculating the (d-1)-th order difference we can turn A and B to polynomials of degree 1.
Hi. I wonder if s = (B(0) — A(0) / a1, is it correct when a1 % MOD == 0? Or can you prove (d — 1)-th order difference of A(1) is not zero. (0.0)
By the constraints of the problem, the d-th coefficient a[d]!=0. If the highest term of p(x) is a[d]*x^d, then the highest term of the difference of p(x) is d*a[d]*x^(d-1). Therefore, the first coefficient of (d-1)-th order difference is a[d]*d!, which is non-zero modulo 998244353.
thanks. I understand ~
I am getting TLE on test case 24 in Div1 B. please help. Here is my submission. 206435558
It seems that conqueror_of_tourist beats tourist again.
Wouldn't say so
Tourist is King System testing Change Everything On Problem E Most People Got FST but Tourist donot That is Tourist Experience he remain King
Fake news, hehehe
FST:(
Fuck me xd I haven't cleared that shit after debugging:
Nice contest, had fun
Huh, no random maxtest in E pretests?
Generally, I didn't want to make pretests for this problem particularly strong, as the key observation could be guessed, and I didn't want people to brute-force their guesses against the pretests. Test 6 is quite large, but it only has very large numbers in the input. In the hindsight, I think I overdid it a bit, and it would be better to include the test 7 into pretests as well, and it was fully random.
Did you explain your intention of the weak pretest to the testers or coordinators? If I were among them I would have strongly opposed the idea.
I did not.
That's pretty sad, but it doesn't surprise me. There were 33 testers and they didn't pay attention to this, while this is one of the things that they should exactly look for.
I generally consider the quality of testing on codeforces as rather poor. Maybe it's a good idea to create some kind of checklist for them to follow, which would contain stuff like check the statement for unclear things and typos, check the strength of pretests (or at least if they contain a random maxtest/everything that they should contain), think if some problems have already appeared before etc?
I think this in particular is because testers are simply not exposed to pretests/systests composition. Few years ago, testing was done on Polygon directly, and now it's just virtual contests in mashups, so they don't really get enough information for quality assurance.
I want to say three things (I was the coordinator):
I should have noticed the small number of pretests compared to the total number of tests (I usually suggest to the authors to have tests=pretests in hard problems, as antontrygubO_o suggested me when he coordinated me).
My opinion is that weak pretests are always bad. I cannot think of a single exception.
If adamant had told me that he wanted to have weak pretests because [see what he wrote above], I would have tried to change his mind. If he remained adamant (pun intended) about his decision, I might have allowed it. I feel like it is something an author can decide in certain problems (after all, Codeforces has never said explicitly anywhere that pretests are always as strong as possible), and this one is a problem where it makes sense (i.e., 1 person out of 10 might agree with Adamant).
Thank you for explaining the situation.
I too believe pretests should be as strong as possible. However, I know some people have a different opinion and they have a right to challenge the tradition.
What I want to say is that they can try to change something, but it must be done through communication. This time it was done by a single person and I feel that is much more problematic than the weak pretest itself.
If I had been consulted about this problem, I would have suggested adding the line "the pretest of this problem is intentionally made weak". This is just an example, but anyway hearing others' ideas could certainly make the situation better.
I hope the future CF rounds will be prepared with better communication.
So happy to have AC-ed Div2C at 2:14:50 in the contest.
adamant Could you please mention first solvers for each problem ? Today is the first time for me to first solve problem. (Problem Div.2 B)
Well done , Mr_7ammoda !!
Congratulations :)
Gamedddd
Rating boost thanks to div1C.
Very good contest. Div2C and Div2D were interesting.
As a tester, I hope that you have enjoyed this round.
Div1D is one of my favorite problems that I have seen on Codeforces, thank you.
Why are 6 files considered enough for Div1E's pretest... And if you know the solution you find the cases with small $$$n$$$ are not useful, and there exists only one (possibly) useful pretest. Why?
My bug is my fault (detail: I had to check cutting the leftmost/rightmost contiguous intervals (instead of just one element), but I am strongly against having deliberately weak pretests because the contest would heavily depend on hidden information.
But it does depend on hidden information every contest, as long as it's not an official policy to make pretests sufficiently strong. At the moment, there is just no guarantee that the pretests are comprehensive, and you can't (and, imo, shouldn't) depend on it. Of course, one can argue that there should be such a guarantee, but (again, imo) to give it there should be a global decision, rather than just a tendency.
Thanks for reply, yes, it does depend on hidden information every contest and that's why I dislike the current pretest rule. And your point:
makes sense.
Yet, in a particular contest, the more you put useless cases into pretests, the larger the factor of guessing hidden information, and the worse (I think) the contest becomes. Or at least "tendency" changes too much. I don't think it is good that one problemsetter can change it (In my opinion this is what the coordinators should keep).
Nice contest! Enjoyed D. B Failed system test, but appreciated to contest authors.
A_G hitting LGM in style 😎
Reference Blog
He is from which country? Any idea anyone?
div2 a > div2 b
This round was cool but i really hope we dont see more problems about polynomials at D2E/D1C, lol
Finally, my color got changed.
Problem A was a bit tricky tho(or the problem statement was somewhat confusing), it took me around 20 minutes to figure out the exact solution.
Div2 top5 are alt accs. As always :(
I know it's a different blog but why the upcoming contest 870(div2) registration will start at the time of starting of that contest then how people are supposed to register ?? or is it a bug?
ahrorov.5758
We know it
We know you are a faggot)))
Can someone tell me how to solve Div1B/Div2D in $$$O(n+m)$$$?