antontrygubO_o's blog

By antontrygubO_o, 4 months 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 kefaa2. 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, GandalfTheGrey, progmatic2, zoomswk, ecnerwala, AllCatsAreBeautiful, DmitryGrigorev, Markellonchik, dasfex, Taran_1407, slicedclementines, 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. esbee

2. handsomeIvan

3. philologist

4. teamskiy

5. NeoGul

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

»
4 months ago, # |
  Vote: I like it -52 Vote: I do not like it

Early blogs !! best of luck !!!!

»
4 months ago, # |
Rev. 2   Vote: I like it -73 Vote: I do not like it

Savage : (please rated)

»
4 months 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!

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +153 Vote: I do not like it

    When people downvote for no apparent reason. :(

»
4 months 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??

  • »
    »
    4 months 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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +161 Vote: I do not like it

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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.

      • »
        »
        »
        »
        4 months 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 :(

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I hope the statement as short as the blog :)

»
4 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Best of luck for your first contest

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.)

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Lets do it!

»
4 months 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.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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. :)

    • »
      »
      »
      4 months 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)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So many testers lol

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Testers Test Test

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
4 months 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!

»
4 months ago, # |
  Vote: I like it -36 Vote: I do not like it

when everyone is getting downvotes but u still have 0 contribution

»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

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

»
4 months 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

»
4 months 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.

  • »
    »
    4 months 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)

»
4 months ago, # |
  Vote: I like it -40 Vote: I do not like it

UPD3: Contest has been delayed by 10 mins :)

»
4 months ago, # |
  Vote: I like it -26 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -27 Vote: I do not like it

oh no arsijo again ;/

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Amazing contest.

»
4 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Thx for the good contest

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

contest started in time wow,CF started improving

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +67 Vote: I do not like it

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

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

How to solve Div.2 E?

  • »
    »
    4 months 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)$$$

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months 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.

»
4 months 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!

»
4 months 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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    This problem is more math than cp.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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?

  • »
    »
    4 months 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}$$$

  • »
    »
    4 months 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} $$$
»
4 months 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?

  • »
    »
    4 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Fast System Test Start. :)

»
4 months 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 )

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem C is solvable using segment tree ?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How can we get this configuration ?

  • »
    »
    4 months 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.

  • »
    »
    4 months 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$$$
    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That statement doesn't contradict with the example above.

      • »
        »
        »
        »
        4 months 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

      • »
        »
        »
        »
        3 months 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.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for awesome round!!! Problems are really interesting

»
4 months 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.

  • »
    »
    4 months 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"...

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 months 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

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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()
            
            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was locking problem D in div 2 prohibited?

  • »
    »
    4 months 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

»
4 months 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 ...

»
4 months 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

»
4 months 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 :)

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -20 Vote: I do not like it

    Ahh, I missed that line that said all val numbers are pairwise different and even.. My bad

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Edge values should be pairwise different.

  • »
    »
    4 months 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

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Good problems.

»
3 months 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 .

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice questions and editorial