Hello Codeforces!

I'm glad to invite you to participate in Codeforces Round #665 (Div. 2) taking place on 21.08.2020 17:35 (Московское время). The round is rated for users whose rating is lower than 2100.

All problems were mainly created and prepared by me, and I'd also like to thank:

You will be given 6 problems and 2 hours to solve them. The score distribution will be announced closer to the start of the round.

Good luck, and have fun!

UPD1 : Score distribution is 50010001500175025002500.

UPD2 : Editorial

UPD3 : System testing has finished. We hope you enjoyed the contest :)

UPD4 : Congratulations to the winners!

Div.1 (Out of competition)

Div.2

• +717

 » 8 months ago, # |   +96 adedalic coordinating round will be great!
 » 8 months ago, # |   +7 35 hours before the contest and this still isn't on the home page. Hmmm...
•  » » 8 months ago, # ^ |   +20 That's the charm of secondthread.........lol
•  » » 8 months ago, # ^ |   +27 The blog was running on SecondThread ;)
 » 8 months ago, # |   +48 Finally kdjonty31 become tester. congrats ! :3 link
•  » » 8 months ago, # ^ |   +44 Yay! Thanks. LMAO. ᕕ( ՞ ᗜ ՞ )ᕗ
 » 8 months ago, # |   +8 Love it. I keep my fingers crossed for you.
 » 8 months ago, # |   +26 6 tasks for 2 hours and testers from different departments |=> well-prepared competition.Thank you to everyone who took part in its preparation!Successful writing!
 » 8 months ago, # |   -37 Hopefully, the problems are as balanced as the color of testers.
 » 8 months ago, # |   0 will be great round definitely :D
 » 8 months ago, # |   +127 As a Tester, I would like to say that the problems are really interesting, also the statements are short too. Please upvote me now! :)
•  » » 8 months ago, # ^ |   +62
•  » » 8 months ago, # ^ |   +17 Love Short Statements
•  » » 8 months ago, # ^ | ← Rev. 2 →   +27 Spoiler
 » 8 months ago, # |   +92 Hope for strong pretests and not shitty problems from Lemonade255!
•  » » 8 months ago, # ^ |   +76 Hard to hope for the latter
•  » » » 8 months ago, # ^ |   +6 I cracked so hard and wanted to upvote your comment. But me being a man of culture did not want to destroy the auspicious number of upvotes on your comment :)
•  » » » » 8 months ago, # ^ |   +9 it went a little above. Had to downvote it. Sacrifices have to be made for greatness
•  » » 8 months ago, # ^ |   -21 Underrated comment.
 » 8 months ago, # |   +182 Also, the problemset's really nice and concise.
•  » » 8 months ago, # ^ |   +2 Congratulations..
•  » » » 8 months ago, # ^ |   +21 Thanks lol! ＼(^o^)／
 » 8 months ago, # |   +45 As a tester I would say that a good strategy will lead to positive rating.
•  » » 8 months ago, # ^ |   -25 Emphasize on "good strategy" part please
•  » » 8 months ago, # ^ |   +5 i think he meant to say A and B are tricky so try out with C and D.
 » 8 months ago, # | ← Rev. 2 →   +13 August:In India — the month of holidaysIn codeforces — the month of contestsWe already have six contests and three more to go.Thanks Mike and codeforces.
 » 8 months ago, # |   +15 Augustforces
 » 8 months ago, # | ← Rev. 2 →   +13 I thought the next competition was in three days, but suddenly there was a competition tomorrow.I'm looking forward to it!
 » 8 months ago, # |   +37 As a master, I hope you good luck and high rating!
•  » » 8 months ago, # ^ |   +61 As a master, give me contribution, please.
•  » » » 8 months ago, # ^ |   +10 I gave you contribution.
•  » » » » 8 months ago, # ^ |   +31 As a master,saying something is better than contributing something.
 » 8 months ago, # | ← Rev. 2 →   +4 WEll, How many contest holds in every month, at least ??
 » 8 months ago, # |   +76 As a tester i advice you to read all problems :)
 » 8 months ago, # | ← Rev. 7 →   -30 is it rated?
•  » » 8 months ago, # ^ |   -18 ???
•  » » » 8 months ago, # ^ |   +7 The round is rated for users whose rating is lower than 2100.Can you read the announcement ?
 » 8 months ago, # |   +5 This round is gonna be an amazing
 » 8 months ago, # |   +184
•  » » 8 months ago, # ^ |   0 I can relate xD
•  » » 8 months ago, # ^ |   +23 I can feel you bro, you can check my profile I've reached 1590+ many times but never crossed 1600, 1600+ rating is still a dream for me
•  » » » 8 months ago, # ^ |   +6 I hope You’ll reach blue after This round
•  » » » 8 months ago, # ^ |   +84 Are you a digon?
•  » » » » 8 months ago, # ^ |   +29 Oh boy! so we have a monogon here too it seems
•  » » » » 8 months ago, # ^ |   +13 Where do you learn these weird polygons ? I never came across these in my school/college.
•  » » » » » 7 months ago, # ^ |   0 But can monogon be also belong to polygon? :P
•  » » » 8 months ago, # ^ |   +10 You are at 1599 right now, coincidentally, your profile picture also has a point on the border of the circle.
•  » » » 8 months ago, # ^ |   +18 I'm in dilemma whether to wish you luck or not. If you cross 1600, your graph will lose the charm.
•  » » 8 months ago, # ^ |   0 This same thing happened to me also
•  » » 8 months ago, # ^ |   0 I can relate bro, I was closer than you xD
 » 8 months ago, # | ← Rev. 6 →   +30 Hope for strong pretests.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +287 protests are really strong these days
