### antontrygubO_o's blog

By antontrygubO_o, 3 years ago, translation,

Hello, Codeforces!

We are glad to invite you to the Codeforces Round #572, which will be held on Friday, 5 July at 18:05. The round will be rated for both divisions (as this time we thanked MikeMirzayanov).

Round was prepared by us, antontrygubO_o and mhq. This is our first round, and, as we hope, not the last one!

A lot of thanks to arsijo for the excellent coordination of the round, gepardo, Mediocrity, kefaa, zoomswk, ecnerwala, AllCatsAreBeautiful, DmitryGrigorev, Markellonchik, dasfex, taran_1407, ankeet, DenisPushkin, austrian_artist, mmello, sas4eka for the testing and valuable comments, and to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon. (please rated)

Participants in each division will be offered 6 problems and 2 hours to solve them. We strongly recommend reading statements of all problems! The scoring distribution will hopefully be announced before the round begins.

We wish you good luck and high rating!

UPD1: Shortly after the contest, we'll be on the community Discord server to discuss the tasks.

UPD2: Slight corrections: participants in Div $1$ will be offered $5$ problems, one of which will have $2$ subtasks, while participants in Div $2$ will be offered $6$ problems, one of which will have $2$ subtasks. Please note that subtasks will be unusual this time and will differ not only by constraints.

UPD3:

Scoring distribution of Div $2$ round: 500 — 1000 — 1250 — (500 + 1250) — 2250 — 2750

Scoring distribution of Div $1$ round: (250 + 750) — 1250 — 1750 — 2250 — 2500

UPD4: Editorial

UPD5 Congrats to winners!

Div 1:

1. Um_nik

2. ugly2333

Div 2:

1. CSWhisky

4. teamskiy

5. NeoGul

• +621

 » 3 years ago, # |   -52 Early blogs !! best of luck !!!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   -10 deleted
•  » » » 3 years ago, # ^ |   +16 downvote !!! that's my luck .
 » 3 years ago, # | ← Rev. 2 →   -73 Savage : (please rated)
 » 3 years ago, # |   -36 The round will be rated for both divisions (as this time we thanked MikeMirzayanov). Everybody takes it seriously now!
 » 3 years ago, # | ← Rev. 7 →   +31 We strongly recommend reading statements of all problems!Hope that the problems are correctly sorted according to difficulty.
•  » » 3 years ago, # ^ |   +153 When people downvote for no apparent reason. :(
 » 3 years ago, # |   +51 guys, can you prepare solutions of problems beforehand so we can see solutions immediately after the contest??
•  » » 3 years ago, # ^ |   +57 But solutions everytime is ready before the contest cause how authors get right answers on tests?
•  » » 3 years ago, # ^ |   +161
•  » » » 3 years ago, # ^ |   -97 Savage...hahhahah
•  » » » » 3 years ago, # ^ |   -48 why I m getting downvotes continously just for saying savage...? Any particular reasons
•  » » 3 years ago, # ^ |   +83 Why is this downvoted even though it is perfectly fine and resonable question? It makes much more sense for authors to release editorials right after contest, cause after two weeks just a tiny fraction of participants will still be interested in reading them.
•  » » » 3 years ago, # ^ |   +151 Well, editorial is already ready anyways :)We plan to post it not later than in $10$ minutes after contest's end
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 It's cool! But it is not every time that problem setters publish their editorials just after the contests.
•  » » » » 3 years ago, # ^ |   +28 I think Codeforces shouldn't accept rounds without editorial been ready, days after the contest most of the time I lose the passion to read the editorial :(
 » 3 years ago, # |   +13 I hope the statement as short as the blog :)
