### Keewrem's blog

By Keewrem, 2 weeks ago,

Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round #701 (Div. 2), which will be held on Feb/12/2021 17:50 (Moscow time). This round will be rated for participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them.

We would like to thank

Last but not least, we also want to thank the testers: armyalpaca, dario2994, davi_bart, DeadlyCritic, franfill, HIS_GRACE, kclee2172, Lorenzo_Ferrari, Manik, mattysal, namanbansal013, Osama_Alkhodairy, Prakash11, rocks03, Shusaku, simpatine, stefdasca and _cherry_.

The score distribution will be announced soon.

We hope you'll like the problemset!

UPD1: The score distribution is $500 - 1000 - 1500 - 1750 - 2500 - 3000$.

UPD2: For technical reasons, the round was postponed by 15 minutes. Sorry for that, good luck on round!

UPD3: Editorial is out.

UPD4: Congratulations to the winners!

Div. 1 + Div. 2:

Div. 2:

First to solve each problem:

A: m_99
B: kmjp
C: Brookli
D: MrDecomposition
E: w0nsh
F: rainboy

• +674

 » 2 weeks ago, # | ← Rev. 2 →   +101 As a tester, i recommend you participate in this round! Problems are very interesting and statements are well written.
•  » » 2 weeks ago, # ^ |   +23 As an Italian dish fan,I predict this round is going to be equally interesting just like thier dish SpoilerRound author is from italy i.e. italian round
•  » » » 13 days ago, # ^ |   +26 Wait does that mean we'll have to write some pasta-like code?
•  » » 2 weeks ago, # ^ |   +25 I wait for the day, when some tester doesn't recommend this! xd!
•  » » 13 days ago, # ^ |   +5 Postponed!!
•  » » » 13 days ago, # ^ |   +1 hope it does not extend much
•  » » 13 days ago, # ^ |   +15 Contest Delay 15 minutes
•  » » » 13 days ago, # ^ |   +4 Not meaning to be rude or aything but why did it get delayed?
•  » » » » 13 days ago, # ^ |   +2 server maintenance
•  » » » 13 days ago, # ^ |   +4 it says something abt maintenance till 22:00.. will it be delayed further??
•  » » » » 13 days ago, # ^ |   +7 Nope it is utc 22:00 so contest wont affect i guess you are confused bcoz of time zone
•  » » » 13 days ago, # ^ |   +1 yawn, it doesn't bother anyone in their neck of the woods. right now its dinner time in Russia, everybody's well fed and rested and setting in for the night. In other parts of the world, it's awkward timing, practically nobody is comfortable.
•  » » » » 13 days ago, # ^ |   +1 India falls within the comfortable time zone as well.
•  » » » » » 13 days ago, # ^ |   0 true
•  » » » » » 13 days ago, # ^ |   0 so UTC, +5 ish?
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   +1 not that much as it's time is 8:05 to 10:05 pm. Many have their dinner time during this time period.
•  » » 13 days ago, # ^ |   +3 "The Beginning is the End and the End is the Beginning"
•  » » 13 days ago, # ^ |   +8 Well, the problems are difficult, but I like this round(because I became Expert)!forgive my poor English:)
•  » » » 13 days ago, # ^ |   +3 I like it too!Because I became Master!
•  » » » » 13 days ago, # ^ |   +3 I like it too, I became newbie again:)
 » 2 weeks ago, # |   +15 I see what you did there.
 » 2 weeks ago, # |   +70 lmao, poor anton!!
 » 2 weeks ago, # |   -70 As a tester, I did not test.
 » 2 weeks ago, # |   +459 As a person who wasn't involved in the preparation of this round, I recommend you to participate.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   -22 Happy Lunar New Year!
 » 2 weeks ago, # |   +102 As a tester ,I reccomend you to read all the problems. The statements are short so you won't lose much time.
 » 2 weeks ago, # |   -158 As a participant looking for negative contribution, help me to reach global minima!!!
•  » » 2 weeks ago, # ^ |   +61 No, I don't think I will.
•  » » » 2 weeks ago, # ^ |   -113 Isn't that true with human psychology?
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   -23 Yes! You deserve my down vote for this :DP.S: He asked for down vote
•  » » » » » 2 weeks ago, # ^ |   -62 I request people to help him by up-voting him( given he was helping me to reach the bottom :P )
•  » » 13 days ago, # ^ |   0 if i upvote, am i helping(with contribution) or obstructing you to reach global minima?
•  » » » 13 days ago, # ^ |   -7 Obviously obstructing
•  » » 13 days ago, # ^ |   0 We don't do that here
•  » » » 13 days ago, # ^ |   0 I don't agree on this, everyone helped me.
 » 2 weeks ago, # | ← Rev. 2 →   +18 Many thanks to Keewrem, MrBrionix, MyK_00L, taulant and TheScrasse for preparing the Div.2 contest.
•  » » 2 weeks ago, # ^ |   +34 Don't forget antontrygubO_o for not rejecting any problems
•  » » 2 weeks ago, # ^ |   -8 Can't you say anything other than thanks fr?
•  » » » 2 weeks ago, # ^ |   +1 What's wrong with practicing gratefulness?
•  » » » » 2 weeks ago, # ^ |   -32 Too much of anything is good for nothing.
 » 2 weeks ago, # |   -18 As an upcoming participant. I saw newbie tester :thinking:
•  » » 13 days ago, # ^ |   +7 I think judging someone based on his/her ratings is a crime, it's the passion for CC that brings everyone here, even in Chess not everyone is a GM yet the people who play it enjoy it, it's high time we start judging people based on the number of contests they have appeared in, as in that case it will ultimately benefit the entire programming community.
 » 2 weeks ago, # |   0 Like the early score distribution, the gap between C and D isn't significant, makes me feel comfy! Hoping for a great round! :D
 » 2 weeks ago, # | ← Rev. 3 →   +7 Stefan stefdasca Dascalescu is back to Codeforces/testing/setting yeah! I think its cause the exams are finished finally in some univerisities but not all :(
 » 2 weeks ago, # |   +19 We are hopeful to have such pretests set so that many of us will not be frustrated in the final standings(In the last round it happened).Thank you.
 » 2 weeks ago, # |   +23 As a participant, wish you all great rating changes :)
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +28 Either positive or negative.
•  » » » 2 weeks ago, # ^ |   +4 "Great negative rating change" doesn't make sense, I guess.
•  » » » » 2 weeks ago, # ^ |   +10 Merriam-WebsterGreatnotably large in size : HUGEall creatures great and small
•  » » » » » 2 weeks ago, # ^ |   -7 No, I mean a "Great negative rating change" isn't a real "Great rating change" !
•  » » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   +6 It's
•  » » » » » » » 2 weeks ago, # ^ |   +8 Sad But True .
•  » » » » » 13 days ago, # ^ |   +1 Words can have multiple meanings. In your link, see4 — used as a generalized term of approvalhad a great timeIt was just great.
•  » » » » » » 13 days ago, # ^ |   0 I didn't check your profile the last time I saw your username, are you really from Finland? If yes, why the mango-lassi? Not against it but expecting a good story.
•  » » » » » » » 13 days ago, # ^ |   0 It's not that great of a story. I first registered with the username "mangolassi", but lost the password (and used an old email I no longer had access to), so I made this account.
•  » » » » » » 13 days ago, # ^ | ← Rev. 2 →   +10 Right. But for a phrase to make sense just one meaning needs to apply.
 » 2 weeks ago, # | ← Rev. 2 →   +22 Thanks to MrBrionix, MyK_00L, taulant and TheScrasse for setting the problems Hopefully , we'll enjoy the contest
•  » » 2 weeks ago, # ^ |   +30 You forgot Keewrem :D
•  » » » 2 weeks ago, # ^ |   +39 And also thanks to Keewrem
 » 2 weeks ago, # |   +6 difference between c and d is 250 only. what does this represent? is it that d is not much difficult than c?
•  » » 2 weeks ago, # ^ |   +34 Yes, D should be slightly easier than usual.
•  » » » 2 weeks ago, # ^ |   +107
•  » » » » 13 days ago, # ^ |   +24 Well, this didn't age very well.
•  » » » 13 days ago, # ^ |   0 "easier than usual"
•  » » » 11 days ago, # ^ |   +5
 » 2 weeks ago, # |   0 Again early score contribution, great! thank you!
 » 2 weeks ago, # |   +41 As a problemsetter, MyK_00L says that problem F is easier than C.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +24 As a problemsetter, only one tester solved F during virtual participation (it may be easier than C, though :D)
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -13 Let me guess, was it dario2994 ? XD
•  » » » » 2 weeks ago, # ^ |   +19 Maybe :D (we've already spoiled too much about the contest)
•  » » 2 weeks ago, # ^ |   +37 As a problemsetter, MyK_00L says that taulant shouldn't have dropped from yellow.
 » 2 weeks ago, # |   +83 Has anyone noticed that all of the authors have the same profile picture?
•  » » 2 weeks ago, # ^ |   +83 Yes.
•  » » 2 weeks ago, # ^ |   +6 I guess it's because that picture is the logo of the contest.(At least you can assume that)
•  » » » 2 weeks ago, # ^ |   +42 Well, not really at the beginning; I'm going to share the backstory here. At first, around 2 weeks ago, I took a picture from the Black Cherry sticker pack and set it as my profile picture on Codeforces and Telegram. A few days later, TheScrasse was looking for a profile picture to replace the Lichess horsey, and he didn't want to use a picture of himself, so I told him he could take mine. After a moment, I came up with the idea that we could all use that picture during the week of the contest.
 » 2 weeks ago, # |   +43 Wow! It falls on Chinese Spring Festival. May my rating increase on the first day of the new year :)
 » 2 weeks ago, # |   +19 happy lunar new year ^^, hope this contest will be a good contest ^^
 » 2 weeks ago, # |   +16 i hope fair pretests !!
 » 2 weeks ago, # |   +45 As a tester, I wish all the participants good luck and I recommend you all to read all the problems.
 » 2 weeks ago, # |   0 As a to be participant, I wish everyone good luck and happy ratings :)
 » 2 weeks ago, # |   -15 ///...
 » 2 weeks ago, # | ← Rev. 2 →   +13 I will be posting solutions of problems of this contest tomorrow. On this YouTube Channel:- https://www.youtube.com/channel/UCfX-OxxzYPELHxpNojOojcw