•  » » » 8 months ago, # ^ |   -7 what is this meme ?
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   +56 It's Pretest, not Protest. — the first comment hoped strong protests.
•  » » » 8 months ago, # ^ |   -27 Русские поймут =)
•  » » » » 8 months ago, # ^ |   +4 Понять-то они поймут, но здесь не политический митинг.
 » 8 months ago, # |   +180 As a tester, this contest made me lose my will to live.
•  » » 8 months ago, # ^ |   0 That makes me worried!
•  » » 8 months ago, # ^ |   +1 I hope that doesn't happen to the contestants after the contest..
•  » » 8 months ago, # ^ |   +13 But it did not kill your craving for contribution.
 » 8 months ago, # |   0 Glad to see specialists are also being accepted as problem setters. :)
•  » » 8 months ago, # ^ |   +13 *testers
•  » » » 8 months ago, # ^ |   +5 You were a tester yourself weren't you?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +5 YES Contigo KHALIYAR
 » 8 months ago, # |   0 Can I ask a question? What type of problems are you best at solving?
•  » » 8 months ago, # ^ |   +62 I wish I could say "relationship"
 » 8 months ago, # |   +4 ![ ]()
 » 8 months ago, # | ← Rev. 2 →   -42 Korean contest! I love it! 반가워요 :)
•  » » 8 months ago, # ^ |   -27 오 한국말이 되네요
•  » » 8 months ago, # ^ |   -6 south or north ?
•  » » » 8 months ago, # ^ |   -20 South! i've never seen North Koreans in codeforces yet
•  » » » » 8 months ago, # ^ |   +4 There are north Koreans in the ranking though.
 » 8 months ago, # |   +15 As a tester I recommend you to read all problems and wish you big positive deltas!!!
•  » » 8 months ago, # ^ |   0 Thanks, really did helped as I skipped B to solve C first
 » 8 months ago, # |   -6 hey bro nice nick
 » 8 months ago, # |   -8 Let's hope the problem statements can be as short as this announcement.
 » 8 months ago, # |   -9 Good luck everyone ;-)
 » 8 months ago, # |   0 Am I the only person who finds the username Lemonade255 weird? Its like saying "Hi, I am Anus No. 1373"P.S No offense intended though
•  » » 8 months ago, # ^ |   +29 Lets just hope that shit doesn't come out.
 » 8 months ago, # |   0 All hail to you brother! Keep rocking! kdjonty31
•  » » 8 months ago, # ^ |   0 LMAO, Thanks! ;)
 » 8 months ago, # | ← Rev. 2 →   -21 [..]
 » 8 months ago, # |   -31 wow! there aren't too many testers...
 » 8 months ago, # |   -89 Seeing the handle name anus, I first thought it's an Indian round! The name anus sounds like Indian though!
 » 8 months ago, # |   -70 Not as a tester, give me contribution
 » 8 months ago, # | ← Rev. 2 →   +31 I had to post this, for 71 minutes the number of comments hadn't changed, a conspiracy.....???
•  » » 8 months ago, # ^ |   +16 Haha funi sex number i laughed, came, and had an epileptic seizure upon seeing this post. It is in fact so hilarious that after I showed it to my entire family they nearly died from asphyxiation because they couldn't stop laughing at this quirky post. I am currently at my mother's funeral, and the priest is unable to keep a straight face when he reads about the cause of her death.I'm just happy my mom died with a smile on her face :)
 » 8 months ago, # |   +19 Just asking, what's the point of the 'x' button if I can't remove them? pic
•  » » 8 months ago, # ^ |   +11 Just asking, Why do you want to remove these?
•  » » » 8 months ago, # ^ |   0 Why not? It's good to have a choice and I'd personally feel better after removing some or all.
•  » » 8 months ago, # ^ |   +16 You could remove them if you didn't make any submission.
 » 8 months ago, # | ← Rev. 2 →   +14 I am scared about 5 page long queue . I hope MikeMirzayanov will fix it before the contest .UPD — It is fixed now !!
•  » » 8 months ago, # ^ |   +6 Not 5 pages but hundreds of pages .. no submissions are judges for last 4 hours(which i saw ).
•  » » 8 months ago, # ^ |   +3 Where can you see the queue?
•  » » » 8 months ago, # ^ |   0 In the NavBar above — Problemset->Status.
•  » » » » 8 months ago, # ^ |   0 Got it. Thanks.
 » 8 months ago, # | ← Rev. 2 →   -22 As a tester, this contest will be interesting and entertaining. Thanks, Codeforces.
 » 8 months ago, # |   -24 Donald Trump.
 » 8 months ago, # |   +11 Only two hours left before the contest, score distribution should be published. Lemonade255
 » 8 months ago, # | ← Rev. 6 →   -28 wishing all coderforces family luck and fortune . May god bless you all @Erica
•  » » 8 months ago, # ^ |   +9 I feel most of the downvotes are from newbies and pupils
•  » » » 8 months ago, # ^ |   0 I also guess so , bcuz Good coders always enjoy everything ... They are cool people
 » 8 months ago, # | ← Rev. 7 →   -30 .