•  » » 3 years ago, # ^ |   0 love short statement with no long story else I will submit sample :>
•  » » » 3 years ago, # ^ |   -16 love short statement? how about love story statement
•  » » » » 3 years ago, # ^ |   +46 How just about love stories or love letters
•  » » » 3 years ago, # ^ |   +24 how about this problem?
•  » » 3 years ago, # ^ |   0 But if you can't solve the problem a good story might cheer you up :)
 » 3 years ago, # |   -30 Best of luck for your first contest
 » 3 years ago, # |   -151 The comment is hidden because of too negative feedback, click here to view it.
•  » » 3 years ago, # ^ |   -25 Nope
•  » » 3 years ago, # ^ |   +2 then,are u NaCly_Fish?
•  » » » 3 years ago, # ^ |   0 Someone used this fake username. This is not real NaCly_Fish.
•  » » 3 years ago, # ^ |   +5 I think you are not real NaCly_Fish...
 » 3 years ago, # |   -24 atlast people have began to recognise importance of showing gratitude to Mark Mirzayanov for his codeforces & polygon platform.
 » 3 years ago, # |   +27 Will I be able to participate in division 2?? I'm new to codeforces.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 Of coures you can.You can be able to participate in division 2 if your rating is lower than 1900.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +2 tmwilliamlin618 has not participated in the codeforces round yet. So he has no specified rating. (Though that kind of users also belong to Division 2 because in that case the user's rating is considered as 1500.)
•  » » 3 years ago, # ^ |   +50 I suggest you register another account with a different username and forget about your current account. I learned the hard way that having "tmw" as a prefix and a permutation of "168" as a suffix of your username will give you a significant disadvantage. Hurry, before it's too late.
•  » » » 3 years ago, # ^ |   +48 Yet you still became IGM and qualified from for the USA IOI team. All you're doing is proving that you deserve to be LGM, but your username is holding you back.
•  » » » » 3 years ago, # ^ |   +63 The significant disadvantage is actually that your rating will be much higher than your skill, not the other way around. People will expect you to do much better than you actually can in non-codeforces contests (like IOI) and you will be given a lot of pressure, especially when you fail to meet their expectations.
•  » » » » » 3 years ago, # ^ |   +40 Tmw orz
•  » » » » » 3 years ago, # ^ |   +29 Don't worry we will always love you tmw <3
 » 3 years ago, # |   +16 Lets do it!
 » 3 years ago, # |   +48 This is the result of a few refreshments on the page. I think these differences should be corrected.
•  » » 3 years ago, # ^ |   +240 this is truly a player who believes in submitting at 1:59:59
•  » » » 3 years ago, # ^ |   +8 You're a witty man. Anyway, I didn't mean to write with such an idea. :)
•  » » » 3 years ago, # ^ |   0 What about hacking at 1:59:59? ("is it correct?" during 1:50:00 to 1:59:58)
•  » » » 3 years ago, # ^ |   +17 There is a "truly player" who submit at 1:59:59 :)56590817
 » 3 years ago, # |   +6 It's really fun to join a contest after completing my final exam.Good luck for everybody.
•  » » 3 years ago, # ^ |   -52 once I post the same statement , I got approximately 30-40 downvotes...
•  » » 3 years ago, # ^ | ← Rev. 3 →   -39 deleted
•  » » » 3 years ago, # ^ |   -30 hahah...True
•  » » 3 years ago, # ^ |   0 what happend?
 » 3 years ago, # |   -11 Testers Test Test
 » 3 years ago, # |   +17 Subtasks will be unusual? Oh,that's fun.
 » 3 years ago, # | ← Rev. 3 →   -20 Although it's not a good time for Chinese. I still wish everyone have fun and I wish the authors' hard work get success!
 » 3 years ago, # |   -36 when everyone is getting downvotes but u still have 0 contribution
•  » » 3 years ago, # ^ |   +1 good job, you just joined us.
 » 3 years ago, # |   -14 Seems like some guys are really having fun of downvoting everybody everywhere(
 » 3 years ago, # |   +82 Codeforces: Sponsored by Telegram we'll be on the community Discord server to discuss the tasks
 » 3 years ago, # |   -18 As a Chinese,it's hard for me to understand the descriptions in English.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 But U can understand it through translators like This and stuff on the Internet. Or U can just work hard on learning English(as a mid-school student in China, I always do this)
 » 3 years ago, # |   -40 UPD3: Contest has been delayed by 10 mins :)