•  » » 2 weeks ago, # ^ |   0 Are you sure you'll handle this?
•  » » » 2 weeks ago, # ^ |   0 I mean not all but at least till C I will do it.
•  » » » 2 weeks ago, # ^ |   +25 doesn't matter even he is not able to do even B but at least he contributed something and at least tried rather than discouraging others
•  » » 2 weeks ago, # ^ |   +7 Best of luck buddy, we'll look forward to it
•  » » » 2 weeks ago, # ^ |   +11 Thanks bro
 » 2 weeks ago, # |   -22 As a completely uninvolved person, I recommend you participate in this round!
 » 2 weeks ago, # |   +27 Happy Chinese New Year!
 » 2 weeks ago, # |   0 Very excited!
 » 2 weeks ago, # | ← Rev. 2 →   +22 Not relatedJust noticed that. It makes delta 0 in unrated rounds. I think it would be better if it calculates virtual rate change like this
 » 2 weeks ago, # |   -16 Guys can u please push me to 0;))
 » 2 weeks ago, # |   +4 I hope this contest has strong test cases, especially pretests :)
 » 2 weeks ago, # |   -36 Is it rated
•  » » 2 weeks ago, # ^ |   +11 Yes.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   -7 Is this comment just intended to get down vote? ( rated for participants with rating lower than 2100. )
 » 2 weeks ago, # |   +7 The last Round was a nightmare for me (even today, I didn't understand the reason), Hoping that this time things will be much different, finger crossed.
•  » » 13 days ago, # ^ |   +6 best of luck....
•  » » » 13 days ago, # ^ |   -13 abe saale tu bhi meri tarah khaliyar hai.
 » 2 weeks ago, # |   +27 Happy Lunar New Yearrrr
 » 2 weeks ago, # | ← Rev. 2 →   0 Can an un-rated user give this round ??
•  » » 2 weeks ago, # ^ |   0 yes
 » 2 weeks ago, # |   0 Hopefully I will solve C today and become pupil
•  » » 2 weeks ago, # ^ |   +2 To become pupil AB solving(I guess up to hour) is sufficient
•  » » » 2 weeks ago, # ^ |   +1 Well if B is of difficulty <= 1300 then I will do it easily I guess.But if its difficulty is >=1400 then I think it will be a challenge for me currently,Let's see what happens.Fingers crossed!!!!
 » 2 weeks ago, # |   0 As a tester, I wish all the participants good luck and I recommend you all to read all the problems.
 » 2 weeks ago, # |   +1 Good luck everyone, i wish we all will raise our ranks
 » 2 weeks ago, # |   +9 I hope there will be a palindrome related problem to honor the day (12.02.2021) :)
 » 2 weeks ago, # |   +30 It's 12/02/2021 A question on palindrome would be fun to solve .
 » 2 weeks ago, # |   0 Happy Lunar New Year!!! :)
•  » » 2 weeks ago, # ^ |   +10 Long time no see :) BtwHappy Lunar New Year!
•  » » 13 days ago, # ^ |   0 Happy Lunar New Year!!!
 » 2 weeks ago, # |   +10 will the contest still be held? because Polygon and Codeforces will be possibly unavailable in the period between Feb. 12, 20:00 (UTC) and Feb. 12, 22:00 (UTC) because of maintenance.
•  » » 2 weeks ago, # ^ |   +9 That would be a few hours after the contest, so it is not a problem. (the contest ends at 16:35 UTC)
•  » » 2 weeks ago, # ^ |   0 THe maintenance won't influence this contest because the contest will end at $\textsf{Feb. 12, 16:35(UTC)}$ :)
 » 2 weeks ago, # |   0 Is today CF round has some technical issue as the message is displayed ???..
•  » » 2 weeks ago, # ^ |   +18 No, the technical issue is not related to the contest.
 » 2 weeks ago, # |   +12 Authors are different but their pictures are the same:D
 » 2 weeks ago, # |   -7 As a human bean, I recommend you all breathe.
•  » » 13 days ago, # ^ |   -20 Is that you?
•  » » » 13 days ago, # ^ |   0 It be me.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 I wonder if those who downvote know who Mr. Bean is.
•  » » » » 13 days ago, # ^ |   0 they probably know Rowan Atkinson and Blackadder too.
•  » » 13 days ago, # ^ |   +2 Do beans have lungs?
•  » » » 13 days ago, # ^ |   +1 Only the human flavour
•  » » » 13 days ago, # ^ |   +4 Human beans do.
 » 13 days ago, # |   0 antontrygubO_o for not being involved and hence not rejecting any problem. Is it a joke?
•  » » 13 days ago, # ^ |   +3 What do you think?
•  » » » 13 days ago, # ^ | ← Rev. 3 →   0 They are absolutely serious about antontrygubO_o not having been involved.
 » 13 days ago, # |   -33 Why contest nowadays are not based on proper ds and algo they are mostly ad-hoc??
