Hello, Codeforces!
waaitg, Cocoly1990 and I are glad to invite you to Codeforces Round 906 (Div. 1) and Codeforces Round 906 (Div. 2), which will take place on Oct/28/2023 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours and 30 minutes to solve them all. Note that one of the tasks is split into two subtasks.
We would like to thank:
- TheScrasse for his brand new coordination.
- KAN for the great help with round preparation.
- Alexdat2000 for Russian translation.
- errorgorn for his 1-year coordination and Monogon for his 2-year coordination of one problem.
- waaitg for donating his Dead by Daylight time to prepare the problems.
- errorgorn, Kubic, zhangjianjuncd, doroc, DoverHi, alwyn, Yakumo_Ran, AquaMoon, Vladithur, DrSwad, abc864197532, null_awe, irkstepanov, KAN, gamegame, tnaito, _irohasu_, mango., Xylenox, imirdy, GusFring, LRJf, SomethingNew, avi15 and gs20036 for testing the round and their invaluable feedbacks.
- Vladithur, errorgorn for their profound contribution in tests making.
- MikeMirzayanov for amazing platform Codeforces and Polygon.
Score distribution:
Div. 2: $$$500$$$ — $$$750$$$ — $$$1250$$$ — $$$2000$$$ — $$$(1250 + 2500)$$$ — $$$3250$$$
Div. 1: $$$750$$$ — $$$1250$$$ — $$$(750 + 1500)$$$ — $$$2000$$$ — $$$3500$$$ — $$$3500$$$
As always, wish you all get a non-negative delta in this round!
UPD1: Editorial
UPD2: congratulations to the winners!
Winners and first solves
fuka round!
fuka round!
fuka round!
what is fuka round?
As a writer, I think this Round is very interesting.(btw, Please give me contribution.)
as a tester, I agree
As a random reader, I also agree with you guys
as a loser in this round i also agree.
As a contender, I also agree.
Okay but that's literally what they all say (btw, Please give me negative contribution.)
i give you what you want. (please give me possitive contribution)
As a agree-er, I contend!
As a tester, problems are very cool! ><
Hoping that it would be a great contest
chinese round , what do u expect?
I hope it will be great contest and get more points.
First Div1 contest for me! Hope that i can solve at least one problem!
I am a newbie, could I take part in Div 2 and solve the easiest problem?
Yes
Contest timing clashes with El Clásico.
El Classico timing clashes with Contest
As a player, I wanna be red.
i was forced to test
Thanks for your voluntary test!
Thanks for the early Score distribution lol:)
Chinese round at usual time. It's unusual, isn't it?
hope get positive rating delta
can't wait to become blue
can't wait to become purple
.
The contest was proposed more than 2 years ago, and one of the problems was accepted in another round from 2 years ago but ended up not being used.
.
Contests are not easy to make and require a lot of work, but there are many people who propose them. In fact, currently there is a long queue and you have to wait 1 year (for div2) and 3 months (for div1) to get a coordinator. Then, the preparation and testing phase is usually a few months long.
GusFring orz
Imakf round!
This round time clashes with IEEEXtreme (which happens once a year) and many contestants can't do both!
Is it possible to delay this round by one day?
just do that round since its once a year, this is just another regular cf round
I am new to this. Please advice a math book and algorithms book. I barely can solve even 1200 problems
You don't need books, just pick a random problem and try to solve it. When you're stuck change problem or look editorial(read one statement and try to do left part yourself, if you couldn't, read one more, in the end code solution yourself). If you found anything you don't know in editorial just google it. cp-algorithmms and geeksforgeeks are good to learn topics.
Is it rated?
I think you wanted to write: "How will everyone get non-negative delta if it was unrated" but it's possible to everyone get non-negative delta if it was unrated.
If it was unrated everyone would get 0(which is non-negative) delta.
Woah, i can see a lot of reds
Clashing with LeetCode Biweekly. Would skip this one.
Codeforces round is always priority.
Nah bro, Codeforces round are always more on mathematical side and gets boring to me after I read problem statements. At one point, I was only doing CF, now when I went to Leetcode, I cant enjoy CF rounds anymore.
leetcode clashes with cf*
Why do you schedule contests on the same day as IEEExtreme? T~T
We check the CLIST calendar before scheduling contests, and there is no IEEExtreme there.
Impossible wish: "you all get a non-negative delta in this round!"
.
.
Grandmaster when?
Hope to be candidate master tonight! (last round I dropped to expert lol)
congrats
thx
I've been consistently losing rating, wish for a positive rating change for me!!!
Hope IM.
Upd: Success!
meh
You'd still be orange
congrats
All top 4( 3700 rating) registered for this contest.
Yes/No contest
6 WA for C Div. 2 C problem. i will get -100 delta :(((((
Back to Specialist :(
Hopefully expert
I chose not to participate in this contest because Imakf had published the editorials accidentally with just codes beforehand and it was there for around a minute or two. Looking at them gave me an unfair advantage in understanding the used data structures and algorithms. Entering the contest with those ideas would have been an act of cheating, so I decided not to participate. Instead, I did leetcode biweekly.
LMAO fr?
seems like a troll comment to me
It's not a troll comment, the editorial was accidentally posted for 5 minutes.
Could the authors/CF admins confirm whether the round will remain rated in light of this issue? I could understand unrating the round given that this is obviously a pretty significant issue (even though empirically, it's unclear whether this actually meaningfully affected the Div 1 standings; there weren't e.g. far more solutions to D-F than I would expect), but I'm hoping a decision is confirmed sooner rather than later since I'd rather not spend too much time wondering if I made 3300 today...
The round is rated!
Why such a tight time limit in D and E1...
I guess that because they are linear complexity...
I thought both of them are O(n log n), what are the linear solutions?
Edit : I saw the editorial, and I can understand it now. Both problems and solutions are cool!
Yeah, but on cf 1 second is really rare constraint, don't you think? Even linear problems have at least 2 second... I am not blaming, just curious, as i really would love to be a problem-setter one day
can E2 be done with bitmask dp?
Unlikely.
It 230262342 pass but in 3759 ms. probably not intended solution...
For easy version I checked for every pair of segments that occur together so when I saw m=10 I thought maybe we could use bitmask dp and it would pass but didn't had time to try it out. Thanks!
230240897 1731 ms
how do you do C?
Hint: Deque
if count1 != count0 then answer is -1 cause one operation increases both by one and in the final string both have to be equal
Try to balance the leftmost and rightmost index each time using at max 300 operaions
How do you proof that this will work though, i thought about brute forcing it like this but couldn't proof it
If 2 index are same then doing operation between them does nothing and doing an operation that don't cancel either one of them affects the rest elements outside them also. Rest was proofbyAC.
I was mostly looking to bound the fact that less than 300 operations will work
I simulated it with a string, we have i = 0 and j = n — 1 if i and j are both 0 then we add an 01 at j, if i and j are both 1 then we add 01 before i, and we stop once i >= j. Also, if n is odd then it is obviously no.
If $$$n$$$ is odd or there isn't the same number of zeros as ones, the answer is $$$-1$$$.
It seems that fixing the first and last element first with just doing operation at the beginning or end always works (I don't know proof).
How do you prove Div1A? I spent 30+ mins trying to prove the obvious approach and got no where before just deciding to try to proof by AC (which worked).
It feels way tougher than Div1B and C1. Div1B actually feels more like a typical Div1A to me in that sense — It requires one fairly simple observation which has a straightforward proof. I suspect the solve counts on it would be equal (if not higher) if their places had been swapped.
prove it by ac lol
for real
Obviously, the string has the same number of $$$1$$$'s and $$$0$$$'s, so if you have the string $$$0xxx0$$$, you can add $$$01$$$ to the end, to get $$$0xxx001$$$, and "remove" the $$$0$$$ and $$$1$$$ from the edges, so you basically go from solving $$$0xxx0$$$ to solving $$$xxx00$$$ in one move (a rotation), and since the string is balanced, eventually you will find a $$$1$$$ to match out with the $$$0$$$ at the end. So at the end, it should take less than $$$n$$$ insertions
The case with $$$1xxx1$$$ is similar, $$$1xxx1\rightarrow 011xxx1 \rightarrow 11xxx$$$
Thanksss
Finally I got negative delta -_-
How to solve C?
For C problem(Div 2)
answer exists when number of ones=number of zeroes in input string
but how do we construct answer ?
How to solve E faster than $$$\mathcal{O}(n\log(n))$$$?
Also, what's wrong with my solution to D? 230219737 It looks linear to me.
Ok, authors' solution (from editorial) to D works 998ms (time limit is 1s): 230265951. With other compiler 842ms: 230266166. After changing it to use vector like a human being instead of array operated like a stack both times go up.
Authors' solution to E maybe takes 1247ms (230266784) out of 2s (yeah, that's already way too much) but it doesn't even use any vectors while there two damned trees on the input and we are supposed to create another graph and find SCC in it.
I don't want to complain, but I actually do. These time limits are a joke (and they would be bad even for these squeezed model solutions, which shouldn't be optimized at all) and I strongly suffered because of them. I expect some action from authors or coordinators (or if I'm retarded and wrong somewhere tell me that).
It's my fault. All the submissions from testing got AC comfortably, so I assumed the time limits were fine and I didn't check the running time of the official solutions.
Next time I will double check.
Thanks for sharing--incidentally, does anyone know why the authors' solution to D is so slow? My code (not optimized at all, makes full use of vectors) runs in 340ms, and a priori I'd be very surprised to see a linear solution with the given bounds take a full second.
The solution runs in 514 ms on Polygon (with C++17). Right now I don't know why it becomes so slow on C++20, maybe it's because of the input.
I'm sorry. But it is strange that on polygon the intended solutions do run faster or inconsistently, compared to on main site.
For D, intended solution runs 498ms (with stacks and without any optimization), and one of the testers runs <= 220ms. Considering the implementation for this problem are barely the same for most people, we set the TL to 1s.
For E, intended solution runs 888ms, and errorgorn's HLD solution runs 795ms. Anyway, for this problem, the TL is tight. It's better to set 4s. I apologize for that.
I'd rather win a round than get an apology, but shit happens. Problems were nice anyway, so don't give up.
Maybe it’s good to say something constructive. Every time when I hear that someone is choosing the time limits to (constant)*(model solution) I lose my mind — it doesn’t work like that at all, it strongly depends on the problem. To choose the time limits you should have possibly many approaches implemented and consider why some of them are slower than the others and what do you want to expect or/and at least consider “what actually could people do in this problem”, like “is it tempting to do something more complicated?” or “is it tempting to repeat something three times?”. For example in yesterday’s E it would be “what if someone wants to create graph with vertices not only for each power of 2 jump, but also extra ones for each edge and vertex of the trees?”. I wouldn’t solve that this way, but I wouldn’t say that it’s impossible.
Errichto once told me something that works in theory and is kind of automatic. He said that a good way is to set the time limit to be equal to the geometric mean between the slowest solution that we want to allow to pass and the fastest that we don’t want to pass. In practice it doesn’t work like that. An example is a problem with $$$\mathcal{O}(n\log(n))$$$ model solution and slower $$$\mathcal{O}(n\sqrt{n})$$$ solution — it might be a case that we’d have to accept the fact that the squeezed slower one might pass to make the model one pass comfortably (or try to change the problem/limits to fix the issue if it’s possible). For example in yesterday’s D such solution is probably link-cut based — I guess you wanted to don’t let it pass, that’s ok, but I don’t think that 1 second is really necessary to do it with one million numbers on the input.
About time limits in the round there is also a general stuff. I think if someone asks about most classic most popular cf time limit, the answer is “2 seconds”. So I’m surprised that time limits set to 1 second in many problems where the solution isn’t something that would obviously take zero time (like $$$\mathcal{O}(1)$$$ or $$$\mathcal{O}(factorization)$$$ for $$$n$$$ up to $$$1e9$$$) didn’t bring any attention. Also these 2 seconds are meant for the problems which don’t do anything crazy and problem with $$$\mathcal{O}(n\log(n))$$$ size tree-structure sounds way more complicated. So I don’t think that either 2s for D or 4s for E are automatically good choices.
I think your solution's slow runtime on D (as well as the authors') is caused by an I/O bottleneck. I resubmitted your first skipped solution using cin/cout with standard optimizations (
Switching to cin/cout cuts your runtime by about 500ms, easily fitting your solution into the time limit.
ios_base::sync_with_stdio(0); cin.tie(0);) and then with the original code (in case the slow runtime was caused by poor server performance during the contest). See below (first two results are your solution, next two are with cin/cout):What's if my solution would do something more complicated but still linear?
I'm not taking a position on whether the time limit was appropriate--I was just curious about why linear solutions were running so close to the 1s time limit, and once I figured it out I wanted to post in case anyone else had the same question.
The author's solution is hacked (tl). Hack And Benq's solution during the contest also didn't survive.
And the hack test case is not even carefully constructed. It's just two random chains. I didn't see the TL of this problem make any sense. And it's totally unfair that heavy-light decomposition can pass this problem and binary lifting can't.
Although I didn't solve this problem during the contest, I feel it's better to rejudge this problem with a larger TL.
Did something happen about it? Model solution not working sounds serious
I went here to check if you complained (and if not to complain myself).
There is a tendency for Chinese authors to write insane constant optimized solutions and then set TL 2x (or worse) from them. I remember one ptz contest where the bottleneck was calculating nimber multiplication, and TL was set as 1.5x from a solution that uses the fastest nimber multiplication code from yusupo judge.
I don't want any rejudges or anything, but I want coordinators to check those kinds of things.
D's idea ?
Always use 1 and try greedy
If you can merge index x and y then you can merge 1 with x or 1 with y. By contradiction assume that you cannot. So ax < cx and ay < cy. Adding : ax+ay < c(x+y) < c.x.y. A contradiction. x+y < x.y for all positive x,y. Except for x = y = 1
For Problem C Div-2 : Who else overthinked and overkilled just by ignoring n<=100 constraint..??
Ohh was it 100?? I literally assumed n of the order of 105 Now it makes sense why the construction is possible within 300 operations
bad task div1 C
timelimit on E1 so tight (for python atleast) ;(
any E ideas? I try scnaline, but, not working for me :)
Why always use 1 works for div2D?
https://mirror.codeforces.com/blog/entry/121718?#comment-1081111
Thanks
Nice explanation
Why do I suck at greedy problems like D?
Can someone explain the idea behind the problem A in div2
ans=Yes if all elements are same ans=No if no of unique elements>=3 in case of two distinct elements ans=Yes if min(frequency(elem 1),frequency(elem 2))=n/2 answer will be of form a b a b a b...
20 points away from CM...
Casting an ancient curse on Div. 2 problem C authors.
Hey, that's my line!
Honestly I think that C is not that bad, D however seems a bit troll: 2000 points for a problem where you can just connect the first node with any of the nodes that come after it (not even a real graph problem, just a tiny bit of math).
Sorry for stealing your line =)
My take on it is that figuring out why connecting everything to the first node in D is correct is much better than calculating all the correct indices on every iteration of C.
E2 was easy just read the constraints k<=10 bruh
What is this message? I was so scared thinking my fraud solutions were exposed and hacked manually by authors
Test cases are very weak for Div.1 B, my solution for B passed even on using int, should not this test case be available in pretests
screwed up so bad lol
same
1D is one of my favorite problems I've solved in a long time. I was working towards a totally different solution path when I realized that we could drop cycles to solve the problem in one move, at which point I spent several minutes thinking to myself about how cool that observation is before going to implement. Thanks to the authors!
https://mirror.codeforces.com/submissions/jiangbowen/contest/1889
Imagine solving C2 and getting FST on C1 lol
How? Codes and languages are same.
Time limit on C2 is 4 seconds but in C1 it's one second.
Then? Code submitted to C2 takes 982 ms, same code submitted to C1 takes 1000 ms.
lmao
don't know if it's luck or unluck
It was a very interesting round! Thanks to the Authors!
Guys, here is my submission for Div2 — E1 problem. It says TLE however, I can see there is output printed for the TLE testcase
MikeMirzayanov Cocoly1990 Imakf waaitg , this looks like a linear time-complexity difference. Can you guys help here. I think increasing time-limit in such problems will help ??
Also the below 2 submissions for the problem have same codes. But you can see that the problem have different TLE failing test-cases. Submission 1: https://mirror.codeforces.com/contest/1890/submission/230270545 Submission 2: https://mirror.codeforces.com/contest/1890/submission/230272906
Please help here guys /\
It Indeed Was A Great Contest :) :)
It was soo cool
Thanks for the nice Div2 round. I'm finally CMMMMMMMM.
is it too much to ask for another 6 points to become cyan :(
I hate Doremy
Thanks for such an amazing round! The tasks were truly enjoyable!
Finally, I became a master. Thank you for this interesting round!!!
problems are good, but i think it could be better to include the statement ("not necessarily adjacent") in div2 E . i thought that the days should be consecutive and fell into wrong idea.
In problem B, how is 1010101 a bad string ?? (test case 4)
t=1010101 is a good string. However s=101100 is not a good string, and you cannot make it a good string by inserting t (as often as you want). This is because s contains the substring 11 and even inserting t between those two 1s doesn't help as t both starts and ends with 1, i.e. you just end up again with the substring 11 after inserting t.
Wow my first time First Solve . Div2B