•  » » 3 years ago, # ^ | ← Rev. 11 →   +5 are my eyes blind? why it shows and 49 + 15 = 64?
 » 3 years ago, # |   -26
 » 3 years ago, # |   -27 oh no arsijo again ;/
 » 3 years ago, # |   +3 I just missed this contest, because I stupidly assumed the announced time was on the same timezone as recent contests. Most contests recently have been announced UTC+1 (London time), whereas this one was announced on Moscow time.Any timezone would do, but it would be good if Codeforces used a consistent timezone for announcing contest start times.
 » 3 years ago, # |   -12 Amazing contest.
 » 3 years ago, # | ← Rev. 3 →   -8 Thx for the good contest
 » 3 years ago, # |   +9 contest started in time wow,CF started improving
 » 3 years ago, # |   +13
 » 3 years ago, # |   +67 Nice contest. Thanks :)Loved watching standings for 2hrs.
•  » » 3 years ago, # ^ |   +3 Your Solution to Count Pairs is awesome. ;)I was expecting you would submit it anytime.I was also watching leader board for almost one hour and then the idea struck me in last 6 mins.
 » 3 years ago, # |   +21 Half of Div1 was judged by a single problem, and even that problem is also a bad problem that relies on one observation.
 » 3 years ago, # | ← Rev. 2 →   +27 How to solve Div.2 E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +19 Hint :$(x-y)(x+y)(x^2+y^2)=(x^4-y^4)$
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Just idea — lated for submit:Let's iterate over a.Fix ai. Then you have cube equation aj^3 + Baj^2 + Caj + D ~ 0 (mod p). I assume that at least one root has to be in interval [1..1000] or [p — 1000..p]. Let's say you found that root r. Then you can reduce to square equation. And square equation can be easily solved.P.S. Sorry for this dumb reply). That was really easier than I assmued
•  » » 3 years ago, # ^ |   +28 Multiply by (x1-x2). You now have (x1^4 — x2^4) = k(x1 — x2) (mod p) this gives (x1^4 — k(x1)) — (x2^4 — k(x2)) = 0 (mod p)So you just calculate x1^4 — k(x1) for all indices then just select any two with same values.
•  » » » 3 years ago, # ^ |   0 Wow, very lame math problem.
 » 3 years ago, # |   0 Is this idea anywhere remotely close to correct solution for D2 — For any non-leaf and non-root node : Let X be the weight between node and its parent. Then after subtracting some values v_i whose sum is equal to X from edges between node and child, if we can divide them into two parts such that their sum is equal we proceed doing same thing.
 » 3 years ago, # |   -10 I surprised how easy was Div1B and why this low count of people solved it.
 » 3 years ago, # |   +6 The curve isn't very beautiful, but the problems are still really interesting! Thanks for the amazing round!
 » 3 years ago, # | ← Rev. 2 →   +64 $(a + b)(a^2 + b^2) = \frac{a^4 - b^4}{a - b}$How on earth are we supposed to know this?