•  » » 8 months ago, # ^ |   +3 This meme isn't new(actually, it's common), so it's likely to get downvoted.
•  » » » 8 months ago, # ^ |   0 okay thanks , I removed it. I didn't know that, As I am new on Codeforces.
 » 8 months ago, # |   -31 WOW! E=F, WILL TRY BOTH!
 » 8 months ago, # |   +47
•  » » 8 months ago, # ^ |   0 Hell yeah..
 » 8 months ago, # |   0 Yeah!
 » 8 months ago, # |   +16 speedforces
 » 8 months ago, # |   +1 I suppose everyone here wants to learn. So the test cases must help us to think regarding the problem.
 » 8 months ago, # |   0 Very nice set of questions. :-)
 » 8 months ago, # |   +4 This is how you make a round.
 » 8 months ago, # |   0 One of the most stable and decent question sets.
 » 8 months ago, # |   0 When I'm sure my logic is correct but WA on pretest 2 (x4) @@
•  » » 8 months ago, # ^ |   0 Problem 4
 » 8 months ago, # |   +5 Problems are good but somehow I choked so hard on B
•  » » 8 months ago, # ^ |   +2 even i felt C was easier than B
•  » » » 8 months ago, # ^ |   0 I made B & C, but couldn't do A. laughing after looking A's solution
•  » » 8 months ago, # ^ |   +9 At least you're not choke hard on "D" *IYKWIM
 » 8 months ago, # |   +26 is it educational round or what? why problems havent any idea
•  » » 8 months ago, # ^ |   -17 What do you mean?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 It's most possible boring math problems.
•  » » » 8 months ago, # ^ |   -13 Problem D which decided the rank of majority was standard re-rooting. And I guess problem F was some modification of segtree but I haven't looked very seriously into the problem.
•  » » » » 8 months ago, # ^ |   +9 D was greedy and not re-rooting.
•  » » » » » 8 months ago, # ^ |   0 Of course it was. But at least in my solution, I used re-rooting to find edge weights.
•  » » » » » » 8 months ago, # ^ |   +12 You could have done it like this- if (not visited v) { dfs(v) number_of_paths_including_this_edge = size[v] * (n - size[v]); } 
•  » » » » » » » 8 months ago, # ^ |   +8 Ah yes of course. #Always_ready_to_overkill
•  » » 8 months ago, # ^ |   -28 +1, I understand that maybe this problems can be Educational for Div2 but they seem uninteresting.. :(
•  » » » 8 months ago, # ^ |   0 you come back please !!
•  » » » 8 months ago, # ^ |   +8 I prefer this problem set. Only one I really thought was too boring was D, but better than having non-diverse round. ABC were even an ur style problems...
 » 8 months ago, # | ← Rev. 2 →   +5 For me A was nearly as difficult as DWill have to check the editorial to understand it lol
•  » » 8 months ago, # ^ |   0 2b+k=n find b
 » 8 months ago, # |   +4 Imo C was easier than both A & B.
•  » » 8 months ago, # ^ |   +1 can you give a hint ?
•  » » » 8 months ago, # ^ |   0 Just sort the original array and check to see which ones are out of order, if all the ones out of order are divisible by the minimum element the answer is yes otherwise no.
•  » » » » 8 months ago, # ^ |   0 I dont think sorting the array fits under the given constraints ( N<= 10^5 , T <= 10^4)
•  » » » » » 8 months ago, # ^ |   0 There is another constraint about max sum of N over all testcases.
•  » » » » » » 8 months ago, # ^ |   +1 SHIIIIIIIIIIIIT
•  » » » » 8 months ago, # ^ |   0 What is wrong in this https://codeforces.com/contest/1401/submission/90583034
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 You need to compare objects using equals, not !=, even if it is Integer objects.
•  » » » » » » 8 months ago, # ^ |   0 Thanks bro, But other answers using != are accepted
•  » » » » » » » 8 months ago, # ^ |   0 Maybe they use int[] instead of List ?
•  » » » » » » » » 8 months ago, # ^ |   0 Yes
•  » » » » » » » » 8 months ago, # ^ |   0 Just curious to know why it runs well on 7 5 2 2 4 but not on 1120 707 16
•  » » » » » » » » » 8 months ago, # ^ |   0 I don't know. Numbers smaller than 128 are somewhat special in Integer class, because Integer.valueOf(int) will return same Object for int<128. Maybe somehow that comes into play.
•  » » » 8 months ago, # ^ |   0 Make a copy of the given array and sort it. Iterate from 0 to n-1 and check if a[i] != b[i], if it is different and a[i] % minValue != 0 then there is no solution.
•  » » 8 months ago, # ^ |   +1 and I can't solve C, I'm too bad :(
 » 8 months ago, # |   +22 After getting 4 WA in D, here are the cases to take care of. Don't take mod of last greatest values when m > n — 1 and insert in list because mod might make the value smaller. Instead take product of those and add to our answer ASAP. While computing how many times edge can be part of various paths, don't forget to take it as long long and also list as long long. And don't mod because again value might become smaller.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 oh fuck I think I fell victim to both of these... RIP
