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, polarity-, atharv, epicxtroll, dbsic211, StArChAn, namanbansal013, BRCode, nishuz, Rehan, Urvuk3, sid., 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))

SpoilerAs 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.

Things to notice ;)The tags XD

An all colour tester list

At Most500 hundred interactive problemsAn all colour tester listCries in newbie intensifyBruh your consistency, Great Job.

The only way I got ScarletS to do work for the contest

SpoilerThere are so many codeforces rounds these days! Thanks to the problem setters and hope every good luck.

Why srk is in the tags :)

How can all problem setters be from different countries! Quite Amazing

Probably because discord

Coz they belong to the same country.

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 6interactive 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.

Alright, i'll upvote.

[deleted]

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.

May the force be with us and that we solve all problems)

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.cc/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

Siiuuuuuuu!

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

Oh, Thanks for reply

what does five hundred interactive problem means?

Good luck every body

memeScore 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 problemsin the round, which means all problems might be interactive. That's interesting!The Pigeonhole principle, I see

I guess, the problem B is harder than usual ... may be , it is interactive ...

Hope people like me who gained negative rating changes in the last round can win back.

Wish everyone good luck and high rating!

saarang is a very good problemsetter. For the past 13 years, he trained under the master(not on codeforces) GoldFish(me) on how to write problems. It's showtime saarang, you can do it

I wish you all to get repeated TLE's and passed pretest but gets failed in system testing may your code gets skipped and you get a minimum of -100. all the worst X). Looks like mu curse worked now go and work hard the rating will go down or up cause of no not by my words.

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

Why is codeforces not working on wifi but working on mobile data . Was not able to participate in this contest due to this reason .

DNS issue most probably

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

Singles be like: Let's move on to problem B.

This round was good one

If i get fst in Problem D, I will die.

BFSForces :D

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

wtf !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I am worthless...

oh it's faster than bfs, wish i knew it sooner

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

please any hint to solve D

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_nikProblem D: Link

CodeI 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.cc/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

EXACTLYone segment on the number line (where it is a maximum value).Drawingunmaxxed

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.

oh thanks! i think there must be something to do with my implementation, let me revisit it.

Seems like problem setters of this round are die hard fans of srk.

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

Can you please explain your approach pls ?

Ok Ok i got that...amazing approach.

Multisource bfs in B ?

Not needed.

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

Amazing

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.

[deleted]

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

Jesus ... must have cost a lot of points.

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

Oh, yeah, I got it. Thank you very much! :)

nice problem B, so lucky i have been practicing BFS recently :))

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:

AIt was a nice A, not too hard but not brainless (you still need to notice something to solve it)

BSome people found it too hard ? I found it ok for a B, the story was fun and the problem is interesting

CI liked it too! Fun problem that asks for something that looks impossible but is actually not hard.

DSystests 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

EWell, 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 ?

Fidk 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.

Problem C is easier than B lmao.

E had me like "Helikopter Helikopter".