### MofK's blog

By MofK, 19 months ago,

Hello Codeforces!

I am glad to invite you to Codeforces Round #601, which will take place on Nov/19/2019 17:35 (Moscow time). The round will be rated for both divisions.

All problems in this round were created and prepared by a team of all-Vietnamese setters: MofK, I_love_tigersugar, UncleGrandpa, ngkan. This is the first Vietnamese Div1 round. We tried to make both the problems and the statements interesting and hope that you will enjoy them!

There is an interactive problem in the round. You can read the guide for interactive problem here.

We would like to give a lot of thanks to:

We wish you an exciting round!

UPD: The message from MikeMirzayanov. If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295 Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest. Mike.

UPD: There will be five problems for Division 1 and six problems for Division 2. The score distribution is as follows:

Division 1: 750 — (500 + 750) — 1500 — 1750 — 2500

Division 2: 500 — 1000 — 1500 — 1750 — (1000 + 1250) — 2750

UPD2: : Thanks for participating! Congratulations to the winners!!!

Div. 1: Top 5 are also the only 5 contestant managed to solve all problems!

Honorable mention: Justice_for_721-incident for solving problem E in just 31mins!

Div. 2:

1. MbahSA1937 (solved all problems!)

2. mintwhale (solved all problems!)

3. Nightmare05

4. Don_Quijote

5. mangojunior

UPD3:Editorial is out!

• +529

 » 19 months ago, # |   +69 from VNOI with love =))
•  » » 19 months ago, # ^ |   0 me too :>> From VNOI with love <3
•  » » » 19 months ago, # ^ |   0 We all from VNOI, with many love <3
•  » » 19 months ago, # ^ |   0 VNOI <3
 » 19 months ago, # |   +6 From VN with orz!
•  » » 19 months ago, # ^ |   -40 orz
•  » » » 19 months ago, # ^ |   -42 orz
•  » » » » 19 months ago, # ^ |   -39 orz
•  » » » » 19 months ago, # ^ |   +69 3 was clearly enough
•  » » » » » 19 months ago, # ^ |   -33 we still need more orz smh
 » 19 months ago, # |   0 Is it supposed to last 2:15 opposed to the standard two-hour competition?
 » 19 months ago, # | ← Rev. 2 →   +63 Interactive problems are always fun and challenging.
•  » » 19 months ago, # ^ |   +176 If it is not a binary-search problem :)
•  » » » 19 months ago, # ^ |   +24 It indeed is not :) how do you feel about today's interactive problem?
•  » » 19 months ago, # ^ |   -13 Are you kiddin me??
•  » » 19 months ago, # ^ |   0 Game theory as well
 » 19 months ago, # |   +37 Wish everyone the best of luck and get a good rating after the contest!!
•  » » 19 months ago, # ^ | ← Rev. 2 →   -20 .
•  » » » 19 months ago, # ^ |   +18 Don't worry. Sometimes when we feel that we are not good, then we need to try a lot harder. For example, you should try to do harder problems such at Div 2 D E F, and aim that in a contest you need to finish A B C D E in 2 hours ( maybe F if you're able to ). Just don't giveup halfway through.
•  » » 19 months ago, # ^ |   0 Wish so :)
 » 19 months ago, # |   -13 Why will contest be held on Tuesday ? There is a Vietnam football match on this day.
 » 19 months ago, # |   0 From VN with love
 » 19 months ago, # |   +17 Vietnam national team will play football at 20:00 :(( oh no
•  » » 19 months ago, # ^ |   +117 Trust me, by that time Vietnam would have the game in their bag anyway, so please join our contest! :)
•  » » » 19 months ago, # ^ |   -27 Not yet calculated the case of rejected goals?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   -18 So many downvotes lol.Just how butthurt people were seeing your comment, or those ignorant dudes not getting the context and still trying to be superior.
•  » » 19 months ago, # ^ |   0 I feel you, I can't stop supporting my national team. So I will write the contest later. =)))
 » 19 months ago, # |   +4 Good luck everyone, from Vietnam with love <3
 » 19 months ago, # |   +21 There will be Hanoi Tower problems?
•  » » 19 months ago, # ^ |   0 Love that!!
 » 19 months ago, # |   +27
•  » » 19 months ago, # ^ |   +59 A character smarter than the cat in your profile picture doesn't exist.
 » 19 months ago, # |   0 then-french now-vietnamese next-?
•  » » 19 months ago, # ^ |   0 Koria :)
 » 19 months ago, # |   +20 But I always wondered, what if someone pass the 9999 rating in the future?
•  » » 19 months ago, # ^ |   +13 Actually the 9999 upper-bound is modifiable from the contest panel. Can change it to 1e9+7
•  » » 19 months ago, # ^ | ← Rev. 2 →   +4 .
•  » » » 19 months ago, # ^ |   +27 forget 9,999.It's not even possible to be rating.
•  » » 19 months ago, # ^ |   +10 That means one day tourist will be affraid of being banned from div1
 » 19 months ago, # | ← Rev. 3 →   -71 .
 » 19 months ago, # |   0 Good luck everyone, from Peru with love <3
 » 19 months ago, # |   0 I should be aware of I_love_tigersugar's tricks
 » 19 months ago, # |   -27 highly expecting Prof.PVH throwing some maniac traps into the statements like how he's done those National/Regional problems
 » 19 months ago, # |   +18 Hope to see both tourist and Benq participate in this round.
 » 19 months ago, # |   0 Have a nice round!
 » 19 months ago, # | ← Rev. 2 →   0 Hoping to see tourist become the highest rated coder on cf again
 » 19 months ago, # |   +12 The only question about the contestWill the No. 1 spot in the rating change ?tourist or Benq or Anyone else
