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

**3.** Radewoosh

**4.** Marcin_smu

**5.** Endagorion

**Div 2**:

**1.** CSWhisky

**2.** handsomeIvan

**3.** philologist

**4.** teamskiy

**5.** NeoGul

Early blogs !! best of luck !!!!

deleted

downvote !!! that's my luck .

Savage : (please rated)

`The round will be rated for both divisions (as this time we thanked MikeMirzayanov).`

Everybody takes it seriously now!`We strongly recommend reading statements of all problems!`

Hope that the problems are correctly sorted according to difficulty.

When people downvote for no apparent reason.:(guys, can you prepare solutions of problems beforehand so we can see solutions immediately after the contest??

But solutions everytime is ready before the contest cause how authors get right answers on tests?

Savage...hahhahah

why I m getting downvotes continously just for saying savage...? Any particular reasons

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.

Well, editorial is already ready anyways :)

We plan to post it not later than in $$$10$$$ minutes after contest's end

It's cool! But it is not every time that problem setters publish their editorials just after the contests.

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 :(

I hope the statement as short as the blog :)

love short statement with no long story else I will submit sample :>

love short statement? how about love story statement

How just about love stories or love letters

how about this problem?

But if you can't solve the problem a good story might cheer you up :)

Best of luck for your first contest

The comment is hidden because of too negative feedback, click here to view it.

Nope

then,are u NaCly_Fish?

Someone used this fake username. This is not real NaCly_Fish.

I think you are not real NaCly_Fish...

atlast people have began to recognise importance of showing gratitude to Mark Mirzayanov for his codeforces & polygon platform.

Will I be able to participate in division 2?? I'm new to codeforces.

Of coures you can.

You can be able to participate in division 2 if your rating is lower than 1900.

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.)

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.

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.

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.

Tmw orz

Don't worry we will always love you tmw <3

Lets do it!

This is the result of a few refreshments on the page.

I think these differences should be corrected.

this is truly a player who believes in submitting at 1:59:59

You're a witty man. Anyway, I didn't mean to write with such an idea. :)

What about hacking at 1:59:59? ("is it correct?" during 1:50:00 to 1:59:58)

There is a "truly player" who submit at 1:59:59 :)56590817

It's really fun to join a contest after completing my final exam.Good luck for everybody.

once I post the same statement , I got approximately 30-40 downvotes...

deleted

hahah...True

what happend?

Testers Test Test

Subtasks will be unusual? Oh,that's fun.

Although it's not a good time for Chinese. I still wish everyone have fun and I wish the authors' hard work get success!

when everyone is getting downvotes but u still have 0 contribution

good job, you just joined us.

Seems like some guys are really having fun of downvoting everybody everywhere(

Codeforces: Sponsored by Telegram

As a Chinese,it's hard for me to understand the descriptions in English.

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)

UPD3: Contest has been delayed by 10 mins :)

are my eyes blind? why it shows and 49 + 15 = 64?

oh no arsijo again ;/

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.

Amazing contest.

Thx for the good contest

contest started in time wow,CF started improving

Nice contest. Thanks :)

Loved watching standings for 2hrs.

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.

Half of Div1 was judged by a single problem, and even that problem is also a bad problem that relies on one observation.

How to solve Div.2 E?

Hint :$$$(x-y)(x+y)(x^2+y^2)=(x^4-y^4)$$$

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

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.

Wow, very lame math problem.

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.

I surprised how easy was Div1B and why this low count of people solved it.

The curve isn't very beautiful, but the problems are still really interesting! Thanks for the amazing round!

$$$(a + b)(a^2 + b^2) = \frac{a^4 - b^4}{a - b}$$$

How on earth are we supposed to know this?

This problem is more math than cp.

Look at roots of polynomial :D ($$$a=-b$$$, $$$a=ib$$$, $$$a=-ib$$$) add $$$a=b$$$ for symmetry.

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.

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.

That's just a difference of two squares,but why does it be related to the problem?

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}$$$

Grade school math.

Cant wait for the editorials....can anyone tell about the logic of Array beauty question F in div2?

The main idea is the beauty won't exceed $$$\frac{100000}{k-1}$$$, then you can use $$$\mathcal O(nkbeauty )$$$ dp to solve it.

Could u please elaborate. I couldn't understand the editorial.

Fast System Test Start. :)

Editorial is up!

We hope you enjoyed the contest even though differences in difficulties were unexpected (with so many testers lol :D )

I enjoyed staring on the scoreboard.

thanks for the early editorial

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.please , explain proof.

Editorial is already out. Please refer to that.

Can problem C is solvable using segment tree ?

you can find the sum using seg tree

why the answer is the (sum of [L,R])/10 ?

check editorial, there is a proof

Short Answer : You are always removing a value of 10 when doing mod 10

Yes, in each node keep the mod value and count of candies for that segment. submission

How can we get this configuration ?

Note that edge between B and F has odd cost, which is prohibited by problem statement.

With integer weights, it's impossible, note that the problem statement specifies that all numbers are even.

With real weights, add for example

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?`

That statement doesn't contradict with the example above.

What about it? mango_lassi's answer shows that the answer is YES

In D1 you can use real weights in your operations, while you can't in D2.

Thanks for awesome round!!! Problems are really interesting

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.

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"...

Please explain in a little more detail if u dont mind.

For Div2 B, this program passed system testing but I'm pretty sure it can be hacked with the following testcase:

3 1 2 3

56565011

first 3 is for n ? if your answer is yes so it's of the same type of 3rd sample

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.

this should be enough to output no and this is what i got after trying this test on your code in custom

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.

this is what i thought first, but in your template you wrote

oh that's my bad then. That explains why it passed system testing. Thanks for the clarification.

Was locking problem D in div 2 prohibited?

Locking only D1 was prohibited as it was required to solve both problems before hacking

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 ...

I believe you :D

i should read E instead of wasting all my time in D :c

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 :)

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 tree

Example :

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`

.Ahh, I missed that line that said

`all val numbers are pairwise different and even.`

. My badEdge values should be pairwise different.

your input is invalid. weights in all edges must be distinct and even

When this is the only test you fail in A2

Within an hour rating has been updated. Best and fastest checking ever.

Haha, that's because nobody solved anything!

Good problems.

Problem C was interesting. I solved it using segment tree. Saw some others solving it with DP and some with cumulative sum technique .

Cool

Nice questions and editorial