### manish.17's blog

By manish.17, 5 days ago,

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:

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!

• +622

 » 5 days ago, # |   +269 As a problemsetter, each upvote on this comment equals one time I'll roast saarang
•  » » 4 days ago, # ^ |   +34 Next time tell me the comment I need to write in the announcement.
•  » » » 4 days ago, # ^ |   0 Good luck to everyone and I wish the experts become candidates
•  » » » » 4 days ago, # ^ |   0 Wish for the Candidate Masters also. Imagine bullying all of them with one comment. :(
•  » » » » » 4 days ago, # ^ |   +4 I want everyone to be legendary grandmasters:D Good luck to everyone in this contest.
 » 5 days ago, # |   +83 As a tester, I was very useful!
 » 5 days ago, # |   +44 looks like this one is skribbl bois round :catthink:
 » 5 days ago, # |   +61 As a tester, I can guarantee this round will be very geniosity!!
 » 5 days ago, # |   -10 $OMG$ ! What's the difference between $indian$ $round$ and other $rounds$ ?
•  » » 5 days ago, # ^ |   +29 No more than 500 interactive tasks are guaranteed in the Indian rounds))
•  » » 4 days ago, # ^ | ← Rev. 3 →   +1 Spoiler ... Indian rounds are sometimes created by Indian people
 » 5 days ago, # | ← Rev. 2 →   +37 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 :)
 » 5 days ago, # |   +65 As a very big fan of both fishy15 and ScarletS, I know this contest will be as geniosity as they are.
 » 5 days ago, # |   +21 Things to notice ;)The tags XD An all colour tester list At Most 500 hundred interactive problems
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 An all colour tester listCries in newbie intensify
•  » » 4 days ago, # ^ |   +4 Bruh your consistency, Great Job.
 » 5 days ago, # | ← Rev. 2 →   +136 The only way I got ScarletS to do work for the contest Spoiler
 » 5 days ago, # |   0 There are so many codeforces rounds these days! Thanks to the problem setters and hope every good luck.
 » 5 days ago, # |   +99
 » 5 days ago, # |   +32 Why srk is in the tags :)
 » 5 days ago, # |   +29 How can all problem setters be from different countries! Quite Amazing
•  » » 4 days ago, # ^ |   0 Probably because discord
•  » » 3 days ago, # ^ |   0 Coz they belong to the same country.
 » 5 days ago, # |   +61 As a tester, I should probably think of something interesting to say :vBut I have no brain so give contrib pls :v
 » 5 days ago, # |   +32 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.
•  » » 4 days ago, # ^ |   -29 As a tester, I now feel my work has not paid off accurately in terms of contribution.
 » 5 days ago, # |   +34 As a tester, please participate in this contest and give me contribution.
 » 4 days ago, # |   +36 As a tester, I'm here to claim my contribution.
•  » » 4 days ago, # ^ | ← Rev. 2 →   -28 ok boomer (gave conrtrib btw)
•  » » 3 days ago, # ^ | ← Rev. 2 →   +32 hello here to claim my contribution
 » 4 days ago, # |   +23 lookcook ORZZZZZZZZZZZZ
 » 4 days ago, # |   +66 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!
•  » » 4 days ago, # ^ |   +122 Just like the gender of your profile picture, I guess no-one knows for sure :P
•  » » » 4 days ago, # ^ |   -16 But the gender shouldn't matter right? I thought all genders were equal.
•  » » » » 3 days ago, # ^ |   -15 Alright, i'll upvote.
 » 4 days ago, # | ← Rev. 4 →   +10 [deleted]
•  » » 4 days ago, # ^ |   +9 bing chilling during the codeforces round
•  » » 3 days ago, # ^ |   0 Finally i can see John Cena . :_:
•  » » 2 days ago, # ^ |   +8 Bing Chilling to you too
 » 4 days ago, # |   +28 As a tester, hope you have a decent day.
 » 4 days ago, # |   +91 There will be at least $-494$ non-interactive problems, as long as I did all the math correctly.
 » 4 days ago, # |   0 May the force be with us and that we solve all problems)
 » 4 days ago, # |   +38 This round's editorial will probably be published earlier than #765
 » 4 days ago, # |   -23 "There will be at most five hundred interactive problems in the round" why????????