•  » » 3 years ago, # ^ |   +29 This problem is more math than cp.
•  » » 3 years ago, # ^ | ← Rev. 5 →   -13 Look at roots of polynomial :D ($a=-b$, $a=ib$, $a=-ib$) add $a=b$ for symmetry.
•  » » 3 years ago, # ^ |   -9 I found it by noticing that$(a + b)(a^{2} + b^{2}) = a^{3} + a^{2}b + ab^{2} + b^{3} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{1 - \frac{b}{a}} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{\frac{a-b}{a}} = a^{3} \frac{a - \frac{b^{4}}{a^{3}}}{\frac{a-b}{a}} = \frac{a^{4} - b^{4}}{a - b}$ by the formula for geometric sum.
•  » » » 3 years ago, # ^ |   +13 No, it's not so hard to get the answer. As we all know (a+b)(a-b)=a^2-b^2,so that we can use a^2 and b^2 to replace a and b,so that (a^2+b^2)(a^2-b^2)=a^4-b^4,and a^2-b^2=(a+b)(a-b), so so that (a+b)(a-b)(a^2+b^2)=a^4-b^4, so we can get the answer.
•  » » 3 years ago, # ^ |   0 That's just a difference of two squares,but why does it be related to the problem?
•  » » 3 years ago, # ^ |   +21 Well, I think the formula $a^2-b^2 = (a-b)(a+b)$ is taught at 6'th grade (at least in Azerbaijan). So, $(a+b)(a^2+b^2)=\frac{(a+b)(a-b)(a^2+b^2)}{a-b}=\frac{(a^2-b^2)(a^2+b^2)}{a-b}=\frac{a^4-b^4}{a-b}$
•  » » 3 years ago, # ^ |   +28 Grade school math. $(a+b)(a^2 + b^2) = \frac{a-b}{a-b}(a+b)(a^2 + b^2) = \frac{a^2-b^2}{a-b}(a^2 + b^2) = \frac{a^4 - b^4}{a-b}$
 » 3 years ago, # |   +1 Cant wait for the editorials....can anyone tell about the logic of Array beauty question F in div2?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 The main idea is the beauty won't exceed $\frac{100000}{k-1}$, then you can use $\mathcal O(nkbeauty )$ dp to solve it.
•  » » » 3 years ago, # ^ |   0 Could u please elaborate. I couldn't understand the editorial.
 » 3 years ago, # |   +10 Fast System Test Start. :)
 » 3 years ago, # |   +27 Editorial is up!We hope you enjoyed the contest even though differences in difficulties were unexpected (with so many testers lol :D )
•  » » 3 years ago, # ^ |   +35 I enjoyed staring on the scoreboard.
•  » » 3 years ago, # ^ |   +13 thanks for the early editorial
 » 3 years ago, # |   +1 Solution for D1: Count the degree of each node and check if there's a node having degree equal to $2$. If yes, the answer is NO. Else, the answer is YES.
•  » » 3 years ago, # ^ |   0 please , explain proof.
•  » » » 3 years ago, # ^ |   0 Editorial is already out. Please refer to that.
 » 3 years ago, # |   0 Can problem C is solvable using segment tree ?
•  » » 3 years ago, # ^ |   0 you can find the sum using seg tree
•  » » » 3 years ago, # ^ |   0 why the answer is the (sum of [L,R])/10 ?
•  » » » » 3 years ago, # ^ |   +3 check editorial, there is a proof
•  » » » » 3 years ago, # ^ |   0 Short Answer : You are always removing a value of 10 when doing mod 10
•  » » 3 years ago, # ^ |   0 Yes, in each node keep the mod value and count of candies for that segment. submission
 » 3 years ago, # |   +1 How can we get this configuration ?
•  » » 3 years ago, # ^ |   0 Note that edge between B and F has odd cost, which is prohibited by problem statement.
•  » » 3 years ago, # ^ |   +11 With integer weights, it's impossible, note that the problem statement specifies that all numbers are even.With real weights, add for example E to F: $9.5$ E to D: $0.5$ F to C: $-0.5$ F to D: $2$ C to D: $1.5$
•  » » » 3 years ago, # ^ |   0 Okay. But for DIV2 D1 it says Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations?
•  » » » » 3 years ago, # ^ |   0 That statement doesn't contradict with the example above.
•  » » » » 3 years ago, # ^ |   +3 What about it? mango_lassi's answer shows that the answer is YES
•  » » » » 3 years ago, # ^ |   0 In D1 you can use real weights in your operations, while you can't in D2.
 » 3 years ago, # |   +3 Thanks for awesome round!!! Problems are really interesting
 » 3 years ago, # | ← Rev. 3 →   +26 So Problem C is solved by one observation that the answer doesn't exceed $\frac{100000}{k-1}$... I was thinking about how to update the dp in an efficient way throughout the whole contest ... well played.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 I came to that almost immidiately and then kept thinking about making an $n*maxBeauty$ dp $k$ times or $k*maxBeauty$ dp $n$ times until the end of the contest. And then i look at the solution and see "do $n*k$ dp $maxBeauty$ times"...
