omg hi Codeforces!
ScarletS, flamestorm, fishy15, saarang, lookcook and I are glad to invite you to our Codeforces round, Codeforces Round 766 (Div. 2), which will be held on Jan/15/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.
We would like to thank:
Monogon senpai for excellent coordination of the contest.
MikeMirzayanov, for creating the amazing Codeforces and Polygon platforms!
KAN, for Russian translations!
dorijanlendvaj, errorgorn, PurpleCrayon, generic_placeholder_name, blue, phattd, atharv, tenth, snowysecret, StArChAn, namanbansal013, BRCode, nishuz, Rehan, Urvuk3, somerandomaltacc3034, tdpencil and bakekaga for testing the round, catching any mistakes and providing lots of valuable feedback! We tried to get a large range of testers with different coding experiences so that everybody enjoys the round.
You will have 2 hours to work on (and solve!) 6 problems. There will be at most five hundred interactive problems in the round. Make sure to read this blog and familiarize yourself with these types of problems before the round! You are highly encouraged to read all the problems ;).
Good luck, and see you on the scoreboard!
UPD1: Thanks to the testers ak2006 for making video editorials for most of the problems, and namanbansal013 who will be streaming solutions after the round!
UPD2: The score distribution is $$$500-1250-1250-1750-2000-2750$$$.
UPD3: The editorial is available here.
UPD4: Congrats to the winners!
Div. 2:
Div. 1 + 2:
We hope you enjoyed the round. Look forward to our next one!
As a problemsetter, each upvote on this comment equals one time I'll roast saarang
Next time tell me the comment I need to write in the announcement.
Good luck to everyone and I wish the experts become candidates
Wish for the Candidate Masters also. Imagine bullying all of them with one comment. :(
I want everyone to be legendary grandmasters:D Good luck to everyone in this contest.
As a tester, I was very useful!
looks like this one is skribbl bois round :catthink:
As a tester, I can guarantee this round will be very geniosity!!
$$$OMG$$$ ! What's the difference between $$$ indian $$$ $$$ round $$$ and other $$$rounds$$$ ?
No more than 500 interactive tasks are guaranteed in the Indian rounds))
As a tester, I believe the problems are great. Do make sure to read all the problems and I hope this contest turns out to be a good one for you :)
As a very big fan of both fishy15 and ScarletS, I know this contest will be as geniosity as they are.
The tags XD
An all colour tester list
At Most 500 hundred interactive problems
An all colour tester list
Cries in newbie intensify
Bruh your consistency, Great Job.
The only way I got ScarletS to do work for the contest
Why srk is in the tags :)
How can all problem setters be from different countries! Quite Amazing
Probably because discord
As a tester, I should probably think of something interesting to say :v
But I have no brain so give contrib pls :v
As a tester, each upvote on this comment equals one time I will save saarang from ScarletS's roasts. So if you like saarang do upvote. And also yeah, since we were paid to appreciate the contest, please do participate! The problems are quite luv.
As a tester, I now feel my work has not paid off accurately in terms of contribution.
As a tester, please participate in this contest and give me contribution.
As a tester, I'm here to claim my contribution.
ok boomer (gave conrtrib btw)
hello here to claim my contribution
lookcook ORZZZZZZZZZZZZ
Not sure if I'm allowed to disclose this information, but hey, there will be at most 6 interactive problems in this round. Don't tell anyone though, keep this sacred knowledge as it is your competitive advantage!
Just like the gender of your profile picture, I guess no-one knows for sure :P
But the gender shouldn't matter right? I thought all genders were equal.
.
bing chilling during the codeforces round
Finally i can see John Cena . :_:
Bing Chilling to you too
As a tester, hope you have a decent day.
There will be at least $$$-494$$$ non-interactive problems, as long as I did all the math correctly.
This round's editorial will probably be published earlier than #765
"There will be at most five hundred interactive problems in the round" why????????
501 interactive problems in one contest was deemed excessive.
have you encountered a contest in which all problems are interactive
https://codeforces.me/gym/315640
Really excited for this one.
fishy15 ORZ
Is every problem in this contest interactive ?
As the official video editorialist for most of the problems, the problems are very interesting and I will try my best to explain the solutions in an intuitive and simple manner. The videos will be available on my YouTube channel after the contest ends. Don't forget to like the videos and subscribe to the channel if you find them useful.
Thank you for preparing this wonderful contest!
Wishing good luck to everyone :)
is there any penalty for wrong submission
Ofc there will be as always -50 points for any wrong submission till accepted
Is 50 points deducted from overall score we got so far, before submitting the current problem or it is deducted from the scores assigned to the current problem we are trying to submit.
It is deducted from current problem you are trying to submit and if you manage to get that problem accepted during the contest it will also reflect in your overall score as well
Score Distribution ?
We do a little trolling.
I have done with bit manipulation . But I can't solve the questions related to it. Even easy questions. Even after practicing all A ans B questions. What should I do?
Practice it by tag in codeforces.... After practice 50-60 questions (increase rating of questions as you feel confident in a particular rating let 1200 then increase it to 1300). You will be able to solve in contest too...
Hi
Can anyone suggest me something to reach expert
Stop thinking about reaching expert :)
Instead focus on solving problems harder than your current rating and solving problems of your current rating fast.
score distribution is interesting ...
There will be at most five hundred interactive problems in the round, which means all problems might be interactive. That's interesting!
Hope people like me who gained negative rating changes in the last round can win back.
Wish everyone good luck and high rating!
Wow, the round has official video editorials. I appreciate the effort from authors and testers.
Best of luck guys ✌️ See you after the contest.
How to become a tester?
This has been asked and answered too many times
Are contests rated if you don't submit any problem after registering. I couldn't submit anything because of network issues so I'm wondering if I should participate at all.
No if you don't submit any solutions you don't loose ratings or count as participant
Okay. Thanks mate.
Absolutely love the problem statement of E, it's from one of my favorite movies!
due to some complicated relationship history that we couldn't fit into the statement!
this. thankyou for not writing unnecessary statements which nobody cares about
it made me laugh :D
This round was good one
If i get fst in Problem D, I will die.
too easy C, D but hard B.
Bruh...what the hell wwas B ???....I was tired of it
Same. was tired of it but at last noticed the trick. Just find the distance of the furthest cell for every cell and sort it
After a point I just didn't cared about WA and facepalmed the hand out of my face after figuring out that corners are the place she will always prefer :'(
The way you said that sounds creepy...lol
E is a literal bruteforce right? Just need to calculate for layers ascending for each value in that layer/floor? I got TLE 8 and suspect it's just because I didn't map the coordinates in graph to some integer value, but rather stuck with maps :P
Your solution looks mostly correct on first glance, but you can solve this problem without needing maps and implementation is fairly clean.
What did you change to prevent getting TLE in test 8? My submission looks $$$nlog(n)$$$. Not sure why I am getting TLE in test 8.
I removed repeating values, actually it was Len who did it. Just compare my last contest submission and last submission.
Wow, this trick works magically. But why, even if I don't do it, it still should be order nlog(n).
Suppose all ladders share an end point $$$v$$$. If you don't exclude the repeating values, you end up traversing edges of $$$v$$$ $$$k$$$ times. So the total runtime ends up being $$$k^2$$$ instead.
yeah got it. Never mind
I truly crave the day in which I will see actually interesting div2 starter problems which are not based solely on one basic observation and a lot of cringy implementation. This day will obviously never come, because the current trend for coordinators is, apparently, to review problems the harder they are. Whatever, at least D and E had some really cute ideas.
It's funny how you say that because I found D and E quite boring. However, it does not mean that they are bad problems, I just saw similar ideas before. I think that you will continue finding A-C boring, much like I find A-E boring, because they are not in your interesting interval (c) Um_nik
Problem D: Link
I can't be the only one who misread problem A as to color the row and column and not the cell intially.
https://imgur.com/a/KyW9gkN
Literally spent 7-8 mins after that Yes answer to my question , thinking i need to colour both row & column, only to figure out.. that i was correct all along. I still don't understand how it can be cell(s) [Yes.] then. :(
I think this is a very poorly formulated question, hence the misunderstanding. Like, I don't understand your English at all, and setters were probably confused as well.
How to solve E? I feel like it is some sort of convex hull stuff and I'd be kind of sad if it was something much simpler...
If I'm correct (TLE test 8), there are at most 2K+M vertices you need to store the value for in order to solve the problem. Simply go layer by layer (from bottom to the top) and calculate the minimum path for every vertex present in the current layer (it is either reachable by using ladders or from some of the reachable 'neighbors'). So it's just a simple DP on each layer with the complexity of O(2K+M) but there's an extra log factor needed to compress the vertices (integer pairs) into some integer form.
Won't it make the solution O(n*(k+m))? If so, both n and k,m can go upto 10^5, and would cause TLE.
No, because you just consider rooms that belong to some ladder and the first floor completely. There are at most 2*K ladder vertices and M floor ones, so it ends up being just (2*K+M).
Why do we need all floor vertices?? 2*k ladder vertices and (1,1) should work??
Yes floor vertices are unnecessary, my implementation for this uses the 2k ladder endpoints, (1, 1), and (n, m).
Because some ladders may start from vertices on floor other than (1,1). I guess your implementation may be different if it doesn't rely on this fact.
Hmmm it's true that there are O(k) nodes (or something like that), but is it really that simple as visiting each node's neighbours? I thought of this case, where algorithms similar to yours would have at least O(k^2) complexity: here. Each green line is a ladder and there would be O(k) ladders with a[i] equal to some level l and another O(k) ladders with c[i] equal to some l.
No it's still O(n+k) as you visit every vertex on each floor exactly once. It's never optimal to same segment on a floor more than once, so you can do DP on prefix and suffix. Here's my submission:
https://codeforces.me/contest/1627/submission/142876952
I think your solutions gets TLE because there might be multiple ladders starting from same point, and your code considers everything multiple times resulting in O(k^2) complexity (Only leaving unique will fix this).
I traverse each vertex three times per layer, so I don't think it's the issue, I've posted the code above so you can check it.
I meant these lines, for example if all ladders will start from (1, n) and go to (n, 1), (n, 2), ..., (n, n), these for loops will work in n^2 (Or maybe I didn't understand it fully).
I traverse every ladder exactly once, so I don't know why that should be an issue. And it's not some sort of recursive function, so I still see no problem with it.
fixed:)
Thanks so much, I guess I didn't understand your initial comment. It's a dumb mistake on my end though :(
let's say you calculated all the minimum values at which you can end up in some points after climbind some stairs until level X (i.e. you calculated $$$minhit$$$ for every cell $$$c[i] <= X$$$), and now you want to calculate where these values can go from this level upwards (using some ladders on level $$$X$$$). Then, we can observe that if we were to plot $$$min(abs(i — d[i]) * x[i] + minhit[i]$$$, for every $$$i$$$ with $$$c[i] = K$$$), then every $$$i$$$ (with $$$c[i] = X$$$) is assigned EXACTLY one segment on the number line (where it is a maximum value).
unmaxxed
maxxed
After sorting each of these points by $$$d[i]$$$, we can do some stack like thinking to determine which values will actually be visible (and we by doing so the points will then be conveniently sorted again by $$$d[i]$$$). Then, we could check for each stair that begins on that level what is the cell from which it derives it's minimum (with two pointer logic).
Time complexity: O(KlogK + N) (more or less)
Great Contest. Balanced. Loved problem D. Thankyou!
code
my approach for C:
please point out what I did wrong
you are specially for checking size ==3,check for size >2
I am checking whether degree of any node becomes 3 while taking input itself ,so it should not be a problem right. Even if in the end degree of node is >3 flag would have become false
You not clearing graph if flag become false, so next testcase become incorrect
Thanks man... I kept staring for 1.5 hours but was not able to figure that out
Can anyone explain logic behind problem C? my idea was if there exist any node connected with more than 2 edges then answer is -1 otherwise we can use 2 and 5 to assign weights in appropriate manner. i am getting WA on pretest 2. Can anyone help??
This is a correct logic as far as I understand it.
If tree is a line then you simply assign 2, 5, 2, 5 ...
If it's not a line it's impossible.
first to be the first AC in D :) cool : L
How can you D that quickly, and then fail on B? (No offence, but for nearly all of us B<<< D)
maybe I solve math problem better than some tricky problem :L
For me D == tricky :D
But congratulations btw. Really strong maths skills
Multisource bfs in B ?
We can simply calculate maximum distance for every vertex ...and then store it in a multiset..
Oh stupid me! My intention was to calculate the same. Only if I spoke "calculate maximum distance for every vertex" to myself in simple english, I would avoid have saved my 10-12 minutes
oof that's such a cool idea. I'm so annoyed for writing BFS xD
i used bfs in my solution , i couldn't think of any greedy idea during the contest
here it is 142893044
Interesting and balanced problems. Very nice round!
WoW, I fucked myself in this contest.
Same here, though the problems were noice, especially B with the manhattan distance observation
I was tricked into submitting late by mean testcases in D and E, bad experience.
First I was annoyed by lengthy problem statements, then by myself because not commited but solved A to E anyway, then submitted and beeing annoyed because D and E where wrong.
The problem statements were straight to the point.
Not Bad
Cool contest. How to solve E? I thought about Dijkstra's, but that seems too slow. I'm not sure if plain DP with memoization would work (and only visiting states in which we have an in-ladder or out-ladder)?
Yep, only visit the "important" rooms in the building + dp works. Dijkstra is more annoying to do because of the negative weight edges but it can be done if you do it right.
.
My stupid ass thought for a whole 15 min that 1 is a prime number and was trying to figure out why assigning 1 to each edge in C would not work....FML
Notforces!
What's wrong with my submission 142866521 ? I see similar logic in others submissions, there must be an implementation problem somewhere, but i cant find it.
The start of your BFS function always starts at a weight of 3, so if vertex 1 is not a leaf, then both of its adjacent edges will have a weight of 3 and thus the path containing both those edges will have weight 6. You can fix this by either starting each edge with different weights or finding a leaf and BFSing from there
wow very fast editorial! nice
anyone else got mle in question 3 in system test?
Problem D is equal to this leetcode1819.(The problem is in Chinese)
link_english
Lol I even have a solution there, but I can't remember doing that :(
Stupid Question, Ignore. :facepalm:
dijkstra doesn't work for negative edges and is intended to TLE.
Hello fellow same-surname, testcase 4 was an anti-Dijkstra testcase (regular Dijkstra doesn't work with negative edges).
Thanks for your reply. Can you elaborate what the test case was. I do understand Djikstra won't work with negative edges but still find it hard to visualise in this instance.
Here is a simple sketch I made of 1 layer of the counterexample.
Specifically, what is happening here is that we will processes the lower left corner with a distance of 0. After this, the next shortest is the upper left corner with a distance of -2, and then the upper right corner with a distance of 1. Finally, the lower right corner will be processed with a distance of $$$x$$$.
There are 2 possibilities for implementations of Dijkstra that happen now. In the first one, a node is processed only if it is not marked as visited in some array. In this case, the upper right corner will have a distance of 1 marked even though the correct distance is 0.
In another implementation of Dijkstra, a node is processed when it is at the top of the priority queue and the distance in the queue matches the distance stored in some array. In this case, the node would be processed once at a distance of 1 and then again at a distance of 0. If we make $$$x$$$ large enough and chain multiple of these layers together, then each layer will have to be processed multiple times which leads to an exponential solution.
To add to this, confusedsouls, the testcase is basically $$$\frac{k}{2} = 5 \cdot 10^4$$$ of these "loops".
Nvm
Is there an actual right solution for E using graphs? I passed pretests with Bellman-Ford(Dijkstra doesn't work well with negative edge weights), but I got FST(here's my solution: Goodbye Candidate Master)
Dijkstra's algorithm works if you construct a DAG and process the states in the order of (row, cost); because the cost in the same row only increases (142887300). Though if you have a DAG, it's easier (and faster) to find the longest path in a DAG using DP (142881726).
To construct a DAG, create two nodes for each cell; the first one can go up or to the left, and the second one can go up or to the right.
Sounds interesting, thank you!
What are the odds that you rewatch a Bollywood classic in the evening and open a problem statement and see that is about a scene that you were watching literally minutes ago. Good choice of story :)
I wasted around ~5 mins remembering the last scene when SRK jumps after reading that line.
after how much time our rating will be changed?
At most right before the next contest.
ok, thank you
As a contestant, I want to clear my contribution
Can someone please point out, why I am getting TLE on test 8 in problem E? I am going layer by layer and using prefix and suffix max to get the answer of a layer. According to me, this is not more than roughly $$$O(nlog(n))$$$. link to 142887592 .
There are repeated rooms on floors, so you might be using multiple ladders from the same room at a floor, multiple number of times. I had the same error. Remove Duplicates from your vectors before taking pref_max suf_max.
Fun round! But for 1627F - Not Splitting, how did that "subarray" vs "subsequence" mix-up manage to get through all that testing and coordination?
I know the statement gave a definition of "subarray" (which matches the conventional definition of "subsequence", not "subarray"), so technically the statement was correct, but those definitions should be skippable by experienced contestants. Problems shouldn't re-define common terms.
Sorry, the statement said "subsequence" during testing and coordination but during the translation (which happened a few hours before the contest), a translator decided to update the English statement to say subarray instead of subsequence and we didn't notice. Hopefully this didn't affect anyone's performance too much (and hopefully you could also tell what we meant by the image and the first sample).
Ah, I see. I was solving the subarray version until I saw the clarification! But it still had a few observations in common.
Maybe it should be a policy that all changes to statements notify authors with a diff (or maybe even require authors' approval to be accepted).
Very nice contest, but I feel like B and D should have been swapped.
Thank you very much for this nice roud :))
Here are my thoughts:
It was a nice A, not too hard but not brainless (you still need to notice something to solve it)
Some people found it too hard ? I found it ok for a B, the story was fun and the problem is interesting
I liked it too! Fun problem that asks for something that looks impossible but is actually not hard.
Systests are weak. Apparently some geeks for geeks article could destroy the problem too so idk what to think. It is still an interesting problem though
Well, I found E really easy for a div2 E. The problem is cool but it felt like an educative problem and not a div2 (the same kind of dp ideas can be found in the atcoder dp contest + in this amazing blog). So maybe it was too standard ?
idk I didn't read it
But to be fair, the round was really good and I enjoyed it a lot! I hope to see more of your rounds in the future :D
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
When I checked your profile and saw : Headquarters — Rating 1772, I thought you were using magic to become headquarters ...
-_-
I think my D is hackable.
For each X, I am not considering the gcd of all the multiples of X. Instead, I am just considering the gcd of the smallest multiple of X with all other multiples of X and checking if there is any instance where gcd == X.
Do I loose my rating if somebody hacks my solution now? xD
You are iterating backwards and marking the elements as present while you move, so it's still correct as the newly added elements are being considered in the further steps. We can prove that taking smallest multiple as the first element always works.
This gives me a sigh of relief. I was also wondering if the way I have implemented is actually making it work. Lemme try to prove it formally. Thanks for reassuring.
I thought the round is good(Even if I just solved 3 problems during contest), but D and E is very fun.
Thank you for giving us a perfect contest. Looking forward to your future contests.
E had me like "Helikopter Helikopter".