•  » » 13 days ago, # ^ |   +2
•  » » 13 days ago, # ^ |   0
•  » » 13 days ago, # ^ |   0 I think creating DS and Algo problems that are completely new and of difficulty level Div2 B,C or so is hard. There are many of them already existing in different OJs.
 » 13 days ago, # |   +21 Delay :(
 » 13 days ago, # |   -16 shifted by 15 min.
 » 13 days ago, # | ← Rev. 2 →   -10 .
 » 13 days ago, # | ← Rev. 2 →   -13 <3
 » 13 days ago, # |   -13 why +15 min more :(
 » 13 days ago, # |   0 This contest also starts postponing. Hoping it will not become unrated as well.
 » 13 days ago, # |   +111 CONJECTURE : If you have exam next day and you attempt a rated round. You will screw up both ratings and grades.
•  » » 13 days ago, # ^ |   +6 Or you will just screw the exam as usual.
•  » » 13 days ago, # ^ |   0 Guess I'll be the one to prove it.
 » 13 days ago, # |   0 :-(
 » 13 days ago, # |   0 15min late
 » 13 days ago, # |   0 LOL BLUFF
 » 13 days ago, # |   +1 contest postponed by 15 min
 » 13 days ago, # |   0 delay 15 min :(
 » 13 days ago, # |   0 And here we go 15 mins late again! ;)
 » 13 days ago, # |   0 Why is the contest being delayed? :( Hope it doesn't get delayed any more.
 » 13 days ago, # |   +3 here we go again.. delay...
 » 13 days ago, # |   0 15 minutes delay!?
 » 13 days ago, # |   +7 ok lemme listen again.
 » 13 days ago, # |   0 Delayed by 15!!
 » 13 days ago, # |   0 Contest delayed...just hoping to not face a long queue!
 » 13 days ago, # |   0 delay of 15 min
 » 13 days ago, # |   0 Contest delayed.New start time at 20:20
 » 13 days ago, # |   0 Has the contest been moved back?
 » 13 days ago, # |   0 This is a bad sign :( We'll probably get a too long tail and the contest will be unrated.
 » 13 days ago, # |   0 Now i know why they delayed the contest , They are watching LOCO CODM Cup Pro , mYm vs Godl .
 » 13 days ago, # |   0 Any idea why the delay?
 » 13 days ago, # |   0 Looks like we've to wait for some time before the contest starts........
 » 13 days ago, # |   +258 Sorry for +15 minutes. I postponed the contest to be sure that everything is OK. I'm here, no reasons to worry. Good luck on the round!
•  » » 13 days ago, # ^ |   +71 Bhai Bhai
•  » » 13 days ago, # ^ |   +13 15min Delay is better than Unrated contest :)
•  » » » 13 days ago, # ^ |   0 I think so.
•  » » 13 days ago, # ^ | ← Rev. 2 →   -17 Bas itna bol diye kafi hai Peace of breath
•  » » 13 days ago, # ^ |   0 Okay thanks
•  » » 13 days ago, # ^ |   0 because I can.
•  » » 13 days ago, # ^ | ← Rev. 2 →   +2 I was hoping this round won't be unrated again, but when MikeMirzayanov tells you he is here, just relax
•  » » 13 days ago, # ^ |   +16 Ek hi to dil hai. Kitni baar jeetoge
•  » » 13 days ago, # ^ |   0 Thanks bhai you are here.......
 » 13 days ago, # |   -6 Codeforces Waiting for 20,000 Participants to Cross! Agree?
•  » » 13 days ago, # ^ |   +1 It is not good at all. Last time everybody shouted for the 30000 and people started coming out of nowhere. And lead to an unrated round. After that, all were disappeared, and numbers came around 20000. And now again IF you start this, IN MY OPINION people new account for such streak. which is not good.DownVote if don't agree.
 » 13 days ago, # |   +2 hope it remains rated...
 » 13 days ago, # |   -7 They should not delay the contest it is quite frustrating
 » 13 days ago, # |   0 QWQ 15 min ..
 » 13 days ago, # |   0 Delayed for 15 minutes...
 » 13 days ago, # |   0 you got je'baited
 » 13 days ago, # |   0 My first contest in the new lunar year <3
•  » » 13 days ago, # ^ |   0 yes idol !!
•  » » » 13 days ago, # ^ |   0 Ukm em = (
 » 13 days ago, # |   0
 » 13 days ago, # |   +15 Even codeforces is taking time to start the contest and you think that your crush will start loving you so easily and early! ;-)
 » 13 days ago, # |   -39 when you are ready with your brain to solve problems but suddenly time to start contest increases. you be like "Mai madarc*od hoon jo isme aaya"
 » 13 days ago, # |   0 when we click 'ok' button and it says 14:58 , it feels like we are carrying the bier of our enthusiasm !!!
 » 13 days ago, # |   +7 Don't be unrated please
