Hi Codeforces!
I am pleased to invite you to Codeforces Round #793 (Div. 2), which will take place on 22.05.2022 17:35 (Московское время). You will be given 6 problems and 2 hours to solve them.
The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.
All problems in this round were prepared by me and rivalq. We have worked on this round for a long time and hope you find every problem interesting.
I would like to thank:
- antontrygubO_o for marvellous coordination of the round.
- errorgorn, kclee2172, AmShZ, nvmdava, TheScrasse, aryanc403, koderkushy, PurpleCrayon, nor, AlperenT, towrist, ExplodingFreeze, conquered, naresh0839, The_Hawkeye, Siuuuuu_7, GuptaSir, sp005, obliviousz, davidgarg20, ak2006, and the_hyp0cr1t3 for testing this round and giving really valuable feedback.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms!
- You for participating and upvoting.
- NEAR for supporting this round, details can be found in this post.
Score Distribution:
750 – 1000 – 1500 – 2000 – 2500 – 2750
Good luck and have fun! See you in the standings. Make sure to read the statements very carefully.
Thanks to ak2006, video editorials for some of the problems will be available on his channel after the round.
Congratulations to winners!!
Global Top 5:
Official Top 5:
Special mention to AwakeAnay for the only Indian to AK the round!
UPD 1: Links to video editorials of Problem B and Problem C
UPD 2: Editorial for problems A-D is here.
UPD 3: Editorial for E is added.
UPD 4: Editorial for F is added.
AmShZ orz, The captain of Iranian testers
CoderAnshu supremacy!
I downvoted you. Then, your contribution was raised by 1
Orz
Good luck to everyone!
As a true cyan (tester), I would recommend you to try the next problem if you get stuck ( '◡' )
ok, vro
Mil to gye itne saare upvotes..... XD koderkushy
As a tester, the problems are fairly interesting and quite challenging.
Enjoy my upvote and Conference league next season ;-)
unlike your idol's club
As a tester, I can confirm that the problems are high-quality and interesting, and cover a good range of topics, and would recommend participating in this contest.
Hopefully the pretests aren't as sad as the last contest
Hopefully
As a tester, I really did test the round this time.
Did you?
I hope it will be great #793 div.2
CoderAnshu lord supremacy. :)
A contest by Indian Coder after such a long time!!! Very Excited!! Hoping that this contest turns out to be the best in recent times.
How can you forget #782 div2 by my friend Newtech66 just a month ago?
Ohh yes! Now indian are making some interesting contest. And they do all this with hectic college schedule in India.(-_-)
The best duos of India. (CoderAnshu and rivalq) supremacy
As a problem setter, I would really like all of you to participate.
i hope the round will be a bit better than previous
Which previous?
i guess its — "Codeforces Round #792 (Div. 1 + Div. 2)" ...not your previous
you're right
This you should judge after the contest itself.
I hope this toxic stream will stop someday
For the last two contests I have been fsting on problem D due to stupid implementation mistakes. Hopefully this contest I will be able to break the streak.(Hopefully by solving problem D )
Edit: Broke the streak by not solving D this time.:clownglasses:
Удачи и приятного время провождения! До встречи в турнирной таблице.
As a tester, I get to write a comment for some contribution. hue hue hue.
Notice in the last line
Make sure to read the statements very carefully.
Ohh... I haven't read that.
All the best Everyone !
Hopefully the "best of 2022" which were replaced in the previous round will be seen here.
Lolll
I hope I solve about 3 problems and become a specialist !!
Good luck for all participant!
All the best for all participants
As not a tester,give me contribution!
No offense though
Everything is so sorted, just look at the testers list! Efforts put everywhere.
Much Awaited Contest
of cource! it seems like very very very great contest and also much awaited.
I will be taking part in this contest.. I am getting back after nearly 1 year.. wish me good luck bois!!
Btw, 793 is a semiprime number. Hope that means at least half of problems will be great!
Good luck!
Best of luck to everyone!!
congrats for rank 7 in kickstart!
Thanks!
I believe in CoderAnshu & rivalq supremacy!
SwapOnPermutationForces.
This justifies your WA on B.
Well just because I didn't initialize the answer big enough :(
Yet another unbalanced round... #SpeedForcesOP
Wow!! You solved none. It's highly unbalanced and speedforces, sorry.
Don't you know anything about alt accounts?
I know, why not comment from it directly?
probably coz i wanna be anonymous '◡'
Or you are coward.
well i knew i'm gonna have -ve contribution so why not write from alt.
Now I can finally sit and watch my rank fall due to so many wrong submissions.
Yeah, me too, thought I'm a master after I became a specialist LOL
Same here lol
me too
Problems are tricy ig.
Would anyone please explain why the output of problem C is 7 for this input?
1
13
1 2 3 5 6 7 7 8 8 9 9 10 10
Thanks.
Put 1 in the middle.
10 9 8 7 3 2 1 5 6 7 8 9 10
Array: 10 9 8 7 1 5 3 6 2 7 8 9 10
10 9 8 7 1 5 3 6 2 7 8 9 10
In reverse: 10 9 8 7 2 6 3 5 1 7 8 9 10
count the numbers that have frequency greater than 2 (lets say 'd'). and those occurring single time will be n-d (lets say 's'). and answer will be d+ (s+1)/2;
FML, I think I have the solution for E. Rip. I think it involves traversing each tree in the forest and doing a tree DP.
Guys!! Hope you liked the round. Please share your feedback on every problem. I will be really thankful.
Because i solved till C, it was very great round!)
unbalanced and stupid problems
Not fair. Frankly speaking, it happens not so often, but A was pretty. As for B, i am not a pro of bitwise operations, but even i didn't found this one too hard. And C... some stupid mistakes, but after about 30 min i did found the right solution by painting samples into notepad, so i do not think that this round was disbalanced
Eeeew pupil, ofc it won't be unbalanced for you.
What, how did ya call me????????? I am a specialist now, baby!!!!!!!!!!!!!!!!!!!
I was able to solve till $$$C$$$, and it felt okay, I had almost got $$$D$$$, it was a nice constructive problem, and I don't know why I was getting WA on test 2.
It would be really helpful if anyone can explain what does this means ? I got this on $$$D$$$
My submission: https://codeforces.cc/contest/1682/submission/158075759
I guess there is a problem in amount of your edges, the compiler is trying to say you have to print another edge, but your code started to answer on the next test case, so you probably don't have enough edges printed. Sorry if I'm wrong
Yeah, you were right, thanks for your help, I got one test case failing "100100100100", and now it got accepted :)
It's a very sad thing that I wasn't able to find this basic test case during the contest..
You are welcome:)
strong pretests for most of the problems and very clarifying statements .thanks for the round.
Questions are very interesting. From B to D all of them involved a decent amount of thinking. Loved the round.
I got TLE for using unordered_map instead of map in C... Bad contest :(
me too
sorry @CoderAnshu, I was upvoting but my mouse sucks, I accidentally clicked on downvote, I am sorry for it. hope you don't mind it
LinearForces :-)
C felt kinda tricky.
Why does the number of solvers of problem C go so high?
I solve it by luck.
The contest wasn't balanced. Problem A and B were too easy and problem C was tricky.
I can solve D quickly, but I can't handle A,B,C.It's weird.
how to solve D?
god damn stupid greedy thought always messes up my first three problems. Well it sometimes works, but the moments it doesn't work really affect my mind.
amazing samples guys
True. It saved me a lot of time
What's the solution to D?
I create egdes as a circle, find a edge to remove, then for each two node (x, y) I need to change the degree, I remove the edge of (y, y + 1) and add the edge (x, y + 1) 158057894
amazing simple solution! I have done a garbage code, by using link list and removing subgraphs of size 3 from boundary. In the end size 3 or 4 graph remains which is handled separately.
If number of $$$1$$$'s is odd or there are no $$$1$$$'s at all the answer is "no", because the sum of degrees should be even (each edge is considered in $$$2$$$ degrees) and we should have at least $$$2$$$ leaves.
To construct a solution, if the string is all $$$1$$$'s, just choose anyone of them to be the root and connect it to all the other nodes.
Otherwise, connect each $$$0$$$ to the node before it ($$$0$$$ at node $$$1$$$ is connected to node $$$n$$$). Now we have chains starting with $$$1$$$ and ending with $$$0$$$ (call such endpoints "tails"). To make all the nodes in these chains valid, we have to connect odd number of edges to the tails.
To do so, if all the $$$1$$$'s are consumed in the chains, just connect the tail of any chain to the tails of all the other chains. Otherwise, choose any unconsumed $$$1$$$ and connect it to all the chain tails and to any other unconsumed $$$1$$$.
Such construction guarantees that no intersections occur, as we first add some edges between adjacent nodes (can't be intersected) and at the end we choose only one node and connect it to some other nodes.
Submission
can anyone explain that how to solce c :*
I just binary searched the answer. You can in linear time check whether an answer X is possible. Although I have to say it was tricky to implement, two WA submissions and like 30 minutes debugging for edge cases
All numbers that appeared two or more times can appear in LIS of both original and reversed array. Then we distribute all numbers that appeared only once evenly in LIS of original array and reversed array. Note that we can share one number in both LISs, so the answer is
x + (y + 1) / 2where x is the number of numbers that appeared two or more times, and y is number of numbers that appeared once.I just count how many number appears 2 times or more as m2, 1 time as m1 and the answer is m2 + (m1 + 1) / 2.
Example: 2 2 3 4 5 6 6 -> 2 3 6 5 6 4 2
Spent near one hour on E and then realized I made the wrong observation. I think A-E are all great problems.
Those who solved problem C with unordered_map, depending on the compiler version, fall on test 26 or 28. Test 28 is a my hack test :)
Thanks
lol
I think Problem B was slightly confusing in my opinion.I am not able to understand B problem clearly.
how to solve E?
Build a graph with $$$(x_i, y_i)$$$ as edges. For each i, find path from $$$i$$$ to $$$a_i$$$. A pair $$$(x, y)$$$ can be swapped if the edge $$$(x, y)$$$ is the end of two paths. Edit: add code 158085317
By "...the end pf two paths" do you mean the path where all of it's subtree nodes are located in their correct position?
Sorry I don't get what you mean but I just realized that it may be beneficial to name an edge with its index rather than its two end points since vertices are moving. Let's say the path from $$$i$$$ to $$$a_i$$$ consists of edge $$$e_{b_1}, e_{b_2}, \dots, e_{b_n}$$$, and path from $$$j$$$ to $$$a_j$$$ consists of edge $$$e_{c_1}, e_{c_2}, \dots, e_{c_m}$$$. If $$$e_{b_n} = e_{c_m}$$$, we can swap that edge. Then remove that edge from the end of two two paths and look for another edge that is the end of some two paths.
I see. But how do you do it in linear time for checking i and j?
Great round! Especially enjoyed E and F.
Thanks!!
orz
i literally did c in 8 minutes by using same approach as in editorial but was not confident enough and waited for it to fail main tests. but it passed :) edit: people made it hard just because it is problem "C". conclusion: don't judge a book by its cover
that's so true, i suppose C can be easier than B for those who have no idea what bitwise is
Great problems, although didn’t solve E.
Why unordered map gives tle on codeforces?
Hash collision resulting in O(n) per access?
is CF getting harder or people are getting so much better? Feels like an 1800 rate problem a few months ago would be just 1600 now. So many solved C
Or There are many cheaters.
It's actually case3: The question was easy
bullshit pretest for C
Why would you use an unordered map when it is quite easy to exploit the hash collisions for it lol
Congratulations!! You've reached the time which every coder reaches where he switches from hash map to map
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Here is some feedback, loved the round overall! I think BCD in particular are excellent.
I didn't really like this task. I think the solution is obvious, but takes some time to prove. Here's my proof (which avoids odd/even casework! but is very "analogy-dependent"): imagine that each letter is a colored block arranged in a line. The string being a palindrome implies that placing a mirror at the midpoint of the line is indistinguishable from the original arrangement. WLOG, suppose we remove a block not in the middle segment of same-colored blocks that is to the right of the mirror. The mirror should be moved half a block's length to the left. Now the segment of same-colored blocks to the left of the mirror is strictly smaller than the segment of same-colored blocks to the right of the mirror, which means that the resulting string cannot be a palindrome.
I think coming up with this proof is much harder than coming up with the solution to the problem (there is also the less-clever parity casework proof, but I find it cancerous to think about). In general, I don't like it when there is a large difficulty gap in proof difficulty and problem difficulty. Especially for problem A, where I feel like it should be solved instantly.
Very good problem! Don't have much to say, I think it's very cute.
Another very good problem! I like the fact that the samples don't include a case where the two subsequences must share one element in common, which penalizes proof by AC. I think the proof for this is quite long, but it flows so naturally and has many parts that can be done fast with intuition, so the difficulty of finding it is good. Extremely fun to think about overall.
Also don't have much to say here, I think the construction is extremely nice and beautiful.
I enjoyed thinking about this. I think the solution I submitted is almost correct, but when doing a swap, I only check if the parent has the correct value needed to fill the "hole" in the subtree. Was panic-implementing at the end hoping I could submit in time though, so will have to think about it more.
Thanks a lot for the feedback!! Glad you liked the problems.
Is it just me or do these submissions look so similar? - https://codeforces.com/contest/1682/submission/158041174 - https://codeforces.com/contest/1682/submission/158063005 - https://codeforces.com/contest/1682/submission/158043928 - https://codeforces.com/contest/1682/submission/158045408
158034396
why TLE?
Because you use unordered_map
Doesn't it satisfy time constraints(nlogn)? I have used it many times. What else should we use then here? (sorting would have also taken nlogn)
unordered_map for int can degenerate to O(n) for lookup/insert (map is guaranteed O(log n)).
But yes, sorting and then linear pass will work too.
you can read this blog for efficient using of unordered_map
Nice round, loved the problems.
Why the guy's submission is so werid? https://codeforces.com/contest/1682/submission/158020409
update: also this guy's submission: https://codeforces.com/contest/1682/submission/158055059
I think in the past several months, they have found a way to trick the CF cheat detectors. That's why there are so many ACs for easy to medium problems now.
such a poor round wasted 2 hours
A should have been little easier :( I wasted more than 20 mins thinking there should be easier solution for A by having right one in my mind. Lesson learnt: Solve what comes to your mind first for A atleast
learnt this lesson long before
nope, it's not reflected in todays contest!
In 3rd Problem, If the array a = [1,2,2] , Then according to codeforces, correct answer is 2. Can anyone explain how is it possible. My Claim : Answer should be 1 and not 2 since it is asked "strictly increasing".
Thanks in Advance !!!
2 1 2
What about array [6,5,3,3,6]?
answer should be 3: we can rearrange array like: 6 3 5 3 6
3 6 5 6 3
a = 2 1 2 a' = 2 1 2 (reversed)
second and third element form LIS edit: Boy but you got it in the Contest? Hopefully it's only due to luck
Hi,I also have similar doubt, we also need to check that the singleton element which we are considering to add in both the sequence should be either minimum or the maximum element otherwise we won't be able to add it in both the sequences.
a = 1 3 2 3 1 (LIS)
a = 1 3 2 3 1 (LDS)
2 is neither max nor min
I don´t understand the problem B, why is {0,2,1} = 0?
swaping 1 and 2 is sufficient ans = 1&2 = 0
Thanks for super fast editorial.
Good Round, I loved thinking about problem C, it was simple but tricky. going to remember it always. A great Round from an Indian problem setter.
for problem :c
test case :
5
1 1 2 3 3
the given answer is 3,could some one please explain how it can be 3.
i am getting answer as 2
3 1 2 1 3 in this order...
in this case answer will be 2 lis=2 (12 or 13) rlis=2(12 or 13) minimum of them will be 2 again
I think you got a misconception about subsequence. It doesn't have to be contiguous.
sorry my mistake , i have considered only continues subsequence
3 2 1 2 3
there is only one 2
a = 1 3 2 3 1
a' = 1 3 2 3 1
got it thank you i have considered only conitnueous subsequence
Same I made so many WAs on this case lol
I have some doubt in problem C.
For this test case
14
150482826 299981842 846268930 299981842 16711396 299981842 160038184 87399809 36731648 410799926 150482826 16711396 410799926 355178268
answer is 7, but my solution is outputting 6, may I know the problem here?
(My approach is to build a sequence greedily by sorting the array and then taking minimum of them and then placing rest of the numbers on left and right of that minimum found (leftMost after sorting) (Counting them just), so that I get a strictly increasing sequence even if reverse, numbers that come twice are put in either of the sides.)
Then I output the final answer as min(leftSum, rightSum) + 1
I am counting these leftSum and rightSum in the above approach.
You are almost correct, but instead of always taking the minimum as the one being used by both the "leftSum" and the "rightSum", you can choose any of the number to be shared by both sequence. An example of this is "5 3 4 5 3" where both the left sequence and the right sequence used "4" in the LIS. Hope this helps :)
Thanks for this wonderful round!
I am finally a CM.
in problem B, with the input:
1
8
0 1 2 7 4 5 3 6
it seems like the answer is not correct, if im wrong, pls point out my mistakes.
in problem statement it is clearly mentioned that value of X will always exist so this kind of test case not possible.
It's Indian territory. love IIT CoderAnshu
In problem D:
for input of: 1 4 1100
my submission: [submission:https://codeforces.com/contest/1682/submission/158117585] gives output of: YES 3 4 1 3 2 4 but the accepted answer is: YES 2 3 3 4 4 1
but I think my printed solution should also get accepted.. can someone please help me with this one. Thanks in Adv!!
(1, 3) and (2, 4) intersect internally in the circle.
Please help me
My solution for problem E got RTE in test 8, but I don't know why; please tell me why
Thank you!
My submission: https://codeforces.com/contest/1682/submission/158149795