•  » » 8 months ago, # ^ |   0 Oh wow, I think now I know why my solution get WA
•  » » 8 months ago, # ^ |   0 Shit..Too bad I couldn't figure out during the contest :(
•  » » 8 months ago, # ^ | ← Rev. 4 →   0 for point 1, how about sorting p array first, then assigning the values, that way the array is always in sorted order, and no need to care of mod making the value smaller.
 » 8 months ago, # |   0 Can D be solved by the greedy method?
•  » » 8 months ago, # ^ |   +11 Yes
•  » » 8 months ago, # ^ |   +11 Yes, I think the author's solution bases on Greedy approach
•  » » 8 months ago, # ^ |   0 Yep, greedily assign the maximum weight to the most used edge (found using dp to get size of subtrees)
•  » » 8 months ago, # ^ |   0 I am also interested to know.
•  » » 8 months ago, # ^ |   0 Thanks, so it must be some silly mistake
•  » » 8 months ago, # ^ |   0 hint — DFS + SORT
•  » » » 8 months ago, # ^ |   0 Don't give hint , either tell full solution or don't , we can wait for editorials .What you are telling everyone knows.
•  » » » » 8 months ago, # ^ |   +6 My approach — find number of times an edge is coming in a path. (n1 elements)--(edge)--(n2 elements) => number of times = n1*n2 (I found n1 = number of elements in subtree of n1 and n2= n — n1)and then fill max factor in maximum edge. my sol — 90611208 I have used iterative DFS, because I thought I might get TLE. Sorry to hurt you feeling Jastin
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 My feelings are already dead . Just see my contribution . Any way i found the solution and it's same as yours .Thanks for helping me to verify .
 » 8 months ago, # |   +3 Completely exhausted after the contest. I got stuck in the 4th problem. There may be some property that will be used. A lot to learn this from contest. A NICE CONTEST with short problem statements!!
 » 8 months ago, # |   +3 How to solve D :(
 » 8 months ago, # |   +51 Wasted all the time with problem D pretest 5, finally I found that i am sorting after taking the numbers module mod :(
•  » » 8 months ago, # ^ |   +11 Same here :(
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +30 At least you realized it during contest ._.
•  » » 8 months ago, # ^ |   +21 Holy shit, I'm dumb af
•  » » » 8 months ago, # ^ |   +18 LOL so glad to know I'm not alone
•  » » 8 months ago, # ^ |   +7 I had the same problem too but wasn't able to notice this. I even solved E mentally and would probably have had time to implement it if it weren't for this mistake. :(
•  » » » 8 months ago, # ^ |   +15 I should have quit it too, but it's really hard to leave a problem solved by about 2K users and go to other harder problem :(
•  » » 8 months ago, # ^ |   0 I've done this but still got WA5 90613994 :(
•  » » » 8 months ago, # ^ |   +3 z.push_back((n - s[u]) * s[u]);Overflow will happen here, as both $n$ and $s$ are declared int.
•  » » » » 8 months ago, # ^ |   0 lol, thank you!
•  » » 8 months ago, # ^ |   0 Thanks for this comment, wasn't able to find the bug in my code until i saw this
•  » » 8 months ago, # ^ |   0 ahhhh thanks! after 22 times getting WA on test 5 i just saw your comment. god damn it :(
 » 8 months ago, # |   -54 Video Tutorial for D. Maximum Distributed Tree
 » 8 months ago, # |   +1 Problems, at least problem statements, were too mathy/formal to my taste
•  » » 8 months ago, # ^ |   +14 It was pure math homework contest. I am surprised as how much people seems to like that kind of problems.
•  » » » 8 months ago, # ^ |   -13 WitchOfTruth and spookywooky if you want to be good at competitive programming , trust me soling math problems will help you a lot .
•  » » » » 8 months ago, # ^ |   0 Math problems per se may not be that bad, but here we had A-B-C three math problems in a row, And then D, which was not math, but the problem statement was so dry and full of formulae that it felt like one.
 » 8 months ago, # |   +17 Great contest...
 » 8 months ago, # |   +33 A round with two data-structure problems!!
•  » » 8 months ago, # ^ |   0 And both of them will most likely have difficulty 2000+. So for most of the real div2 participants there were no ds problems.
 » 8 months ago, # |   0 Explain solution for d please?
 » 8 months ago, # |   0 F — press segment tree to win
•  » » 8 months ago, # ^ |   0 But how to do? Lazy-tag can't work!!
•  » » » 8 months ago, # ^ |   +6 Maintain left and right childs and a tag for each level if they have to be swapped. Reverse operation is same as swapping at all levels below current level.
•  » » » 8 months ago, # ^ |   +6 Observation — order of the operations doesn't matter, so just write amount of each operation for each k. So when pushing from vertex, just look at the number of operations for the current level k. Swap is just swapping children, and Reverse can be done lazily.
•  » » » » 8 months ago, # ^ |   +6 Alternatively, notice that all operations are xoring the indices and segment tree works really nicely with xor.
•  » » » » 8 months ago, # ^ |   0 Is it obvious?During the contest I doubted whether the order matters .:(
 » 8 months ago, # |   +1 What was the logic behind C
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 The numbers which are misplaced must have their common gcd equal to the smallest element in the array. Edit: Just have to check that all misplaced numbers are divisible by the smallest number or not.
•  » » 8 months ago, # ^ |   0 Consider the sorted list. Compare to actual list. In the places which differ, check if modulo min of the list.
•  » » 8 months ago, # ^ |   0 you can always sort the array as long as all elements which you want to move is multiple of min element of array. because if that's not the case, gcd(element,min element)!=min element. so you can't change its position.
•  » » » 8 months ago, # ^ |   0 Shit!!!Got where my logic was wrong.Btw Thnax!!
 » 8 months ago, # |   0 Could E be solved using a linesweep and avl tree?
 » 8 months ago, # |   +26 Today for the first time I had to implement Segment Tree from scratch lol.
 » 8 months ago, # |   +24 lol!