•  » » 13 days ago, # ^ |   0 Yeah when you practice soo much and it gets unrated...really dude it hurts
 » 13 days ago, # |   0 waiting for 15 min when we are all set to go, is quite frustrating but we can wait for a better experience!
 » 13 days ago, # |   0 Noo!!! delay :( Wishing everything goes well :/
 » 13 days ago, # |   0 15 min delay : my brain : unrated , server issues , queuemike comments : my brain : It's time to solve problems now !
 » 13 days ago, # |   0 So,no contest today due to server maintainance ? can anyone confirm ?
•  » » 13 days ago, # ^ |   0 The contest will start in a few minutes.
 » 13 days ago, # |   0 All the best 1 min remains now
 » 13 days ago, # |   +2 My sister brought a fried chicken for me at 8:30. I said I'll eat this after 10:35.Thanks for the delay
•  » » 13 days ago, # ^ |   +3 4 parallel universes ahead of us all
 » 13 days ago, # |   +11 delayforces :) But Actually delay is better than Unrated round :)
 » 13 days ago, # |   0 CancerForces
 » 13 days ago, # |   -9 The comment removed because of Codeforces rules violation
 » 13 days ago, # |   -23 Please don't make contests if u can't make one.
•  » » 13 days ago, # ^ |   +15 Bruh, don't blame the writers if you cannot solve the problems.
•  » » 13 days ago, # ^ |   +5 I don't see any problem with the contest. It's just that it is a little tougher than usual. And it's completely okay to have such small variations.
 » 13 days ago, # |   +8 Welcome to the comment section, who left the contest unattempted after watching 1st question.
•  » » 13 days ago, # ^ |   +10 is your surname Modi? kyuki aapne meri "Mann ki baat" kehdi
 » 13 days ago, # |   +1 thanks for clear and short statements , really liked the problems
 » 13 days ago, # | ← Rev. 2 →   +1 Contest is running now, but I cant register now, why??
 » 13 days ago, # | ← Rev. 2 →   +13 Wow even A was pretty tough!
 » 13 days ago, # |   +8 Is it rated?
•  » » 13 days ago, # ^ |   -8 Yes.
 » 13 days ago, # | ← Rev. 2 →   -8 :|this was a hard div 2 contst
•  » » 13 days ago, # ^ |   -29 It's not a shit contest, but it is made for div1 after b.
•  » » » 13 days ago, # ^ |   -10 maybe
•  » » » 13 days ago, # ^ |   +23 You don't know shit about CF then. D2C is D1A, so it's always made for D1 after B.
•  » » » 13 days ago, # ^ |   +28 This is why C solved by ~2k?)
•  » » 13 days ago, # ^ |   +10 Though I couldn't do my best today, I think the problem-set was pretty standard. Being unable to solve a problem doesn't mean it has to be a shitty contest. Besides, you don't have any right to insult a setter panel like this. I enjoyed the problem-set. And I am pretty sure they worked really hard to make this contest enjoyable and successful.
 » 13 days ago, # |   0 20,000+ Registration and somewhat 10,000 people made submissions :/
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 Yeah
 » 13 days ago, # |   0 How to solve C,D ??Verry toough contest for mee :(
•  » » 13 days ago, # ^ | ← Rev. 4 →   +4 Hint : We can find all pairs $(a,b)$ by fixing remainder $R$. $R$ must be less than $sqrt(x)$ and we can do binary search . Full IdeaProblem C :Suppose we fix $b$ , then all possible $a$ will be of form $b*h + h$ where $hR$ and thus $b*R + R > R^2$ . Thus all possible remainders for which answer will exist will lie in $[1,sqrt(x)]$ . For each remainder $R$ , we can binary search upper limit $U$ such that $U*R + R <= x$ . Then we can add $U-R$ to the answer.
•  » » 13 days ago, # ^ |   +3 Problem D:LCM of all numbers from 1 to 16 is 720270. You can fill a matrix B with this number. Now all we have to do is to make differences of k^4. For that you can simply subtract A[i][j]^4 from B[i][j] in a chess pattern. Now all numbers in B are divisible with the numbers in A and they respect the conditions.Here is my code: 107219536
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 For C, for one possible b, min(b-1,floor(x/(b+1))) values of a is possible I did it by breaking it in two parts doing first for b which are less than sqrt(x) and then the for the b whose multiples are less than sqrt(x). The numbers left need to be tackled separately so that any b is not counted more than once. Solution
 » 13 days ago, # |   0 lol that F was nice XD
 » 13 days ago, # |   +3 How to solve C ? Plz