•  » » 4 days ago, # ^ |   +86 501 interactive problems in one contest was deemed excessive.
•  » » » 4 days ago, # ^ |   0 have you encountered a contest in which all problems are interactive
•  » » » » 3 days ago, # ^ |   +14
 » 4 days ago, # |   +1 Really excited for this one.
 » 4 days ago, # |   0 fishy15 ORZ
 » 4 days ago, # |   +11 Is every problem in this contest interactive ?
 » 4 days ago, # | ← Rev. 2 →   +49 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.
 » 3 days ago, # |   +12 Thank you for preparing this wonderful contest!
 » 3 days ago, # |   +4 Wishing good luck to everyone :)
 » 3 days ago, # |   -10 is there any penalty for wrong submission
•  » » 3 days ago, # ^ |   +5 Ofc there will be as always -50 points for any wrong submission till accepted
•  » » » 3 days ago, # ^ |   0 Siiuuuuuuu!
•  » » » 3 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 3 days ago, # ^ |   0 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
•  » » » » » 3 days ago, # ^ |   0 Oh, Thanks for reply
 » 3 days ago, # |   0 what does five hundred interactive problem means?
 » 3 days ago, # |   0 Good luck every body
 » 3 days ago, # |   +14 "omg hi codeforces" meme
 » 3 days ago, # |   +1 Score Distribution ?
•  » » 3 days ago, # ^ |   -24 We do a little trolling.
 » 3 days ago, # |   0 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?
•  » » 3 days ago, # ^ |   0 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...
 » 3 days ago, # |   0 HiCan anyone suggest me something to reach expert
•  » » 3 days ago, # ^ |   +19 Stop thinking about reaching expert :) Instead focus on solving problems harder than your current rating and solving problems of your current rating fast.
 » 3 days ago, # |   +18 score distribution is interesting ...
 » 3 days ago, # |   0 There will be at most five hundred interactive problems in the round, which means all problems might be interactive. That's interesting!
•  » » 2 days ago, # ^ |   0 The Pigeonhole principle, I see
 » 3 days ago, # |   0 I guess, the problem B is harder than usual ... may be , it is interactive ...
 » 3 days ago, # |   +14 Hope people like me who gained negative rating changes in the last round can win back.
 » 3 days ago, # |   0 Wish everyone good luck and high rating!
 » 3 days ago, # | ← Rev. 2 →   0 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
 » 2 days ago, # | ← Rev. 2 →   -53 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.
 » 2 days ago, # |   +40 Wow, the round has official video editorials. I appreciate the effort from authors and testers.
 » 2 days ago, # |   +8 Best of luck guys ✌️ See you after the contest.
 » 2 days ago, # |   0 How to become a tester?
•  » » 2 days ago, # ^ |   +11 This has been asked and answered too many times
 » 2 days ago, # |   0 Why is codeforces not working on wifi but working on mobile data . Was not able to participate in this contest due to this reason .
•  » » 32 hours ago, # ^ |   0 DNS issue most probably
 » 2 days ago, # |   +9 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.
•  » » 2 days ago, # ^ |   +13 No if you don't submit any solutions you don't loose ratings or count as participant
•  » » » 2 days ago, # ^ |   +8 Okay. Thanks mate.
 » 2 days ago, # |   +24 Absolutely love the problem statement of E, it's from one of my favorite movies!
 » 2 days ago, # |   +18 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
•  » » 2 days ago, # ^ |   +50 it made me laugh :D
•  » » 2 days ago, # ^ |   0 Singles be like: Let's move on to problem B.
 » 2 days ago, # |   +29 This round was good one
 » 2 days ago, # |   +19 If i get fst in Problem D, I will die.
 » 2 days ago, # |   -16 BFSForces :D
 » 2 days ago, # |   +20 too easy C, D but hard B.
•  » » 2 days ago, # ^ |   0 Bruh...what the hell wwas B ???....I was tired of it
•  » » » 2 days ago, # ^ | ← Rev. 3 →   0 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
•  » » » » 2 days ago, # ^ | ← Rev. 2 →   0 wtf !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I am worthless...
•  » » » » 2 days ago, # ^ |   0 oh it's faster than bfs, wish i knew it sooner
•  » » » » 2 days ago, # ^ |   +8 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 :'(
•  » » » » » 2 days ago, # ^ |   +9 The way you said that sounds creepy...lol
 » 2 days ago, # |   +3 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
•  » » 2 days ago, # ^ |   +3 Your solution looks mostly correct on first glance, but you can solve this problem without needing maps and implementation is fairly clean.
•  » » 2 days ago, # ^ |   +3 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.
•  » » » 2 days ago, # ^ |   +3 I removed repeating values, actually it was Len who did it. Just compare my last contest submission and last submission.
•  » » » » 2 days ago, # ^ |   +3 Wow, this trick works magically. But why, even if I don't do it, it still should be order nlog(n).
•  » » » » » 2 days ago, # ^ |   +3 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.
•  » » » » » » 2 days ago, # ^ |   +3 yeah got it. Never mind
 » 2 days ago, # |   0 please any hint to solve D
 » 2 days ago, # |   0 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.