•  » » 19 months ago, # ^ |   -13 but tourist is not registered yet
•  » » » 19 months ago, # ^ |   +56 but Benq can lose ratings
•  » » » » 19 months ago, # ^ |   +259 Agreed.
•  » » » » » 19 months ago, # ^ |   0 I love you
•  » » » 19 months ago, # ^ |   0 not registering does not means your rank can't increase or decrease. Everything is relative
•  » » » 19 months ago, # ^ |   +18 It seems tourist made the smartest decision: to stay away from this contest. The easiest way to regain the top spot!
•  » » » » 19 months ago, # ^ |   +31
•  » » » » 19 months ago, # ^ |   +3 It may also be possible that tourist wants to give others a chance to be at the top position.
•  » » » » » 19 months ago, # ^ |   -12 Like.... me?
•  » » 19 months ago, # ^ |   0 And it comes true now
 » 19 months ago, # |   0 For some reason I am not able to register for the contest :/ There is no register link displayed anywhere.
•  » » 19 months ago, # ^ |   0 Register now for extra rregistration
 » 19 months ago, # |   +11 Why close the Registration when the competition begins? I forget to register before the competition.
 » 19 months ago, # |   -13 I have no electricity right now and i have made submissions. Can you please make the round unrated for me because i am writing now from my phone with 4G. It is completly dark in my house and the only thing i can do is participate from my phone in a div1 contests which is absurd. Please understand my problem and help me.
•  » » 19 months ago, # ^ |   -36 I just submited from my phone and got accepted xdddd. Still can you please make it unrated for me. I dont know how to prove to you that i dont have any electricity now.
•  » » » 19 months ago, # ^ |   +60 Image checks out
 » 19 months ago, # |   -12 help in B DIV2
 » 19 months ago, # |   0 This round should be unrated. Sample and constraints should not be modified in-between contests. This creates an overall negative experience.
•  » » 19 months ago, # ^ |   +118 Sorry, we are all not perfect. This time I suggested such a change for the problem and it leads to a much more harder problem. This problem is really minor, all participants solved (thinking that they are solved) harder version actually solved the simplified version. I'll give a chance to exclude yourself from the rating if it really affects you. But 99% (or more) of users weren't really affected.Actually, I saw what diligence and efforts were put by both the writers and the coordinator. They really tried to do their best. All the other problems are great.Sorry again for the issue. I feel it mostly my mistake (I didn't ask writers to stress it with naive solution).I hope you liked the problems!
•  » » » 19 months ago, # ^ |   -128 No, I hate the problems
•  » » » 19 months ago, # ^ |   +37 Thanks, Mike for proactively addressing the issue.I was impacted as I was trying to solve a different problem all this time (as you can look from my submission history). I would want to be excluded from the rating.Codeforces is the best platform out there and a minor glitch here and there does not change the fact regarding how much effort goes into every round all thanks to admins, setters, testers and co-ordinators in maintaining the continuous high quality of every contest. Thank you for herding all the cats to keep things in order.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +18 If the issue heavily affected you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest.Thank you.
•  » » » » 19 months ago, # ^ |   +20 "Hardly" means "not much", heavily/strongly seems to be what you mean.
•  » » » » » 19 months ago, # ^ |   0 I think, a more appropriate word here would be "significantly".
•  » » » » » » 19 months ago, # ^ |   0 There are a lot of near-synonymous options.
•  » » » » » » » 19 months ago, # ^ |   0 "Near" is the key. :)
•  » » » » » » » » 19 months ago, # ^ |   0 Um, no? Any near-synonymous words work well enough if you're not dealing with formal writing and even more will convey the point, although awkwardly. The thing here is that "hardly" has the opposite meaning.
•  » » » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 I get the last point.
•  » » » » » » » » 19 months ago, # ^ |   0 programmers have their own English. It is as simple as possible
•  » » » » » » » » » 19 months ago, # ^ |   0 Neither variant being considered is simpler than any other.
•  » » » » 19 months ago, # ^ |   -29 Sorry , but how can i get unrated if my electricity was cut out a minute 47 of the contest and then i submitted for fun from my phone problem A an it passed. I had no way of participating for more than half a contests , i know that i can't prove it but may be somehow you can check where from my last submission was made, please help.
•  » » » » » 19 months ago, # ^ |   +39 Submit a notarized affidavit from the utility company.
•  » » » » » » 19 months ago, # ^ |   -26 Sorry but i didn't understand what you just said.
•  » » » » 19 months ago, # ^ |   +15 I am really disappointed of that. I solved the problem 2 min after the change. I lost a lot of time , 3 wrong submissions and maybe I could solve E1 Div2 I just needed more time to do that. I don't know what you gonna do but I really think I was affected to much by this. Thanks anyway the problems were amazing and I learnt new things.
•  » » » » » 19 months ago, # ^ |   +10 I solved E1 .... I think this is a real affect now..
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +2 The only issue for each and everyone who actually solved B initially was that we spent close to 45 mins more or less which reduces to less than 5 mins of time spent after the constraints changed, time that one could have utilized to solve C which was not a mighty hard problem.It's okay if you want to keep this rated but it makes user experience pretty weird.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 to me it seems like you are more or less telling my story.
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +15 Basically, if: you participated in the contest && you spotted the tricky case && you spent too much contest time thinking of how to solve/work around it (and/or tried to hack others based on it) then appeal, otherwise, move along :)
•  » » » » » 19 months ago, # ^ |   -10 A tricky case — I am sure it's not unique.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 I filled the appeal and It was rejected. why it was rejected ? you not just miss up a promising contest for me. but I also get -50. You probably didn't even read any appeals MikeMirzayanov
•  » » » 19 months ago, # ^ |   +38 What was the problem with $m>n$?
•  » » » » 19 months ago, # ^ |   0 The checker?
•  » » » » 19 months ago, # ^ |   +9
•  » » » 19 months ago, # ^ | ← Rev. 4 →   -57 Tell before the contest that you are not perfect and no one will ever participate;
•  » » » » 19 months ago, # ^ |   +5 lol you haven't even participated in a single contest, why are you whining?
•  » » » 19 months ago, # ^ |   +10 MikeMirzayanov Sir can you please tell us what was the problem with the problem that it required modification of constraint .Was it to make the problem easy or the tester code was designed for m <= n ?
•  » » » 19 months ago, # ^ | ← Rev. 3 →   -9 MikeMirzayanovMay you explain what do you mean "by all participants solved (thinking that they are solved) harder version actually solved the simplified version"? Was the problem with the checker? The solution is the same but only with adding edge between the 2 lightest fridges m-n times (which is a very easy addition that I doubt being the reason for the change in constraints).EDIT: Have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now.
•  » » » 19 months ago, # ^ |   +29 make it unrated for Benq, he was strongly affected
•  » » » 19 months ago, # ^ |   0 Why my submissions are skipped? :/ It was hard to me to get that position :c
•  » » » » 19 months ago, # ^ |   0 maybe u copy code from some one else
•  » » » » » 19 months ago, # ^ |   0 No, this is my only account and I would never do that. :/ If I had done that, I wasn't claiming now.
•  » » » » 19 months ago, # ^ |   0 It is unfair: c
 » 19 months ago, # |   +8 Anyone else thought in Div2D/Div1A that the rice cells assigned to every chicken form a connected area? I was going nuts trying to solve that, would be a really nice problem though.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +36 Div1A reminds me of this CF995A — Tesla when people go derp mode real hard.Contestants tried heuristic solutions, dijkstra, weird heaps, while you only need loops to solve it.