•  » » » 3 years ago, # ^ |   0 Please explain in a little more detail if u dont mind.
 » 3 years ago, # |   +3 For Div2 B, this program passed system testing but I'm pretty sure it can be hacked with the following testcase:3 1 2 356565011
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 first 3 is for n ? if your answer is yes so it's of the same type of 3rd sample
•  » » » 3 years ago, # ^ |   0 Yes the first 3 is for n. I just couldn't figure out how to write a line break there. The program outputs yes but the answer should be no.
•  » » » » 3 years ago, # ^ |   0 if(arr[0] >= arr[1] + arr[2]){ cout<<"NO"<
•  » » » » » 3 years ago, # ^ |   0 That if loop doesn't run with my testcase above. Once sorted, arr[] will be equal to {1, 2, 3}, so the if loop would be checking if (1 >= 2 + 3) which is clearly false. The program thus would print out YES which is wrong, as 3 is not strictly less than 1 + 2.
•  » » » » » » 3 years ago, # ^ |   0 this is what i thought first, but in your template you wrote #define all(a) a.rbegin(), a.rend() 
•  » » » » » » » 3 years ago, # ^ |   0 oh that's my bad then. That explains why it passed system testing. Thanks for the clarification.
 » 3 years ago, # |   0 Was locking problem D in div 2 prohibited?
•  » » 3 years ago, # ^ |   +3 Locking only D1 was prohibited as it was required to solve both problems before hacking
 » 3 years ago, # | ← Rev. 2 →   +9 In my opinion, div2 D1 has really weak pre tests. I submitted a solution checking if there was a vertice with degree == 2 as a father of a vertice with degree == 1. And it passed ... luckily I noticed it a 1 minute before de end of the contest, and corrected it ...
•  » » 3 years ago, # ^ |   +3 I believe you :D
 » 3 years ago, # |   0 i should read E instead of wasting all my time in D :c
 » 3 years ago, # |   +90 Contest starts without delays System tests start very soon after round ends System tests finish less than 45 minutes after end of round Editorial published within 10 minutes Insanely fast! I'm on vacation in Asia and this contest started past midnight, now I can go to sleep without sweating the whole night about how the systests turn out :)
 » 3 years ago, # | ← Rev. 3 →   -20 There is a huge mistake for Div2 D2. If a node has degree 2 and the weights on both sides are equal then it is possible to still construct a treeExample : Input : 3 1 2 2 1 3 2 This is a simple tree, we can do the operation 2 3 2 and construct the weights of the tree. But I tried this testcase on a number of peoples solution and they print NO.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -20 Ahh, I missed that line that said all val numbers are pairwise different and even.. My bad
•  » » 3 years ago, # ^ |   +10 Edge values should be pairwise different.
•  » » 3 years ago, # ^ |   0 your input is invalid. weights in all edges must be distinct and even
 » 3 years ago, # | ← Rev. 2 →   +7 When this is the only test you fail in A2 2 1 2 100 
 » 3 years ago, # |   0 Within an hour rating has been updated. Best and fastest checking ever.
•  » » 3 years ago, # ^ |   +18 Haha, that's because nobody solved anything!
 » 3 years ago, # | ← Rev. 3 →   +1 Good problems.
 » 3 years ago, # |   0 Problem C was interesting. I solved it using segment tree. Saw some others solving it with DP and some with cumulative sum technique .
 » 3 years ago, # |   0 Cool
 » 3 years ago, # |   0 Nice questions and editorial