•  » » 2 days ago, # ^ |   0 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
 » 2 days ago, # | ← Rev. 3 →   +3 Problem D: Link Codeint countDifferentSubsequenceGCDs(vector& nums) { int max_num = *max_element(begin(nums), end(nums)), res = 0; vector flags(max_num + 1); for (auto num : nums) flags[num] = true; for (auto i = 1; i <= max_num; ++i) { int ni_gcd = flags[i] ? i : 0; for (auto n = 1; n * i <= max_num && ni_gcd != i; ++n) if (flags[n * i]) ni_gcd = ni_gcd ? gcd(ni_gcd, n * i) : n * i; res += ni_gcd == i; } return res; } int main() { fastio; int n; cin >> n; vt a(n); for(auto& x : a) cin >> x; cout << countDifferentSubsequenceGCDs(a) - n << "\n"; return 0; } 
 » 2 days ago, # |   +18 I can't be the only one who misread problem A as to color the row and column and not the cell intially.
•  » » 2 days ago, # ^ |   -9 https://imgur.com/a/KyW9gkNLiterally 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. :(
•  » » » 2 days ago, # ^ |   +8 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.
 » 2 days ago, # |   +3 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...
•  » » 2 days ago, # ^ |   0 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.
•  » » » 2 days ago, # ^ |   0 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.
•  » » » » 2 days ago, # ^ |   0 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).
•  » » » » » 2 days ago, # ^ |   0 Why do we need all floor vertices?? 2*k ladder vertices and (1,1) should work??
•  » » » » » » 2 days ago, # ^ |   0 Yes floor vertices are unnecessary, my implementation for this uses the 2k ladder endpoints, (1, 1), and (n, m).
•  » » » » » » 2 days ago, # ^ |   0 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.
•  » » » 2 days ago, # ^ |   0 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.
•  » » » » 2 days ago, # ^ |   0 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
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » 2 days ago, # ^ |   0 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.
•  » » » » » 2 days ago, # ^ |   0 for(int j:v[i]){ if(!dist.count({i,j}))continue; for(auto k:g[{i,j}]){ 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).
•  » » » » » » 2 days ago, # ^ |   0 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.
•  » » » » » » » 2 days ago, # ^ | ← Rev. 2 →   0 fixed:)
•  » » » » » » » » 2 days ago, # ^ |   0 Thanks so much, I guess I didn't understand your initial comment. It's a dumb mistake on my end though :(
•  » » 2 days ago, # ^ | ← Rev. 3 →   0 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). DrawingAfter 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)
 » 2 days ago, # |   +1 Great Contest. Balanced. Loved problem D. Thankyou!
 » 2 days ago, # | ← Rev. 2 →   0 codemy approach for C: if any node has degree more than 2-> -1 start dfs from leaf node and assigning edge alternate 2 and 3 as weight is this approach correct? please point out what I did wrong
•  » » 2 days ago, # ^ |   +4 you are specially for checking size ==3,check for size >2
•  » » » 2 days ago, # ^ | ← Rev. 3 →   0 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
•  » » 2 days ago, # ^ |   +1 if(!flag){ cout<<-1<
•  » » » 2 days ago, # ^ |   0 Thanks man... I kept staring for 1.5 hours but was not able to figure that out
 » 2 days ago, # |   0 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??
•  » » 2 days ago, # ^ |   0 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.
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 oh thanks! i think there must be something to do with my implementation, let me revisit it.
 » 2 days ago, # |   +62
•  » » 2 days ago, # ^ |   0 Seems like problem setters of this round are die hard fans of srk.
 » 2 days ago, # |   +3 first to be the first AC in D :) cool : L
•  » » 2 days ago, # ^ | ← Rev. 2 →   +2 How can you D that quickly, and then fail on B? (No offence, but for nearly all of us B<<< D)
•  » » » 2 days ago, # ^ |   0 maybe I solve math problem better than some tricky problem :L
•  » » » » 2 days ago, # ^ |   0 For me D == tricky :D
•  » » » » 2 days ago, # ^ |   0 But congratulations btw. Really strong maths skills
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 Can you please explain your approach pls ?Ok Ok i got that...amazing approach.
 » 2 days ago, # |   +4 Multisource bfs in B ?