•  » » 13 days ago, # ^ |   0
•  » » 13 days ago, # ^ |   0 i use a = c * (b + 1) then c = 1...5e5 (c < b) for each c find how many b and a satisfy
•  » » 13 days ago, # ^ |   0 a should be of the form n*k+k. Now n*k+k<=x, then n<=(x-k)/k. Now iterate over k from 1 to x (say). answer will be incremented by min(n,y)-k, I did this because numbers which have k as the remainder and quotient will be in between k+1 and min(n,y). Now if min(n,y) < k+1, then you should break the loop because right value is smaller than left value. You can check using simple maths that you don't need to iterate for k more than sqrt(x+1) times check to get the final answer
 » 13 days ago, # | ← Rev. 2 →   0 Tf is pretest 8 in C QAQ
 » 13 days ago, # |   -21 C
 » 13 days ago, # |   +5 I like this type of contest :) Thanks for good problems.
 » 13 days ago, # |   +6 How to do C or D ?
 » 13 days ago, # |   -11 Very bad contest!
 » 13 days ago, # |   +60 Unbalanced contest. Today we had a Mathforces ! Problem C was too math oriented.C should have been divided in two parts, with lessor and higher constraints.I got the idea of C but couldn't implement in 1.5 hours :( Approachfor each i from [1...a] , we need to find the number of second half of divisors of each i which are less than and equal to b.
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 I noticed a pattern in C:a : b : cnt3 : 2 : 1 <3>4 : 3 : 2 <4,8>5 : 4 : 3 <5,10,15>6 : 5 : 4 <6,12,18,24>so suppose take set for a=6 then every number in that set and b is special pair......a goes till x and b till y. Take approproiate minimas of x and y though.
•  » » » 13 days ago, # ^ |   0 I'm not sure if your approach would fit in the constraints as x,y <= 1e9.
•  » » » » 13 days ago, # ^ |   0 Yeah I could just get the idea though let alone implementing the whole thing :(
•  » » 13 days ago, # ^ |   0 Hi, actually I had a very cool idea. But its a little bit maths oriented :( Approach : a should be of the form n*k+k. Now n*k+k<=x, then n<=(x-k)/k. Now iterate over k from 1 to x (say). answer will be incremented by min(n,y)-k, I did this because numbers which have k as the remainder and quotient will be in between k+1 and min(n,y). Now if min(n,y) < k+1, then you should break the loop because right value is smaller than left value. You can check using simple maths that you don't need to iterate for k more than sqrt(x+1) times check to get the final answer
•  » » 13 days ago, # ^ |   0 C could be done with binary search too
 » 13 days ago, # |   +13 Unfortunately, I have seen a similar task with C when preparing for our last round...
•  » » 13 days ago, # ^ |   +15 Sorry, we didn't know about that task.
 » 13 days ago, # | ← Rev. 2 →   +6 Is C is really something so simple, or it is easy to google? :)Because all I have thought is to try solve $a = (b + 1)ceil(a / b)$ and it led me to "iterate $b$ over $[1; y]$ and add to answer $min(x, b(b+1) - 1) / (b + 1)$". But ofc it's $O(y)$ :(
•  » » 13 days ago, # ^ |   +1 I literally submitted that: https://codeforces.com/contest/1485/submission/107226790(and it TLEd obviously)
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 it's not o(y) because you only have to go until min(y,1e5).
•  » » » 13 days ago, # ^ |   +4 I don't know how to calculate sum of $x / (b + 1)$ in range $[sqrt(y); y]$. I think there is formula but not found it.
•  » » » » 13 days ago, # ^ | ← Rev. 3 →   0 After you pass sqrt(X), some values start to repeat (ie. floor(100/80) = floor(100/81) = 1)You can split the code into two parts, one iterate from [1, sqrt(X)], doing the same thing you made: ans += X / (b + 1). For the rest, you could iterate on the quotient, instead of the divisor (ie. how many Z satisfy 100 / Z = 1?)It will end up as a pattern like this: for every i in [L, R], floor(X / i) == 1 for every i in [R + 1, ...], floor(X / i) == 2 ... for every i in [..., ...], floor(X / i) == sqrt(X) So you will end up with another loop that iterate over sqrt(X) values, doing this operation: ans += (R — L + 1) * quotient
•  » » » » » 13 days ago, # ^ |   0 Yeah, I've already done that 107235694Silly me that not thought of it during contest
•  » » 13 days ago, # ^ |   0 lol i thought the same and even submitted that XD
 » 13 days ago, # |   0 Great Round, thanks.
 » 13 days ago, # |   +4 How to calculate Summation min(b-1 , x/(b+1) ) in C . b varies from 1 to y . Is there any other way??
•  » » 13 days ago, # ^ |   +1 No need to go till Y. Iterate on the remainder, the maximum remainder you require is 32000.
•  » » » 13 days ago, # ^ |   0 How did you found that after using 32000 I got AC https://codeforces.com/contest/1485/submission/107234382
•  » » » 13 days ago, # ^ |   0 Got that we need to go only till sqrt(x) so used r*r<=x
•  » » 13 days ago, # ^ |   0 Observe that $min$ is only useful for $1 <= b <= sqrt(x)$.$sqrt(x)$ isn't that high. So you can bruteforce the part with $min$.For other values of $b$, just do a binary search on when $x/(b+1)$ changes. As there are around $sqrt(x)$ different such values (remember harmonic sum?) this would not be that bad either.
•  » » » 13 days ago, # ^ |   0 I kind of observed that , but thought it's C and shouldnt be that trickier. Knew that n/x yields same value for i <=x<= n/(n/i).
 » 13 days ago, # |   0 How to find all $x$ in $[1, a]$ such that $x = i \cdot (j + 1)$ where $1 \leq i < j \leq b$?
 » 13 days ago, # |   +3 Was there some trick in D?