•  » » » 19 months ago, # ^ |   +17 Crazy, but what a nice chicken story behind, isn't it?
•  » » » » 19 months ago, # ^ |   +64
 » 19 months ago, # |   0 Div2 D and E1 should not have been together because they don't require much concepts and their implementation took a lot of time.
 » 19 months ago, # |   +7 How to solve div. 1 C Point ordering ?
•  » » 19 months ago, # ^ |   +26 Find the next point to first using second type of queries (n-2 queries used).Now we have 2 adjacent points. Now find areas of all the others with these 2.(n-2 queries).Now the take highest area point (lets say h). Now using 1,h,i we can decide side of i to h. And with information of area we can sort points in each side.
 » 19 months ago, # |   +25 Div. 2 Was just a coding contest, sorry but not the best contest :)
 » 19 months ago, # |   +10 How to solve Div1 C?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 we save the relevant number (1 to n) ex) (1,2,3) -> 1 save 2,3 and 2 save 1,3 and 3 save 1,2 i used set supervising the array for (1 to n) we find the number that has two sizes of set then, that number is what we start to solve the problem then, keep track of that number also erase the already using number from the other set the size of set of that number is three , then that is not proper number to keep going sorry, i am not good at english.. so i can't write any more
•  » » » 19 months ago, # ^ |   +18 Hmmm, looks like Div2 C
•  » » » » 19 months ago, # ^ |   +26 sorry
•  » » » » » 19 months ago, # ^ |   +5 Username checks out.
•  » » 19 months ago, # ^ |   +36 First of all, lock the first and second point. We'll consider other points to be on either side based on those two points.We can see that the query $(2, 1, i, j)$ can tell that in a permutation starting from $1$, which point will come first: if the response is $1$, $i$ comes before $j$, and the other way around if the response being $-1$.Loop through point from $3$ to $n$ to find out if each of them comes before or after $2$ in the permutation, using the query $(2, 1, 2, k)$. Here we can see that the points have been separated into two halves.For each half, we can see that, following the permutation's order (i.e. the points' counter-clockwise order), the area of the triangle with point $1$, point $2$ and point $k$ forms a bitonic sequence: the area increases until the maxima value, then it decreases. From this knowledge, we may do the following: Use the query $(1, 1, 2, k)$ for each half to get all the required areas. Pick the point with the maximum area as maxima (if there are many points having the same maximum, pick an arbitrary one). Traverse through the not-chosen-as-maxima points in the area-increasing order, check if it comes before or after the maxima using the 2nd type of query (similar to the aforementioned part). If it comes before the maxima, add it to the left side of the current half, otherwise add it to the right side. Total number of queries used will not surpass $3n-6$.
 » 19 months ago, # |   +41 Amazing contest, thanks for it! All tasks were very interesting!
 » 19 months ago, # |   -42 bullshit contest.
•  » » 19 months ago, # ^ |   +17 Why?
•  » » » 19 months ago, # ^ |   +5 Sorry, in B I was missing n=2 case, it took me 1 hour to find it, so contest went bad for me..Contest was good.
 » 19 months ago, # |   -9 Div2 C & D are just implementation problems.. got stuck with some sily bug in both..
•  » » 19 months ago, # ^ |   -12 the same for me , and problem B changed during the contest was very confusing to me, !Rated.
•  » » » 19 months ago, # ^ |   0 What changed in div2b during contest?
•  » » » » 19 months ago, # ^ |   0 Example inputs.
 » 19 months ago, # |   +1 what is pretest 5 in C it's so weird to me it's WA ...isn't it we just see the first 3 numbers and then we can detect the next number
 » 19 months ago, # | ← Rev. 3 →   0 how solve div 2 b
 » 19 months ago, # | ← Rev. 5 →   +13 well i thought if div2b if m