•  » » 2 days ago, # ^ |   0 Not needed.
•  » » 2 days ago, # ^ |   +8 We can simply calculate maximum distance for every vertex ...and then store it in a multiset..
•  » » » 2 days ago, # ^ |   +4 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
•  » » » » 2 days ago, # ^ |   +5 oof that's such a cool idea. I'm so annoyed for writing BFS xD
•  » » 36 hours ago, # ^ |   0 i used bfs in my solution , i couldn't think of any greedy idea during the contest here it is 142893044
•  » » » 35 hours ago, # ^ |   0 Amazing
 » 2 days ago, # |   +22 Interesting and balanced problems. Very nice round!
 » 2 days ago, # |   +5 WoW, I fucked myself in this contest.
•  » » 2 days ago, # ^ |   +3 Same here, though the problems were noice, especially B with the manhattan distance observation
 » 2 days ago, # | ← Rev. 2 →   -64 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.
•  » » 2 days ago, # ^ |   +28 The problem statements were straight to the point.
 » 2 days ago, # | ← Rev. 2 →   +3 Not Bad
 » 2 days ago, # |   0 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)?
•  » » 2 days ago, # ^ |   0 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.
 » 2 days ago, # | ← Rev. 2 →   +24 [deleted]
 » 2 days ago, # | ← Rev. 3 →   0 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
•  » » 2 days ago, # ^ |   0 Jesus ... must have cost a lot of points.
 » 2 days ago, # |   +3 Notforces!
 » 2 days ago, # |   0 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.
•  » » 2 days ago, # ^ |   0 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
•  » » » 2 days ago, # ^ |   0 Oh, yeah, I got it. Thank you very much! :)
 » 2 days ago, # |   0 nice problem B, so lucky i have been practicing BFS recently :))
 » 2 days ago, # |   0 wow very fast editorial! nice
 » 2 days ago, # |   0 anyone else got mle in question 3 in system test?
 » 2 days ago, # |   +3 Problem D is equal to this leetcode1819.(The problem is in Chinese)
•  » » 2 days ago, # ^ |   0 link_englishLol I even have a solution there, but I can't remember doing that :(
 » 2 days ago, # | ← Rev. 2 →   0 Stupid Question, Ignore. :facepalm:
•  » » 2 days ago, # ^ |   +3 dijkstra doesn't work for negative edges and is intended to TLE.
•  » » 2 days ago, # ^ |   +14 Hello fellow same-surname, testcase 4 was an anti-Dijkstra testcase (regular Dijkstra doesn't work with negative edges).
•  » » » 2 days ago, # ^ |   0 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.
•  » » » » 2 days ago, # ^ |   +29 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.
•  » » » » » 2 days ago, # ^ | ← Rev. 3 →   +5 To add to this, confusedsouls, the testcase is basically $\frac{k}{2} = 5 \cdot 10^4$ of these "loops".
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 Nvm
 » 2 days ago, # | ← Rev. 2 →   +1 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)
•  » » 2 days ago, # ^ |   +11 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.
•  » » » 2 days ago, # ^ |   +6 Sounds interesting, thank you!
 » 2 days ago, # |   +20 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 :)
•  » » 2 days ago, # ^ |   +14 I wasted around ~5 mins remembering the last scene when SRK jumps after reading that line.
 » 2 days ago, # |   0 after how much time our rating will be changed?
•  » » 2 days ago, # ^ |   +3 At most right before the next contest.
•  » » » 2 days ago, # ^ |   0 ok, thank you
 » 2 days ago, # |   0 As a contestant, I want to clear my contribution
 » 2 days ago, # |   0 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 .
•  » » 12 hours ago, # ^ | ← Rev. 2 →   0 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.
 » 2 days ago, # | ← Rev. 4 →   +69 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.
•  » » 2 days ago, # ^ | ← Rev. 2 →   +45 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).
•  » » » 2 days ago, # ^ |   +10 Ah, I see. I was solving the subarray version until I saw the clarification! But it still had a few observations in common.
•  » » » 2 days ago, # ^ |   +24 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).
 » 2 days ago, # |   +3 Very nice contest, but I feel like B and D should have been swapped.
 » 2 days ago, # | ← Rev. 2 →   +12 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 itBut 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
 » 2 days ago, # |   +9 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 2 days ago, # ^ |   +3 When I checked your profile and saw : Headquarters — Rating 1772, I thought you were using magic to become headquarters ...
•  » » » 37 hours ago, # ^ |   +38 -_-
 » 37 hours ago, # |   0 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
•  » » 37 hours ago, # ^ |   +3 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.
•  » » » 37 hours ago, # ^ |   0 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.
 » 20 hours ago, # |   +5 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.
 » 15 hours ago, # |   +3 Problem C is easier than B lmao.
 » 12 hours ago, # |   0 E had me like "Helikopter Helikopter".