•  » » 8 months ago, # ^ |   +12 Yes problem A took me 11 minutes!!
•  » » 8 months ago, # ^ |   0 Solved B & C, couldn't solve A :P
 » 8 months ago, # |   0 I'm curious that how one would solve C? if the gcd of two element of array is not needed to be the minimum element of array.
•  » » 8 months ago, # ^ |   0 Consider the sorted list. Compare to actual list. In the places which differ, check if modulo min of the list.
•  » » 8 months ago, # ^ |   0 I was stuck with this logic. But say array is 2, 8, 4 and you want to swap (8, 4), you can just swap (2, 4) (8, 2) and (4, 2) again.Basically 4, 8, 2 -> 4, 2, 8 -> 2, 4, 8.
•  » » 8 months ago, # ^ |   0 if gcd can be anything (i.e. no conditions on gcd) then according to me its always possible to sort the array, just like swapping every possible pair.
•  » » » 8 months ago, # ^ |   +1 so true..then the problem will not even be considered as prob A
•  » » » 8 months ago, # ^ |   +1 no I didn't mean that gcd can be anything it's like that the gcd should belong to the array but it's not need to be the minimum element of the array.
•  » » 8 months ago, # ^ |   0 if you have one element whose gcd is always equal to min with others (like — minimum number) and those numbers if gcd != min are in right position than you can always arrange that array. ex — 2, 6, 5, 4if min = 2, and you want 4 to be in 2nd position, but gcd(6, 4)!=min, then you canswap — 2-6 => 6, 2, 5, 42-4 => 6, 4, 5, 22-6 => 2, 4, 5, 6
 » 8 months ago, # | ← Rev. 2 →   0 what's wrong in this? https://codeforces.com/contest/1401/submission/90616241 (problem D)
•  » » 8 months ago, # ^ | ← Rev. 2 →   +1 Test case: 1 4 1 2 2 3 3 4 5 2 3 5 7 11 Correct answer: $1555$Your answer: $95$
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Why the answer is 95? we give the following value: 11*7*5 in the edge between 2-3, 3 in the edge between 3-4, 2 in the edge between 1-2; then answer should be 4*(11*7*5) + 3*(3) + 3*(2) = 1555; Correct me where I am wrong!
•  » » » » 8 months ago, # ^ |   0 Yes, the correct answer is 1555, but instead of do 4*11*7*5 i did 4*11+4*7+4*5
•  » » 8 months ago, # ^ |   0 you should consider the cases in which m is larger than n-1.
 » 8 months ago, # |   0 For C, I made a vector of elements which had gcd(minOfArray, element) = minOfArray. sorted them and then placed them again in the array in the places where the above condition holds in increasing order. Then checked if array is sorted.Can't understand the fault in the logic!!
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 4 2 6 7 8 5- so your vector is {4,2,6,8} sort : {2,4,6,8} place : 2 4 6 7 8 5 is this what you did ?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Yah EDIT: Actually logic is correct, I declared the minElement globally. I was doing it for the first case. Forgot to shift it inside the loop.
 » 8 months ago, # |   +7 Like if you sorted after taking mod
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I even didn't do that stil got WA. Please help to debug.UPD: No need i got what i did wrong. Spoiler#include #include #include using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define pii pair #define pll pair #define all(x) x.begin(), x.end() #define rep(a, b, c) for (int a = b; a < c; a++) #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m)) #define pb push_back #define fi first #define se second #define INF 1000000000000000000 #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); # define M_PI 3.14159265358979323846 const int maxx = 1000002; const int mod2 = 987654319; const int maxlog = 20; const ll mod = 1000000007; const int mod3 = 998244353; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; ll prime[maxx]; void make() { prime[1] = 1; rep(i, 2, maxx) { if (!prime[i]) { for (int j = i + i; j < maxx; j += i) prime[j] = 1; } } } ll power(ll x, ll y) { ll res = 1; while (y) { if (y & 1) res = (res * x) % mod; y >>= 1; x = (x * x) % mod; } return res; } vector> g; ll arr[maxx], par[maxx]; int dfs(int u, int p) { int cnt = 1; par[u] = p; for (auto& to : g[u]) { if (to != p) { cnt += dfs(to, u); } } arr[u] = cnt; return cnt; } void solve(int test) { int n; cin >> n; g = vector>(n, vector()); vector edges; rep(i, 0, n - 1) { int x, y; cin >> x >> y; x--, y--; g[x].pb(y); g[y].pb(x); if (x > y) swap(x, y); edges.pb({x, y}); } int k; cin >> k; vector p(k); rep(i, 0, k) cin >> p[i]; dfs(0, -1); vector paths; map, ll> mp; // rep(i, 0, n) { // for (auto& to : g[i]) { // int u = i, v = to; // if (u > v) swap(u, v); // ll a1 = 0, a2 = 0; // a1 // } // } for (auto& to : edges) { int u = to.fi, v = to.se; ll a1 = 1, a2 = 1; for (auto& t : g[u]) { if (t != v) { if (t == par[u]) a1 += n - arr[u]; else a1 += arr[t]; } } for (auto& t : g[v]) { if (t != u) { if (t == par[v]) a2 += n - arr[v]; else a2 += arr[t]; } } //cout << u << ' ' << v << ' ' << a1 << ' ' << a2 << '\n'; mp[to] = (a1 * a2); } for (auto& to : mp) paths.pb(to.se); sort(all(paths)); reverse(all(paths)); //for (auto to : paths) cout << to << ' '; ll ans = 0; sort(all(p)); reverse(all(p)); rep(i, 0, n - 1) { if (i + 1 > k) { ans += paths[i] % mod; if (ans > mod) ans %= mod; } else { ans += ((paths[i] %mod) * p[i]) % mod; if (ans > mod) ans %= mod; //cout << paths[i] << ' ' << p[i] << ' ' << ans << ' '; } } cout << ans % mod << '\n'; } int main() { IOS ifstream ifs; ofstream ofs; ifs.open("input.txt"); ofs.open("output.txt"); //make(); int tt = 1, test = 1; cin >> tt; while (tt--) { solve(test); test++; } } 
•  » » » 8 months ago, # ^ |   0 What if m>n-1
•  » » » » 8 months ago, # ^ |   0 Thanks, I wish I would have realized this during the contest.
 » 8 months ago, # |   0 I kept on getting RTE on test 6 of D. Thanks a lot to python!https://codeforces.com/contest/1401/submission/90611250
 » 8 months ago, # | ← Rev. 3 →   0 Can anyone tell who user SorryNotSorry (who got the first rank) might be by his coding style?
 » 8 months ago, # |   +1 GCD is resounding in all directions ——when i solved D but not C and only 30 mins left
 » 8 months ago, # |   -8 I am beginner here on codeforces can anybody tell me if my submission will be counted, I submitted my file at the last moment and it ran on the pretests and showed 'pretests passed' after which the time ended, will my code be further evaluated so as to get accepted?