•  » » 19 months ago, # ^ |   +8 when n == 2 && m == 2, then answer is -1
•  » » » 19 months ago, # ^ |   0 why?
•  » » » » 19 months ago, # ^ |   0 because in that case both the chains will be (1 <-> 2) and anyone (1 or 2) can unlock all the chains, so no fridge is private.
•  » » » » 19 months ago, # ^ |   0 Your query is answered in the problem statement itself.
•  » » 19 months ago, # ^ |   0 n = 2
 » 19 months ago, # |   0 How to solve div2B ?I was thinking of connecting each of them to the 2 with the smallest values
•  » » 19 months ago, # ^ |   0 case where you have 3 fridges and 2 chains, your code will fail. answer should be -1.
•  » » » 19 months ago, # ^ |   0 What was your solution?
•  » » 19 months ago, # ^ |   0 Solution: SpoilerIts possible only when n<=m. Create a cycle connecting all fridges (1-2-3-4..-n-1), now connect the remaining chains to 2 fridges with least values.
•  » » » 19 months ago, # ^ | ← Rev. 4 →   +8 That's incorrect, consider N = 5 nodes with weights 0 1 2 3 4, and M = 6After building the cycle with 5 edges, you can remove the edge between 2 and 3 to create two edges between (0 and 2) and (0 and 3), which costs the same and uses all edges instead of creating a new one that costs 1 more.
•  » » » » 19 months ago, # ^ |   0 So to replace a chain between any 2 fridges with 2 chains coming from the smallest-weighted will cost 2*(smallest-weighted). And add a chain between 2 fridges with least values will cost (smallest-weighted + second-smallest-weighted). If the first one is smaller then you can just replace any pair of fridges k time. If not, you can add k number of chain between 2 fidges with least values.
•  » » » » » 19 months ago, # ^ |   0 You certainly can't "just replace any pair of fridges k times" since in the example above you can't replace the edges 0 and 1, 1 and 2, 3 and 4 or 4 and 0
•  » » 19 months ago, # ^ |   0 Solution BSo you notice that you need to connect each fridge to minimum of 2 other fridges for it to be secure. If only 1 man knows answer or no answer is needed, it is not secure. So each fridge contributes to sum with 2*its_weight + weights for connected fridges to him. Well we can get greedy and try to achieve getting 2*weight for each fridge contribute to the answer. We cannot get less, and this we can get by forming a cycle. n = 2 is edge case because that cycle we do not like. If we need any more chains, just take the cheapest one k times to fill the gap. And if we took more than we could take, then answer is no
 » 19 months ago, # |   -11 problem B is bad..
•  » » 19 months ago, # ^ |   +1 Felt like C in difficulty to me, both implementation and solution
•  » » » 19 months ago, # ^ |   0 I felt c was horrible in implementation, what did you do for c?
•  » » » » 19 months ago, # ^ |   0 Not too horrible if you store everything in sets, cause you just need to know if it contains stuff or not, something like 3 loops it makes
•  » » » » 19 months ago, # ^ |   0 i guess linked list can help here
 » 19 months ago, # |   0 wa9 on E1 and pretests passed on E2. cmooon. Does it means that solution differ or threre are just different tests?
 » 19 months ago, # |   0 I was getting wrong in e1 easy. My strategy was to accumualate lowest prime factors of total 1 at one place(middle of that prime factors) . can any tell me what i m doing wrong?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +1 first i did the same, wa at 8. check all factors(no need prime) and pp
•  » » » 19 months ago, # ^ |   0 thanks
•  » » » 19 months ago, # ^ |   0 why should we check all factors? I had solution on contest that passed E2 pretests and failed on E1. It is probably a bug, but i can't find it. Idea is to find all prime factors and enumerate over it. For each prime factor find an answer, grouping by this number to it's meridian. I checked test i failed on, but it is too big. (submission 65381763)
•  » » 19 months ago, # ^ |   +2 In array 1 1 1 0 0 1 1 1 The best solution would be 4 (divisible by 3)
•  » » » 19 months ago, # ^ |   0 thanks for reply and test case.
•  » » » 19 months ago, # ^ |   0 you can collect 3 on 2-nd and 7-th place. What is wrong with idea of accumulating prime factors?
 » 19 months ago, # |   +11 Why were constraints for B changed??
 » 19 months ago, # |   +16 When you realize that its not the boxes to be shuffled but the units in them in E1.......