•  » » 13 days ago, # ^ |   +4 Yes. 720720 is lcm of numbers from 1 to 16, i.e. 720720 is divisible by any number in our matrix. further if (i + j)% 2 == 0 b [i] [j] = 720720 else b [i] [j] = 720720 + a [i] [j] * a [i] [j] * a [ i] [j] * a [i] [j]. chess coloring
•  » » » 13 days ago, # ^ |   0 Wow!
 » 13 days ago, # |   +24 fuucccckkkk, I couldn't submit E because I spent the last 10 minutes debugging the fact that my ape mind didn't understand the tree input format
•  » » 13 days ago, # ^ |   0 That tree input sucks.It should be trivial to implement the parser.
•  » » » 13 days ago, # ^ |   0 It's actually my favorite way to input a tree. You can show that v[i] is also the parent of i, which saves you from doing a dfs to separate parent and child.
 » 13 days ago, # |   +4 Kudos to problem setters. Short & crisp problem statements were great!!
 » 13 days ago, # |   +17 Whoa, that was tough but fun. A was a bit tougher than usual but OK. I felt B and C required really careful implementation (especially C). I solved as far as C and I can tell by the rankings that this contest was tougher than usual.Couldn't crack D, was interesting though.
 » 13 days ago, # |   +34 Again, I realized how bad my math is :(
 » 13 days ago, # | ← Rev. 2 →   +1 I think problem F is easier and lighter(implementation wise) than usual. Otherwise, A pretty nice round. Thanks for the problems.
 » 13 days ago, # |   0 it sucks so bad when you realize how D can be solved after coding a dumb ass recursive solution and there is only 1 minute left.
 » 13 days ago, # |   0 A was really interesting one!
 » 13 days ago, # | ← Rev. 4 →   +26 For D. Notice that minimum number that divide each element is $720720$. We should make difference between adjacent elements equal $k^4$ for some $k$. Consider our matrix ass chess desk with white and black cells, so each white cell will be adjacent to black cells and vice versa. So we can set black cells equal $720720$, and white $720720 + M[i][j]^4$ what is less than $10^6$ and difference condition is met.
 » 13 days ago, # |   0 How to solve A ?? sorry in advance for bothering you .
 » 13 days ago, # |   0 for $C$ the answer will be $\sum_{b=2}^{Y} min(X/(b+1),b-1)$. Can anyone tell how to compute this efficiently?
•  » » 13 days ago, # ^ |   0 This is what I did: up until b=1e5 just apply the formula you mentioned, and after that it is clear that $X/(b+1)$ will be the minimum for whatever value of X, so figure out a way to efficiently do $\sum_{b=1e5+1}^{Y} X/(b+1)$
 » 13 days ago, # |   0 107225945 why my code getting tle ? explain me!
•  » » 13 days ago, # ^ |   0 107221818 sorry exacly this code
•  » » » 13 days ago, # ^ |   0 Bruh. Because B is big.
•  » » » » 13 days ago, # ^ |   0 but some code already ac like 107226318
•  » » » » » 13 days ago, # ^ |   0 He has break inside loop, you don't.
•  » » » » » » 13 days ago, # ^ |   0 *didn't
•  » » » 13 days ago, # ^ |   0 because your sol is O(b * t) = 1e11 = TLE
•  » » » 13 days ago, # ^ |   0 ok thanks.
 » 13 days ago, # |   +9 I corrected a mistake in my solution for E just two minutes after the contest was over, and then it passed the sample test case. I met such a situation again and again. o(╥﹏╥)o Anyway, I'll try my best next time and wish myself to keep calm during the contest for better debugging.
 » 13 days ago, # |   +1 Please Help Suppose I submit a correct solution of a problem and a minute later i again resubmit another correct solution of the same problem . Will the second solution get a penalty of 50 points because that is what happened with me today in problem A despite never having a wrong submission . Instead of 478 points I got 428
•  » » 13 days ago, # ^ |   +1 Yes, it does happen that way. Even if your original submission happens to be correct, (which is not something that is known during contest as only pretests are run) you still incur a penalty.If I am not wrong, the only submissions that don't count towards penalties are the first submission (not counting any compilation issues beforehand) Submissions that fail to compile.
•  » » » 13 days ago, # ^ |   0 Okay !! Thank you very much
•  » » » » 13 days ago, # ^ |   0 happy to help :)
 » 13 days ago, # |   +4 Unfortunately, weak pretests for B.
•  » » 13 days ago, # ^ |   +1 wrong answer 80200th numbers differ — expected: '930343232', found: '576709456628597052'
•  » » 13 days ago, # ^ |   0 I got FST on B for a very simple case which is when l==r, this type of simple cases should be present in the pretests.
•  » » » 13 days ago, # ^ |   0 I also got FST on B I forgot the case for n=1 , today I had the chance to become expert but I missed it :(
•  » » » 13 days ago, # ^ |   0 Same problem for me. I forgot to test l==r.
 » 13 days ago, # |   0 if i have 2 more min, i would AC B :(