•  » » 8 months ago, # ^ |   0 yes it will be further evaluated, if you submitted before the contest ended.
•  » » » 8 months ago, # ^ |   0 thank you!
•  » » 8 months ago, # ^ |   0 Yes
•  » » » 8 months ago, # ^ |   0 thank you!
 » 8 months ago, # |   -8 Solved F first and didn't have enough time to debug E :(
 » 8 months ago, # |   0 have you left a question because you just don't want to type that?
 » 8 months ago, # |   0
 » 8 months ago, # |   0 Without Reverse and Swap last problem is easy to solve)
 » 8 months ago, # |   +16 Thanks for the good samples in F though
 » 8 months ago, # | ← Rev. 2 →   +6 Can anybody tell me why my solution for D is failing on pretest 5? It looks like the logic is correct, comparing it to people who got it accepted. Submission link
•  » » 8 months ago, # ^ |   +3 Alright, so I realised my mistake, one of the arrays I had sorted after taking modulo. I crie. TT
 » 8 months ago, # |   +4 What is the correct approach for problem E? I guess there would be some magical trick.
•  » » 8 months ago, # ^ |   +4 wingardium leviosa
•  » » 8 months ago, # ^ |   0 are you really Dr Vishal Gupta from pilani?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +5 Yes indeed. Why should students have all the fun.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 indeed.I was just little surprised to see you here after so long, also because you are only prof I know here. enjoy :)
 » 8 months ago, # | ← Rev. 2 →   0 Please help!Can anyone tell me why I'm getting TLE on problem D? I switched to c++ from python recently and I really thought these things won't happen anymore :<< n-1){ while (p.size() != n-1){ ll tmp = p.back();p.pop_back(); p.back() = (p.back() * tmp) % NUM; } } else { while (p.size() != n-1){ p.pb(1); } } sort(all(p)); vll cnts; int size = dfs(0,-1,adj,n,cnts); sort(all(cnts)); int total = 0; FOR(n-1){ cnts[i] %= NUM; } FOR(n-1){ total = (total + (cnts[i] * p[i]%NUM)) % NUM; } print((total + NUM) % NUM); } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef _DEBUG freopen("q1.input", "r", stdin); #endif int t = 1; read(t); FOR(t){ solve(i+1); } return 0; } 
•  » » 8 months ago, # ^ |   0 I think you should put vvi &adj instead of vvi adj in dfs()
•  » » » 8 months ago, # ^ |   0 You think that one copy made all the difference? Oh.. As I'm writing this comment, I realize every dfs copies it, because it's recursive :|Well it was the first dfs problem I solved since switching to C++. There have to be some bumps in the road I guess.
•  » » 8 months ago, # ^ |   0 You need to declare vectors given as parameters as references. Here, you copy the array adj each time dfs is called.
 » 8 months ago, # | ← Rev. 2 →   0 For problem D, do we have to greedily arrange the m factors on each edge based on which edge is most visited?
