antontrygubO_o's blog

Codeforces Round #572
By antontrygubO_o, 5 years ago, translation, In English

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 244mhq. 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, gop2024, 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

  • Vote: I like it
  • +621
  • Vote: I do not like it

Comments Comments (128)
| Write comment?
»
5 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Early blogs !! best of luck !!!!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -73 Vote: I do not like it

Savage : (please rated)

→ Reply
»
5 years ago, # |
  Vote: I like it -36 Vote: I do not like it

The round will be rated for both divisions (as this time we thanked MikeMirzayanov). Everybody takes it seriously now!

→ Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +31 Vote: I do not like it

We strongly recommend reading statements of all problems!

Hope that the problems are correctly sorted according to difficulty.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +153 Vote: I do not like it

    When people downvote for no apparent reason. :(

    → Reply
»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

guys, can you prepare solutions of problems beforehand so we can see solutions immediately after the contest??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +161 Vote: I do not like it

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +83 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +151 Vote: I do not like it

      Well, editorial is already ready anyways :)

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I hope the statement as short as the blog :)

→ Reply
»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Best of luck for your first contest

→ Reply
»
5 years ago, # |
  Vote: I like it -151 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Of coures you can.

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +63 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Lets do it!

→ Reply
»
5 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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

I think these differences should be corrected.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +240 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -20 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -36 Vote: I do not like it

when everyone is getting downvotes but u still have 0 contribution

→ Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Codeforces: Sponsored by Telegram

we'll be on the community Discord server to discuss the tasks

→ Reply
»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    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)

    → Reply
»
5 years ago, # |
  Vote: I like it -40 Vote: I do not like it

UPD3: Contest has been delayed by 10 mins :)

→ Reply
»
5 years ago, # |
  Vote: I like it -26 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it -27 Vote: I do not like it

oh no arsijo again ;/

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Amazing contest.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Thx for the good contest

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

contest started in time wow,CF started improving

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Nice contest. Thanks :)
Loved watching standings for 2hrs.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

How to solve Div.2 E?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +64 Vote: I do not like it

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

How on earth are we supposed to know this?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    This problem is more math than cp.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it -13 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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} $$$
    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Fast System Test Start. :)

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Editorial is up!

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

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem C is solvable using segment tree ?

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How can we get this configuration ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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$$$
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That statement doesn't contradict with the example above.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for awesome round!!! Problems are really interesting

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        if(arr[0] >= arr[1] + arr[2]){
	cout<<"NO"<<endl;
	return 0;
}

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            #define all(a) a.rbegin(), a.rend()
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was locking problem D in div 2 prohibited?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +90 Vote: I do not like it
  • 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 :)

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -20 Vote: I do not like it

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 : 

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Edge values should be pairwise different.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

When this is the only test you fail in A2

2
1 2 100

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Good problems.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool

→ Reply