•  » » 19 months ago, # ^ |   +42 When you realize you passed pretests with a blatantly incorrect solution ...
•  » » » 19 months ago, # ^ |   0 Which question are you talking about sir?
•  » » » » 19 months ago, # ^ |   +1 The same problem you are :P
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Aah, actually I could say that for my solution as well :(
 » 19 months ago, # |   +7 After one hour of round I see message with words "sorry, we gave you wrong task". What is it?
 » 19 months ago, # |   0 What was the required time complexity for DIV2 c ?
•  » » 19 months ago, # ^ |   0 If a number X appears just 1 time in all triplets, it must be the first/last one in the original permutation. Save number->triplet mapping and start finding with X. It's an O(n) solution.
 » 19 months ago, # |   +7 Those pretesting times on div1 D...
 » 19 months ago, # |   0 Thanks you for this contest
 » 19 months ago, # |   0 I guess that the std of D is O(n^1.5) . (because of so large time limit)
•  » » 19 months ago, # ^ |   0 I'm pretty sure O(n^1.5) wouldn't need a large time limit, especially not for such low constraints. I've got $O(Q \sqrt{N \log N})$ where the log factor comes only from binary search. It still got TLE, but on pretests 29 and then 34, so it must be pretty close to passing.
•  » » » 19 months ago, # ^ |   +5 It can be done in $O(Q \sqrt{N})$ online
•  » » » » 19 months ago, # ^ | ← Rev. 6 →   0 Could you please tell how to solve it in $O(Q\sqrt N)$?I've seen your submission which perform (# different subtree size of $v$) for each update on $v$.The tightest bound I know is $O(Q\sqrt N log N)$ for (# different subtree size of $v$) can't be too much.I believe it has tighter bound but can't come up of a proof. (Ignore this line, found myself stupid :( )
•  » » » » » 19 months ago, # ^ |   +8 You can eliminate the log factor as described in my other comment
•  » » » 19 months ago, # ^ |   +20 I think D's O(nlogn) solution is very interesting, but unfortunately std is O(n^1.5)
•  » » » » 19 months ago, # ^ |   +3 "std" is the namespace, do you mean the intended solution and that there's a log solution?Okay, so the time limit is just intentionally loose and a lot of slow solutions had a chance thanks to that. I'll try squeezing through with my own.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 what is the $n \log n$ solution?
•  » » » » » 19 months ago, # ^ |   +91 Root the tree at node 1. Suppose we iterate through all the neighbors of node $v$ for some type 1 query; we can update a child's subtree or the parent's subtree in $O(log(n))$ with a segment tree. Since the number of neighbors can be $O(n)$, this solution is $O(qnlogn)$. So we can't really traverse every child of an update node. Instead, for an update, we will update the biggest child's subtree and the parent's subtree "normally". We won't update the other children but we will keep a running sum of type 1 updates for each node $u$, which can be used later. The answer for a node will be the value of that node in the segment tree + some of it's ancestor's updates which we didn't apply. We can traverse through each such ancestor and sum up the answer. The number of such ancestors will be $O(log(n))$. So, our total complexity is $O(QlogN)$.
•  » » » » » » 19 months ago, # ^ |   0 The number of such ancestors will be $O(log(n))$Can you explain this?
•  » » » » » » » 19 months ago, # ^ |   +13 If the biggest subtree of node u is that of child v, then we call edge (u, v) heavy. Others are light edges. Starting from a node, if we go up to the root, there will be at most $O(log(n))$ light edges. Proof
•  » » » » » » » » 19 months ago, # ^ |   0 I was not familiar with this technique. Thank you!
•  » » » » » » 19 months ago, # ^ |   0 That's cool. Thank you!
•  » » 19 months ago, # ^ |   -10 I am the author of this problem. My solution runs in $O(QT\log{N} + QN/T)$ with some predefined constant $T$. I divide all queries into blocks of $T$. Choosing every $T$ between $175$ and $350$ should give you AC, unless your implementation has huge constant factor.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Might give you AC if you haven't put effort into keeping your constant factor explicitly low. That's how it always is with these problems, you need to check.UPD: I just didn't have high enough $T$ to pass (I had 350), but more optimisations speed it up massively.
•  » » » 19 months ago, # ^ |   0 I had $T=\sqrt{N/\log N}\approx93$. Where did you get 175 and 350?
•  » » » » 19 months ago, # ^ |   +10 It turns out (a bit counterintuitively) that with such sqrt solutions, the branch "update values after processing a block" has a much worse constant than "answer query", probably because it's basically DFS and that's cache-inefficient and just more to calculate. You need less blocks than the theoretical value implies.
•  » » » 19 months ago, # ^ |   +20 Maybe you should learn from the god of sqrt decomposition ODT
 » 19 months ago, # |   0 bad div2 B, the first time to get ranked 3k+...
•  » » 19 months ago, # ^ |   0 Can you explain the problem statement I can't even understand it
•  » » » 19 months ago, # ^ |   +1 u need to take care of the case with n = 2(ans = -1), n=3, n=4, when n > 4 && m > n, the smallest ans will not be the circle cause the head and tail can connect to the smallest node, the left edge just link the smallest and second smallest node, just it...
•  » » » » 19 months ago, # ^ |   0 if n = 2 or m < n, ans =-1, otherwise answer is circle and (m — n) edges between two smallest nodes. To lock fridge, you must connect it with two different fridges, so each node must have min 2 edges. So in cost weight of each fridge will be counted minimum 2 times, it just turns out when you connects all fridges in circle and in this case all fridges are private. It takes n edges and other (m-n) edges must have minumum weight, just connect two smallest fridges (m-n) times. Its not clear explanation, but i hope it helps to understand solution.
•  » » » » » 19 months ago, # ^ |   0 look this blog https://codeforces.com/blog/entry/71562 and you will notice that you were wrong.
•  » » » » » » 19 months ago, # ^ |   0 whoops, i didn't see it, thanks.
 » 19 months ago, # |   +70
•  » » 19 months ago, # ^ |   +85 It was my problem in the round. I didn't know (also the coordinator and writers) about the previous problem. Yes, it is very similar. Sorry about it. My problem was invented completely independently by myself. You see, it is not the first, not the last case when problems coincide. Sometimes it happens, sorry. Moreover, it can happen even on more important official contests. It's a life. The only way to prevent prepare a similar problem, just do not invent any problems. But I don't think it is the right way.
•  » » 19 months ago, # ^ |   0 Is there an english editorial for it ?
•  » » 19 months ago, # ^ |   +24 Maybe I have a solution that differs from yours, but I can't get how one can solve this problem using the solution to the problem you mentioned.
•  » » » 19 months ago, # ^ |   0 Yeah it's subtly different. In the old problem, the permutation is treated as circular.
•  » » 19 months ago, # ^ |   +9 That is interestingI'm not saying it's the same code, but it's interesting submit during the contest somewhere else
 » 19 months ago, # |   +5 What is testcase 2 for div2 C ?
 » 19 months ago, # |   +6 Took a long time to implement B & C. Problem D, a zig-zag scan will do but i don't have time to finish it correctly. sad.
 » 19 months ago, # | ← Rev. 2 →   -9 deleted
 » 19 months ago, # |   0 I thought of a solution for Div2. B as it was originally.Any review would be appreciated : I thought of first making 1 cycle of size N(in case when m>=n) and from set of total edges sorted by weight, to remove edges till my graph contains M edges.Is it a correct solution?Please confirm.
•  » » 19 months ago, # ^ |   0 but it allow multiedge between two nodes
•  » » » 19 months ago, # ^ |   0 Yes, thank you!I was missing that
•  » » 19 months ago, # ^ |   0 if all fridges have same value except 2 that have a larger value than the others, you might break the cycle of n. (if m=n+1, the last edge you remove is the one between the 2 larger valued fridges).
•  » » 19 months ago, # ^ |   0 In fact, I solved D2/B and still do not get was was wrong with it, why the change?
•  » » » 19 months ago, # ^ |   0 If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy (assuming that your strategy is the one everyone used — build a cycle of size N and add the edge between the 2 minimums how many times it is needed), while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.
•  » » 19 months ago, # ^ |   0 You can add same edge several times so just add the one with minimum weight instead of removing things which might result in incorrect solution
•  » » » 19 months ago, # ^ |   0 Oh sorry, my bad..
 » 19 months ago, # |   -7 Didn't like the problems of this contest, got stuck in Div2/C with some more or less stupid implementation problems. Now, afterwards, having read D and E it would have been better to not work on C.Afterwards we allways know better.I was not able to register within like first 10 minutes of contest. That sucks.
 » 19 months ago, # | ← Rev. 2 →   0 Not Satisfied with Today's Contest1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 Here is the test case that made me thinking for over an hour in B and finally your announcement came.Contest should be unrated for everyone
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 how did you solve for m > n, same was troubling me for more that hour, when new constraint was announced, I got the idea in 2 minutes but due to some silly mistake and debugging, took some time to get B accepted.
•  » » » 19 months ago, # ^ |   0 Mathematically if m = 2 * n — 3 Then we can perfectly select two smallest cost fridges and connect all with them.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +4 MikeMirzayanov I guess if you go for previous constraints where m<=2000 80% of people who solved it till that would get WA so I am still wondering why this contest can't be unrated.Still wondering why people who couldn't able to figure out for 1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 and go for making a cycle just for n==m should get benefit over people who wasted time.
•  » » » » 19 months ago, # ^ |   0 I was thinking of selecting two smallest cost fridges and adding all else to them but what if m > n && m < 2 * n — 3 ?
•  » » » » » 19 months ago, # ^ |   0 Here you can think of select any smaller x
•  » » » » » 19 months ago, # ^ |   -12 Make a cycle of length n, you're left with m — n edges, use them all to connect two smallest fridges. Works for all m and n
•  » » » » » » 19 months ago, # ^ |   -8 except when m < n or n = 2
•  » » » 19 months ago, # ^ |   0 you could make multi-edges though
•  » » » » 19 months ago, # ^ |   0 I do but with the new constraints for this test case1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 total cost is 36k approxbut in old constraints, it should be 16k approx.. that's what I'm saying..
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 it doesn't affect jury's solution right?and your test case not satisfying 1 <= m <= 2000 in the old constraint and 1 <= m <= n in the new constraint
•  » » » » » » 19 months ago, # ^ |   0 How about 1 10 1000 1 1 1000 1000 1000 1000 1000 1000 1000 1000
•  » » » » » » » 19 months ago, # ^ |   0 it's 17984
•  » » » » » » » » 19 months ago, # ^ |   0 And what if we connect 1 and 2 node to all and then just 1 and 2 m — n + 1 times?
•  » » » » » » » » » 19 months ago, # ^ |   0 This is invalid. All nodes $i$ ($i>2$) will not be private (node $1$ or $2$ can unlock them working alone).
•  » » » » » » » » » 19 months ago, # ^ |   0 They can't for opening any i both 1 and 2 would be required.
•  » » » » » » » » » 19 months ago, # ^ | ← Rev. 3 →   0 $1$ and $2$ will be required if only every $i$ ($i>2$) was connected to both $1$ and $2$. And it will give no lower cost (than in the cycle construction method) as weight of every $i$ ($i>2$) is still added $2$ times to the total cost.EDIT: I have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now. Got the issue.
•  » » » » » » » » » 19 months ago, # ^ |   0 aight from mohamedeltair's link I can see the problem now, thanks for discussing :)
 » 19 months ago, # |   0 Am I the only one who solved div2 D within 50min but could not solve C:(BTW, how to solve div2 C?
•  » » 19 months ago, # ^ |   +1 Solution CFor each number, count number of times you have seen it in any triplet. Notice that you see first one only in one triplet and last one only in one triplet. Pick any of them, the second value will be the one you see twice in any triplet and the third one will be the one left. Now, iterate over array to find next value. To find next value, find a triplet containing last 2 values and another unseen value. This unseen value is our next candidate. Finding id's of triplets might be done in O(1) by storing them in an array. So the solution is O(N)
•  » » » 19 months ago, # ^ |   0 How are we going to sort the triplet's array?
•  » » » » 19 months ago, # ^ |   0 Don't sort it, just know for each number the three triplets that contains it. Map, vector, anything
•  » » » » » 19 months ago, # ^ |   0 thanks mate
 » 19 months ago, # | ← Rev. 2 →   +55 I wasted 20 minutes because I missed the $p_1 = 1$ condition in C (interactive problem). Not reading statements carefully hurts :(I would highlight it or write something like "all these conditions mean that the output is unique", that would help.Also, I didn't like the round. Problems A-D didn't require much thinking. Just my opinion.
•  » » 19 months ago, # ^ |   +30 Daaaaaamn I didn't even see that, luckily my solution does that by default
•  » » 19 months ago, # ^ |   0 I also missed it, got WA on pretest 1, read the sample error message, fixed it and resubmitted.
•  » » » 19 months ago, # ^ |   +8 wtf, that thing is always displayed?
•  » » » » 19 months ago, # ^ |   +13 For samples, yes — it sure is better than dealing with eternal "I got WA on the first sample but my solution works on it!". I didn't even rely on that, just automatically clicked on my submission and scrolled down.
•  » » » » » 19 months ago, # ^ |   +5 It is helpful, obviously. I just didn't know it exists and it should be this way. Can I see that msg for all problems with a checker?
•  » » » » » » 19 months ago, # ^ |   0 Yes you can. This is actually a very useful feature of Codeforces that not many people know. I only discovered this during an ICPC training with 10 WA on test 1.
•  » » » » » » » 19 months ago, # ^ |   0 This should definitely be considered as bug not a feature and be fixed asap.
•  » » » » » » » » 19 months ago, # ^ |   +19 +1, don't rules say that you only see WA/TLE/etc. verdict for the first failed test?
•  » » » » » » » » 19 months ago, # ^ |   +8 As I mentioned, it helps avoid questions about samples, so I'm not opposed to changing it and creating a Polish Brigade for answering questions during contests (for free, ofc). It would be like Microsoft Tech Support except with Poles instead of Indians!
•  » » » » » » » » » 19 months ago, # ^ |   -24 What kind of a twisted reasoning is that? Maybe we should write some machine learning algorithm that tells you which line of your code contains bug in order to omit questions?
•  » » » » » » » » » 19 months ago, # ^ |   0 That would be interesting, you can even try to pitch it as a startup idea.
•  » » » » » » » » » 19 months ago, # ^ |   -20 The same argument can be used for introducing rule "show what first failed test looks like". No other platform displays some detailed verdict for test 1, right?
•  » » » » » » » » » 19 months ago, # ^ |   0 The first failed test is always in the statements?
•  » » » » » » » » » 19 months ago, # ^ |   +1 Only if you fail a sample test...
•  » » » » » » » » » 19 months ago, # ^ |   +148 Topcoder displays checker verdict for test 1 as well :)What exactly is wrong with that? The only problem I see is lack of awareness, and yes, it can be improved.
•  » » » » » » » » » 19 months ago, # ^ |   +11 Well, that's why you can see it for sample tests. When you have undefined behaviour, you see a different output and a comment for that output. Otherwise, it doesn't give you extra info beyond which rule from the Output section you're failing.It sounds like you're glad you spent so much time on it.
•  » » » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   -12 You are right that Topcoder does that too.The lack of awareness is a big deal (knowing that you should click something and then you will get a hint). Two small issues are being different than other platforms and the fact that a participant can check this way if there is indeed a checker in the problem. It sounds like you're glad you spent so much time on it. It's more convenient to see this thing, but I need to know about this feature in the first place. It's something easy to forget, I don't like it.
•  » » » » » 19 months ago, # ^ |   -45 What the actual fuck?
 » 19 months ago, # |   -29 So, what will happen to me because I had 3 WA submits for prob B and after rejudging, I got 3 AC submits in total, tbh I dont like this contest because of rejudging and in prob D, number of rows is r and c for columns and I followed it, then it took me a lot of time to debug because I used variable with same name (in other contest, they use m and n instead of r and c) and I cant like this kind of trick at all. If it had been m and n, I would have been able to solve this prob on time (with some luck). Anyway, I will try my best till I get to my goal. Have a nice day everybody!!
•  » » 19 months ago, # ^ |   +30 Tbh, you can make your life easier, instead of int r,c; cin >> r >> c;just do int m,n; cin >> m >> n;It isn't really a "trick", it's just your implementation skill.
•  » » 19 months ago, # ^ |   +25 Use meaningful variable names in your code, you will never be confused. int numRow, numCol; cin >> numRow >> numCol; 
•  » » » 19 months ago, # ^ |   +21 Or just H and W, as in height and width.
•  » » 19 months ago, # ^ | ← Rev. 2 →   -32 Can anybody tell me why I get a lots downvotes here? I dont think I had any very big mistakes in my comment. Quite annoying when seeing it without any acceptable reasons, hmm...
•  » » » 19 months ago, # ^ |   +13 Your comment is quite boring. Yes, people make bugs. Complaining about the contest because $r$ and $c$ are bad variables seems stupid. And you could use some more sentences (dots at the end and then an uppercase).But don't care too much about downvotes in CF, they are quite random.
•  » » » » 19 months ago, # ^ |   +19 Your comment helps me feel a little better. Thank you!
 » 19 months ago, # |   +3 What's the correct solution for Div2B in case n < m < 2n — 4? Does greedy work?
 » 19 months ago, # | ← Rev. 2 →   0 Wasn't the solution of both the cases (m>n and m<=n) of DIV2 B was to create a cycle and thus the answer will be 2*(sum of weights of all fridges) and if mn we have (sum of least two weights ) * (m-n) + 2*(sum of weights of all fridges )
•  » » 19 months ago, # ^ | ← Rev. 2 →   +1 Create the cycle, so every fridge has two locks, then add chains between the two cheapest fridges until m is reached.Edit: Turns out that this is wrong.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 take $n = 4, m = 4, a = [0, 0, 1000, 1000]$. For "cycle" solution, the answer is $4000$, but you can get $2000$ if you connect $2-0$, $2-1$, $3-0$, $3-1$
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +5 2 — 0 costs 0 + 10002 — 1 costs 0 + 10003 — 0 costs 0 + 10003 — 1 costs 0 + 1000total: 4000
•  » » » » 19 months ago, # ^ |   +3 I think answer will by cycle only since to avoid other person to open the fridge , each fridge should be connected to two other fridges and thus it's weight will be added twice in final answer.Hence answer will be 2*(sum of weights of all fridges) + (sum of least two weights) * (m-n) . Is this correct ?
•  » » » » » 19 months ago, # ^ |   +1 I believe so, because every fridge MUST contribute 2x their weight. So with leftover edges it must be optimal to connect the lightest fridges.
•  » » » 19 months ago, # ^ |   0 its still 4000! LOL
•  » » 19 months ago, # ^ |   0 If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy, while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Is this a corner case (i.e when of the fridge has weight 0) or there is any other counterexample ? Oh Mike has written a blog on it ! https://codeforces.com/blog/entry/71562
•  » » » » 19 months ago, # ^ |   0 Not a corner case. Just what happens when m > n. The problem basically asks for a graph of minimum cost having each node contained in at least one cycle. Doing a big cycle and adding edges on it is just a greedy solution which is not correct if m > n. However, it is correct for n == m because all nodes should have at least 2 edges so the minimum cost has a lower bound of sum(2 * w[node]). And this is also the answer of the greedy approach.
 » 19 months ago, # |   +9 "If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link"Looks like only positive deltas this round!
•  » » 19 months ago, # ^ |   +3 If people who did poorly withdraw, then this depends on whether the ratings for the rest of us will be calculated based on their absence or presence. If they are ignored when computing our ratings, then we can expect all our deltas to drop, due to our ranking relative to the size of the group diminishing. I hope this does not create a runaway effect, where contestants fear that their rating would drop due to people who did poorly withdrawing, thus withdrawing themselves and exaggerating this effect.
 » 19 months ago, # |   0 If my rating is still increasing after getting affected, will it be unrated for me?
 » 19 months ago, # |   +21 Was the modification in Div2 problem B made to simplify it?
•  » » 19 months ago, # ^ |   0 The edge count was limited to value of N.
 » 19 months ago, # |   +32 Even though I might not gain much rating from this contest, It was indeed educational for me, to work on my weak points.Thank you to all the organizers.
 » 19 months ago, # |   +26 Implementation problems occur now and then. It's a nice contest overall. Kudos to setters.
 » 19 months ago, # |   +9 Too much implementation for a slow coder like me :( Really regret not being able to finish the div2D in time.
 » 19 months ago, # |   +15 Thanks for the contest!
 » 19 months ago, # | ← Rev. 5 →   -18 Deleted .... i am sorry
 » 19 months ago, # |   +2 I didn't see the clarification of div2-B ,because I used "m2.codeforces.com" : ( Does anyone have the same situation as me?　: (
•  » » 19 months ago, # ^ |   0 Then I guess you have all the right to fill that form. If you want it to be unrated for you. :)
 » 19 months ago, # |   +16 I think Div1-B2's Time Limit is a little severe and I got TLE on the system test... How to avoid TLE? My code is following: https://codeforces.com/contest/1254/submission/65368643 (I've only used prime numbers as $k$)
•  » » 19 months ago, # ^ |   +8 I got TLE on pretest because of high constant also. Many of friends did the same
 » 19 months ago, # |   +20 It affected me lots but I want this Round to be Rated for me ^^ From Vietnam with love <3
 » 19 months ago, # |   0 I could not really understand what is the issue with div2 B. what is wrong with the case if(m>n).
•  » » 19 months ago, # ^ |   +3 I don't think there is any problem. They just wanted the problem to get simpler I guess.
 » 19 months ago, # |   0 When will editorials be released?
 » 19 months ago, # |   0 Why my 1st AC submission skipped and counted as a wrong submission?? and minimized my score from 748 to 690?? Please check out this issue.(skipped : 65373327 AC : 65391169) Thanks
•  » » 19 months ago, # ^ |   0 in normal codeforces rounds(except div3) last pretest passed sollution is judged in maintest. You will also get resubmission penalty. But today's div2 B has a special case. Contraint changed during contest. That may be considered if it is applicable for you.
•  » » » 19 months ago, # ^ |   0 Yes. When rejudged, my 1st submission was pretest passed (with constraint m<=n), but CF skipped it in main test. My 2nd submission accepted with a wrong submission penalties. . Details1st submission: 65373327 (Skipped but pretest passed and Accepted in practice)2nd Submission: 65373839 (AC with penalties)
 » 19 months ago, # | ← Rev. 2 →   0 Can someone please tell why this code of div2B is giving TLE? 65391058
•  » » 19 months ago, # ^ |   0 You do a nested loop here for i in range(n): for j in range(i+1,n): Since n is up to 1e5 this is to long.
•  » » » 19 months ago, # ^ |   0 Sorry but n ranges from [2,1000].
 » 19 months ago, # |   +4 Back to codeforces after my cultivation days, I became stronger, go to blue!
 » 19 months ago, # | ← Rev. 4 →   +3 is round rated today?
 » 19 months ago, # |   +77 I think that the testcases in D might be weak. My time is 420ms while I'm able to create test on which my program runs 3790ms.
•  » » 19 months ago, # ^ |   -12 A lot of solutions got TLE on either high-numbered pretests or systests, so they can't be that weak. It's more like your solution happens to not have a strong countertest among these tests. (You can uphack other solutions to find out if it's the case for them too.)
•  » » » 19 months ago, # ^ |   +36 Probably not so many people did it like me and this is strange in my opinion as the solution is very simple.If vertex $v$ has some subtree of size $x$, then ofc. we want to add $(n-x)\cdot d$ to all the vertices in the subtree. As there can be at most $\sqrt{n}$ different sizes of subtrees, we can do the query with $\sqrt{n}$ operations on BIT.Is there anybody who also solved it this way?
•  » » » » 19 months ago, # ^ |   +8 Yeah, I solved it that way and used Segment Tree instead. Just hacked myself. 65387642
•  » » » » 19 months ago, # ^ |   +29 I too solved it this way and am getting TLE because of unnecessary %mod operations.
•  » » » » » 19 months ago, # ^ |