•  » » 8 months ago, # ^ |   0 Yes!! But how will we know which edge is visited most? I was stuck in this part only!!
•  » » » 8 months ago, # ^ |   0 It will be equal to number of times a particular edge xan be used in a path from u to v which will eventually the product of number of elementsin the subtree and other the nodes As that edge will come only if you have a node other than the nodes in the subtree and the other node is in the subtree.
 » 8 months ago, # |   0 What's wrong with my solution for C? 90603416 I created a copy of the given array and sorted it. Next, for each index, if the elements in the original array and the sorted one aren't equal, I checked if their gcd was equal to the minimum element. If it is different, I print "NO", else "YES".
•  » » 8 months ago, # ^ |   0 even I did the same :(
•  » » 8 months ago, # ^ |   +3 If the arr is 2, 8, 4, then the sorted array is 2, 4, 8. GCD of 4, 8 isn't 2, but it's still possible to fix this. Swap 2 with 4, swap 2 with 8, swap 2 with 4.
•  » » 8 months ago, # ^ |   0 Try the test case consisting of 3 elements, 16 2 8. Your code will fail. Correct answer is "YES". __
•  » » 8 months ago, # ^ |   0 You need to check if it is multiple of min element, because that is enough. Every two multiples can be triple-swaped with each other using the smallest element.
 » 8 months ago, # |   -30 I felt like a math exam, didn't like this contest at all
 » 8 months ago, # | ← Rev. 2 →   +24 Amazing round ! Clear statements with no stories, hopefully strong pretests. This has to be one of the least constructive rounds I have seen in recent times on CF :)EDIT: And fast editorial as well :)
 » 8 months ago, # |   +17 Great contest :) No shitty stories
 » 8 months ago, # |   0 what a contest!!
 » 8 months ago, # |   0 In C, i just took all elements which were not in the correct place after sorting in another array arr2, and found the gcd of arr2. whats wrong in this??
•  » » 8 months ago, # ^ |   0 If we have the array = [2,8,4]. Your gcd array will be [8,4] and its gcd is 4 which isn't equal to 2. But still, the array can be arranged in non-descending order.
•  » » 8 months ago, # ^ |   0 First: Find minimum element.Second: Find elements that not in their place.Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"
 » 8 months ago, # |   +16 Query Party!
 » 8 months ago, # |   0 Stuck in Problem A. Orz
•  » » 8 months ago, # ^ |   +10 I won't tell you how to solve it directly, but I can give you 3 similar problems to today's C:
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 my solve: we can never move elements, which are not divisible by min_of_array, so we should check if they are in their "sorted" place. Lets call other elements divisible. after that we can always sort the array with this logic: gcd(min_of_array, any divisible) = min_of_array, with that we can swap for ex min_of_array with the last element and then with min_of_array with max, with that iteration we decreased size of our array to sort by one (we sorted biggest divisble in its right place) and can continue with that logic.
•  » » » 8 months ago, # ^ |   0 also good problem to practice this kind of thinking is: Replace by MEX — https://codeforces.com/problemset/problem/1375/D
•  » » 8 months ago, # ^ |   0 First: Find minimum element.Second: Find elements that not in their place.Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"By "swap any 2 elements using minimum element as a buffer" I mean this. U have a1 a2 ... aN . A1 is minimum element (aM), GCD(aM,aX) == aM. So, if we want to swap aX and aY. We can do like this:[aM,aX,aY]->[aX,aM,aY]->[aX,aY,aM]->[aM,aY,aX]
 » 8 months ago, # |   0 Could anyone help me,why is my solution for D is TLE. I think my answer is perfect. 90615633
•  » » 8 months ago, # ^ |   0 pass the "tre" by reference in dfs function.Because in your code the vector is copying itelf everytime dfs is called
•  » » » 8 months ago, # ^ |   0 Thank you.
•  » » 8 months ago, # ^ |   0 Had the exact same problem. Need to pass 'tre' as a reference (or do like all the experiences ones and declare it as a global variable).Every time you call 'dfs' you copy the whole vector.
 » 8 months ago, # |   0 This was the first time I solved 2C and still am able to get a +3 according to predictor. :(
 » 8 months ago, # |   0 Can someone please tell me why this is giving RTE. link
•  » » 8 months ago, # ^ |   +4 In dfs function you are using int val = sub[x] * (n — sub[x]); but you shoud use long long int as it (sub[x] * (n — sub[x])) may exceed the limits of int
•  » » » 8 months ago, # ^ |   0 int is already defined long long in macros :)
•  » » » » 8 months ago, # ^ |   +1 Okay, I didn't see that earlier. But now I have found the mistake. for(int i = n — 1; i >= 0; i--){ cal[i] %= mod; factors[i] %= mod; int temp = (cal[i] * factors[i]); temp %= mod; ret += temp; ret %= mod; }In above for loop you should start i with (n-2) not with (n-1)
•  » » » » » 8 months ago, # ^ |   0 okay got it...Thanks. But why my code didnt fail on pretest 1?
•  » » » » » » 8 months ago, # ^ |   0 I am also wondering, why it was not failing on pretest1. But I didn't came up with any answers.
 » 8 months ago, # | ← Rev. 3 →   0 Can anyone detect why this code gave WA on pretest 2 in problem D , I am not able to understand the issue in it. 90570026PS:- Finally done , I was missing case when m>n!
 » 8 months ago, # |   0 Off 5 blue participants in my friendlist 4 did not submit any solution. And the one who did won't be blue next contest.