•  » » 13 days ago, # ^ |   0 If I have 10 more sec, I would have AC C
 » 13 days ago, # |   +1 Thanks for the great problems. What is the fastest way of finding any positive solution to $ax + by = c$?
•  » » 13 days ago, # ^ |   +3
•  » » » 13 days ago, # ^ |   0 I am not too sure but doesn't linear diophantine only tell you if there exist some a and b. not necessary positive a or b
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   +11 But you can always shift the obtained fundamental solutions to obtain both positive x and y if they exist in O(1) time.
 » 13 days ago, # | ← Rev. 3 →   0 My bad.
•  » » 13 days ago, # ^ |   0 It's too late to hack in contest, but CM's and above can uphack, which would add the test for future upsolvers. It won't change anyone's rank in contest, but it's still useful (not to mention fun). If you send me the submissions and the hack test, I could uphack them for you.
•  » » 13 days ago, # ^ |   0 test case 26 has n = 1.so no, not a "lotta solutions" fail to cover n = 1.
•  » » » 13 days ago, # ^ |   0 Oh! my bad.
 » 13 days ago, # |   +4 like task D
 » 13 days ago, # |   +9 Dear Keewrem, I am very sorry that I complained irrationally about math today. I may have hurt your feelings unintentionally. I may have disrespected your hard work. I didn't want to do that. I loved today's problem set. I deeply appreciate your hard work. As I suck at math and I didn't have anything to do, I irrationally started trolling you guys without thinking a bit. But one of my friends made me realize that I was very wrong. I am extremely sorry. Please accept my apology. I hope to see you guys set more awesome contests like this! Thank you.
 » 13 days ago, # |   +14 Easy D (1750), LOL
•  » » 13 days ago, # ^ |   +14 D feels like aprils fooling if not solved :/
•  » » 13 days ago, # ^ |   0 Just chess coloring of 720720 and same number minus a[i][j]
 » 13 days ago, # |   +6 oughh... Pleeassee make pretests hard :'( it hurts so much
 » 13 days ago, # |   +64 $\lfloor \frac{a}{b}\rfloor$ forces
 » 13 days ago, # |   0 Nice contest..... I like that there are hints in editorial before giving out the solution
 » 13 days ago, # |   0 Don't know about others, but coming from a math background, this contest was really enjoyable. Kudos to all the authors! :)
 » 13 days ago, # |   +18 A-D are math problems
 » 13 days ago, # |   0 Can anyone tell why B failed on System Test 5?
•  » » 13 days ago, # ^ |   0 Check when b is equal to 1, e.g. 4 1 10 6 7 8 9 1 1 
•  » » » 13 days ago, # ^ |   +1 Can't believe I missed this case. Anyways thanks a ton for help!
 » 13 days ago, # | ← Rev. 2 →   0 The idea of putting hints inside the tutorial before describing the complete solution is the best ever!
 » 13 days ago, # |   +8 Thanks for good pretests in B...
 » 13 days ago, # |   0 Although I couldn't Participate but I just want to say that the problems are Brilliant!! Thanks a lot for the contest.
 » 13 days ago, # | ← Rev. 2 →   +21 if I read D before C, I would AC D :( Why in this contest D is much easier than C?
 » 13 days ago, # |   0 I must admit, those problem are pretty nice. I didn't expect the solution to be that short and elegant. But my rating isn't happy rn
 » 13 days ago, # | ← Rev. 2 →   0 I think there was issue in problem A, like it was not clearly mentioned that u have to perform only one of the two operation. for first 10 min I was performing both operation in each step. bad luck...xd!But the problem were very nice, I was able to solve only A & B, but both were very logical.
 » 13 days ago, # |   +1 Thanks for the contest :)
 » 13 days ago, # |   0 I tried to calculate $Dp_i$ from bottom to top in problem E, but got wa on test 3. It works like this: sort(stage[i].begin(),stage[i].end(),cmp); ll Max=-Inf; rep(j,0,stage[i].size()-1){ int k=stage[i][j]; f[fa[k]]=max(f[k]-a[k]+maxx,f[k]+a[k]-minn); f[fa[k]]=max(f[fa[k]],a[k]+Max); Max=max(Max,f[k]-a[k]); } Max=-Inf; per(j,stage[i].size()-1,0){ int k=stage[i][j]; f[fa[k]]=max(f[fa[k]],Max-a[k]); Max=max(Max,f[k]+a[k]); } Where $i$ is the depth. The nodes in $stage[i]$ has the same $dis$ which is $i$.$minn$ is the minimum of $a_i$ at the same stage, $maxx$ is similar to $minn$.Could anyone explain that why it is wrong? The submission : 107250435
 » 13 days ago, # |   +1 Hello everyone, this is my first time making a tutorial if you like then please like and share and if there is any concern then please comment: https://youtu.be/fMZIuQU7fqY Solutions for problem A,B,C,D
 » 13 days ago, # |   -23 Why have the recent rounds started adding so many Adhoc, Math and Constructive questions? We should have more DP, Graph, Range Queries etc.
 » 12 days ago, # |   0 I wish there could be more video based editorial to help newbies.
 » 11 days ago, # |   +1 A very cool problemset. Thanks.