•  » » 8 months ago, # ^ |   0 how to check who took part and didn't submit?
•  » » » 8 months ago, # ^ |   +3 On the contest page you can click the number which shows the participants to get the list of all registered ones. Then there is a friends button.Same friends button is in standings table.
•  » » 8 months ago, # ^ |   0 Yeah and they are the people who will fail when time comes due to lack of courage. I have many a times solved first problem in > 1 hour and then B,C,D in < 1 hours . If you really love CP you won't see al these things.
 » 8 months ago, # |   0 solved C but got stuck at B :(
 » 8 months ago, # |   0 Any small hints for problem E?
•  » » 8 months ago, # ^ |   0 The editorial is the smallest hint as well as the complete answer .
 » 8 months ago, # | ← Rev. 2 →   0 problem c: n=5. 8 8 4 4 2 why the sample is correct? (this smaple printed "yes" in some codes)
•  » » 8 months ago, # ^ |   0 Because 8, 8, 4, 4 are all divisible by 2 (the minimum), so they can easily be swapped to create a sorted array.
•  » » » 8 months ago, # ^ |   0 ok,i think so.I get it.Thank you.
•  » » 8 months ago, # ^ |   0 For C , If input is n = 52 12 8 32 24min = 2, gcd = 4, My ans : "YES" passed, actual ans should be "NO"
•  » » » 8 months ago, # ^ |   0 Answer is YES. cause using 2 you can swap any element .you have to find just 2 element gcd not all..
•  » » » » 8 months ago, # ^ |   0 you can swap if two elements if their gcd is equal to min element.
 » 8 months ago, # |   +4 Did anybody else feel this contest was so smooth? I mean.. I got my "Wrong answer on pretest 2" the second after I made my submission. Kudos to the platform! Jokes apart, it was nice problem set!! Thanks overall!!
 » 8 months ago, # |   +15 SO, what does the "1-s" mean ??? I didn't get it, so I lose Problem D. Can't you just write directly " 1s " or " '1's " ?
•  » » 8 months ago, # ^ |   0 By the way, the other problems are good. Thanks for your contest.
 » 8 months ago, # |   +3 Thank you very much for uploading editorial this fast!!
 » 8 months ago, # |   +54 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
 » 8 months ago, # |   0 Those who are getting WA in D like me m can be greater then n , it have to be considered! I got WA in 2 facepalm!
 » 8 months ago, # |   +3 During the contest, I submitted solution for F, but quickly realized that it works in $O(2^n \cdot q)$, though it was easy to fix so I resubmitted. But then I submitted initial slow solution after the contest again, and it passed systests! So I quickly hacked it 90619845 But I'm quite disappointed that systest didn't manage to break my initial slow solution(
 » 8 months ago, # |   -10 when my rating was increased in last contest they updated it afer 6 hours or more and today my rating was going to decrease they updated it inside one hourwhy?
»
8 months ago, # |
-16

Hello I've passed pretest 1 of first problem of this round, but failed on pretest 2. May I know where was I wrong? ~~~~~

include<bits/stdc++.h>

using namespace std;

int main(){ int no_of_times; cin>>no_of_times;
for(int l = 0;l < no_of_times;l++){ int n,k; cin>>n>>k; if(n == 1 && k == 1){ cout<<1<<"\n"; } else if(n == 1 && n > k){ cout<<1<<"\n"; } else if(n > k){ if(n%2 == 0 && k%2 == 0){ cout<<0<<"\n"; } else if(n%2 == 0 || k%2 == 0){ cout<<1<<"\n"; } else{ cout<<0<<"\n"; } } else{ cout<<(k-n)<<"\n"; } } } ~~~~~

 » 8 months ago, # |   0 What becomes problem C if instead of having the rule "you can swap elements if their gcd is equal to the minimum element of the array" you have "you can swap elements if their gcd is equal to x" where x can be any number (in particular x may not be in the array) ?
 » 8 months ago, # |   +3 My screencast of the round, where I start to give up on templates, horribly screw up D, continue my curse of never full-solving, and explain solutions for A-E
 » 8 months ago, # | ← Rev. 2 →   +11 I have a new record !!! 2000+,I am waiting for your congratulations!!!!
•  » » 8 months ago, # ^ |   0 Congrats!
•  » » » 8 months ago, # ^ |   +19 Congrats!
•  » » 8 months ago, # ^ |   +1 congrachulasunzz
 » 8 months ago, # | ← Rev. 2 →   +7 No announcement for any problems in the round is the best evidence to prove an expilcit and clear round.
 » 8 months ago, # |   0 Amazing Problem statements. Loved problem A very much. Fantastic round!!! Kudos to authors and Mike for fantastic round.
 » 8 months ago, # |   +1 It was unrated for me — rating change 0. lol
•  » » 8 months ago, # ^ |   +3 Same as 72 other people
 » 8 months ago, # | ← Rev. 2 →   0 Problem C has nothing to do with the greatest common divisor. We only need to consider whether each number not in the correct position can be divided by the smallest number in the sequence.
•  » » 8 months ago, # ^ |   +1 You are saying that it has nothing to do with gcd just because you figured out how to solve it without explicitly finding any gcd?
 » 8 months ago, # | ← Rev. 2 →   0 for problem A2∗x=a+kFor what minimum value of a , x= 0does the above equation has any mathematical formula?my code
 » 8 months ago, # | ← Rev. 2 →