McDic's blog

Codeforces Round #633
By McDic, history, 2 years ago, In English

내가 돌아왔다! (Hello, Codeforces!)

I am thrilled to introduce you to Codeforces Round #633. Followings are basic information:

  • This contest will take place on Apr/12/2020 17:05 (Moscow time).
  • The round is rated for all participants who can understand this announcement. There will be two divisions.
  • There are 5 problems in each division and you will have 2 hours to solve it.
  • Score distribution will be announced later.

Followings are contributors:

Followings are some fun things:

  • antontrygubO_o is the most intense coordinator I have ever met. He rejected lots of my problems. Some example of rejection comments are below:
    • This problem is too standard.
    • Don't ask people about theorem and formula.
    • This problem is appeared in recent ptz camp with higher constraints.
    • I don't like it.
    • Rock Scissor Paper makes statement messy, because some people don't know about it.
    • D2A should be easier than this one.
    • I've found generalized version of this problem in POI.
    • Isn't this obvious?
    • Your proof is wrong.
    • This problem is not very interesting.
    • This is too (censored).
  • After lots of rejections, I tried my best to make problems to be interesting. I hope you like at least some of my problems.
  • This round was originally supposed to be rated for Div.2 only. However, after we completed Phase 1 testing, we found that my round is too hard for Div.2, so we added more problems and made this round to be Div.1.
  • In this round, statements will be even shorter than last contest.
  • Even for some of problems which my coordinator approved, there were critical issues that made problems to be excluded. I will introduce some of my rejected problems which won't be used anymore in another post, after this contest ends.

I hope everyone can enjoy my third contest. Thanks in advance!

Followings are updates:

  1. Score Distribution:
    • Div.1: 500 1000 1500 2000 2750
    • Div.2: 500 750 1250 1750 2250
  2. I am sorry for such Div2C/Div1A statement issue. We fixed that immediately after few minutes to the round, but we should have announced it.
  3. Editorial is posted: https://codeforces.com/blog/entry/75913
  4. I opened new mashup for excluded problems. These problems are originally approved by antontrygubO_o but excluded for some reasons.
    1. Binomial Determinant is old Div1D. We found this problem on google so we removed this.
    2. Divisible Xor is old Div1A. But since we made 3 xor problems, we removed this one.

Followings are winners:

<Div.1>

  1. tourist
  2. Radewoosh
  3. TLEwpdus
  4. ecnerwala
  5. gisp_zjz
  6. Maksim1744
  7. scott_wu
  8. Petr
  9. jiangly
  10. maroonrk

<Div.2>

  1. Nachia
  2. MyAngelBakapiano
  3. 0.142857
  4. kekekeke228
  5. LeierKing
  6. Ka_ng_Hyeon
  7. Anithas_love_for_tries
  8. confeito
  9. TOPCYBERFLOWER
  10. wattaihei
 
 
 
 
  • Vote: I like it
  • +1622
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +94 Vote: I do not like it

In this round, statements will be even shorter than last contest.

I hope we will enjoy the problems. Thanks.

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

hope the statements will be as short as the announcement

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

WOW! Statements will be short let's see :)

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

Is It Rated?

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

    The round is rated for all participants who can understand this announcement.

    Don't you see it !!

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

      Can I decide after the contest if I understand the announcement? xD xD

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

so the round is going to be tough a bit , we are ready to face it and enjoy according to question haha.

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

Are McDic and dick related?

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

YES

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

I've found generalized version of this problem in POI.

A full trilogy of horror movie starts with this sentence...

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

who can understand this announcement

The task conditions will only be in English?

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

    ah, no, there will be Russian statements available too.

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

10 April to 15 April. There are 4 contests where I can participate. (Educational round 85,div2,div3,div2 again). Wow! Thanks to the authors who worked so hard to make our quarantine life happy. Thanks to codeforces too!

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

    Unless if you get a rating increment after div 2 rounds such that you are no longer in div 3 :)

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

Be prepared for the interesting behind story of every problem :)

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

Just saw the contests page!! I literally got chills seeing the list of upcoming contests!! Thank you MikeMirzayanov as well as all the other writers for the upcoming contests!!

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

Looking forward to McDic x Twice round!

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

This Problem is too (censored) xD.

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

i hope we will enjoy this round

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

Everyone, Look out for the unusual start time

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

antontrygubO_o X McDic

https://codeforces.com/blog/entry/70141

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

.

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

is there a hacking phase after this round?And can Div3 people write it ?

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

    Hacking phase is generally for educational rounds and Div.3 rounds as this a classic Div.1 and Div.2 round there's no hacking phase and if a hacking phase is there it would be mentioned in the announcement and yes anyone who has rating below 1900 can give Div.2 round.

    EDIT: Since you seem new, people can hack each other's solution, if they're in the same room(all registrants are divided into rooms), during the contest. But after the contest there's no hacking phase.

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

In this round, statements will be even shorter than last contest.

And I instantly love it!

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

when the editorials will be published i am curious to see the editorials....Thanks in advance to the problem setters who have setted the problem so good and interesting..

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

Thanks to the whole team, I don't know what I'd be doing in these quarantine days if you were not there making these amazing problems!!!

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

Omg it's McDic round

McDic orz

(Pls don't troll me again)

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

I bombed my last round so I hope I can do well on this one.

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

Please Make strong test case ... And thanks CF for making more contest in our bad time to increase our ability..

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

Hope pretests are strong !!

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

..

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

In this round, statements will be even shorter than last contest

Hopefully longer than April fools contest.

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

mcdicorz

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

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

"(censored)"

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

Perhaps you can create a Gym with the rejected problems. :)

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

McDic orz! Even though you were assigned such a ruthless coordinator you kept on creating problems and came up with this geniosity round. McDic is so good I wish I had 1/x where x>1e9 of McDic's problemsetting skill.

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

I really liked this blog and I am very excited to participate in your round after reading it!

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

Is it true that tzuyu_chou is the real Tzuyu Chou from Twice?)

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

    no

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

    Yes

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

      Dude don't know whether you are joking or saying the truth.But I will be honest I have seen this profile and I am awestruck how fast he/she improved from the first code he/she submitted like within 2 months to international grandmaster and I wish I can have that level of motivation and dedication in this time of quarantine. Thanks tzuyu_chou for motivating me...

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

        Whether tzuyu_chou is the singer from Twice or not, it's pretty clear that they were already highly skilled when "their first code was submitted". So it's not some 2 month newbie->IGM miracle story.

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

          You are underestimating Tzuyu's skill. If she can sing as well as she does in Twice music, surely she has the talent to go newbie->IGM that quickly ;).

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

Loved the rejection comments part

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

I hope it will be easy so that I can enjoy the problems.

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

"statements will be even shorter than last contest", if so than it will be really good for everyone I hope. Cz, long statement is so boring...

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

isItrated

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

Wow, interesting "Fun" statistics! We are equally thrilled to take part in the contest :D

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

Haha, long queue again.

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

Very interesting blog! Good coordinators help organize high-quality rounds in Codeforces and I am grateful.

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

Hope that codeforces won't shut down tomorrow :)

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

hey no one has yet asked whether this contest is rated or not?? P.S — i know it is ! But some people still ask the question ;)

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

Well, how about a separate section for memes in code forces?

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

Your proof is wrong.

Well this doesn't sound like a very unreasonable explanation for rejecting a problem..

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

For the first time I am seeing someone coming with score distribution this early.

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

waiting for formula and theorem forces...

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

Is tzuyu_chou going to perform a private live concert for the winner of this contest (of course after coronavirus ends)?

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

    Unfortunately, she already did it for organizers and testers of the round.

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

    That would be the most serious I've ever been in a contest...

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

As some people strongly requested, I post one of archived funny conversations here:

img

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

Short statements, 5 questions. Quality will be epic! Looking forward to participating.

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

Is iterated?

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

fan ei ae yo

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

After we completed Phase 1 testing, we found that my round is too hard for Div.2...

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

Good Luck everyone

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

Back to back rated contest , I am enjoying it and after knowing questions are going to be shorter as compared to usual ones ,felling more excited.

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

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

5 problems in 2 hours?? "In this round, statements will be even shorter than last contest.", i hope it would make the contest interesting.

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

Just look at the number of upvotes for the announcement of the contest. It is way more than average.

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

Lots of contest in this week ...

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

I am registered in Div1 and Div2 bcz of my recent rating change XD. What happens now? Screenshot-from-2020-04-12-12-52-18

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

    I think you will be moved automatically, I'm in a similar situation.

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

    Participate in Div1. If predictor says -ve delta just resubmit them in div2 to compensate.

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

In this round, statements will be even shorter than last contest.

(looks at 1329C - Drazil Likes Heap) That's not so impressive.

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

I'm ready for the contest. Good luck and high rating !

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

how many questions do u need to solve to hit specialist??...in a DIV 2 contest I AM DESPERATE!!!!!!!!!

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

    It's an ELO System, so it depends on how the others perform. To be honest, it will probably be enough to solve just one problem (or maybe 0), since the base rating is 1500.

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

Gulag: It's time to earn your freedom

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

A long queue in submissions right now. Server was down yesterday. I hope it doesn't happen in the contest.

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

how many questions would a pupil need to solve in a regular DIV 2 contest to hit specialist???

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

tourist doesn't register the contest yet ?

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

Will there be contest today considering the server problem?

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

McDic [user:MikeMirzaynov] I do not know if this is happening only with me, the submission takes a lot of time to get checked since past few days. I request you to make sure that the same does not happen when contest is running. Thanks, Kushal Shah.

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

233E - Doe Graphs

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

    I would be more worried about the opposite thing — in such situations people sometimes want to prove that they can prepare really hard problems and eventually round becomes too difficult.

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

    Don't forget he is the author of 3400 rated problem.

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

hope that the round does not turn out to be unbalanced, 5 problem contests are unbalanced more often than not :(

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

juicy round :)))

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

(MikeMirzayanov) Is it just me, or m3.codeforces.com is not working? (403 Forbidden, nginx/1.16.1)
m1, m2, and the main site are okay, though.

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

I predict Div2C will be a math problem and Div2D will be a graph problem.

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

I hope I become specialist in this round. And expert sometime sooner.. :)

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

i need help. i understand the question but i fail to implement the logic and my code are never optimized.. please any suggestion.

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

All the best guys !!!

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

Hey, for some reason my registration did not work, I cannot submit!!!

:/

→ Reply
»
2 years ago, # |
  Vote: I like it -39 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces

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

Please stop creating problems.

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

Thor is reading F just after D. Thor Fill in the Blank? XOR

→ Reply
»
2 years ago, # |
  Vote: I like it -34 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Statements are short, but damn are my ideas wrong.

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

ridin ba in contestaye shokhmitoon

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

Your problems are excellent, but please consider the difficulty distribution of the problems. I think "After Solving ABC" might appear in one of the comments after the contest.

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

    If that's the case, then there's no solution. Contests are not meant to be solved fully by everyone smh

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

I hope I won't see soon more "guessing pattern shit" problems like today $$$C$$$. Other problems were nice and interesting for solving.

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

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

When the first place becomes two

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

Really disliked problem Div1 C. Somewhat disliked Div1 D but I haven't seen the solution yet so I am giving it the benefit of the doubt. The former was just bad, though.

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

    Can you explain why? I think both were fine.

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

      The simplest way to solve Div1 C is to write a bruteforce and find a pattern. This doesn't require any CS-related skills and often feels like a maths competition.

      Div1 D probably boils down to some DP on a tree, and I don't mind it, but it's just not pleasant to try and figure it out in terms of these loops. It feels like it's a really straightforward solution hidden by a really unpleasant abstraction.

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

    I think D is a really nice problem. C is not something spectacular, but I think it is refreshing to see some "code and see pattern" problem from time to time and I don't think they are fundamentally wrong.

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

Wtf was pretest 3 of C?

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

gg

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

Tourist is back to the top.

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

Can someone explain why 1D was not maximal independent set on a tree? :(

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

    Look at the sequence of bands $$$b_1, b_2, \dots, b_k$$$ that form an answer. For each vertex $$$v$$$, if $$$v$$$ is adjacent to $$$b_l$$$ and $$$b_r$$$, it must be adjacent to each $$$b_i$$$ for $$$l \leq i \leq r$$$

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

how to do Div2.C/Div1.E?

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

    exchange 1 with 2.

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

    Brute force a bunch of values and observe the pattern for all the $$$a$$$, $$$b$$$, and $$$c$$$ values separately, assuming you're talking about Div2E/Div1C.

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

      What's the pattern? jef

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

        The bits of the middle col go like 00 10 11 01 and the right col like 00 11 01 10

        List in binary
        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      And what pattern is?
      I found that indices 3i forms 1, 4-7, 16-31, 64-127, and so on. But indices 3i + 1 not lies in any pattern I can assume). Indices 3i + 2 is just 3i ^ (3i + 1).

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

        I didn't have time to figure it out completely, but the $$$b$$$ values in binary looks like this:

        Spoiler

        The bit at index $$$i$$$ has a period of $$$2^{i+2}$$$ for even $$$i$$$ and $$$2^{i+1}$$$ for odd $$$i$$$, after the first few values.

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

        If you print $$$a, 2 a - b$$$, you get a pattern in blocks of $$$4^i$$$.
        And blocks of $$$4^i$$$ can be seen as a repetition of smaller blocks of size $$$4^{i-1}$$$.

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

How to solve Div2 B and C?

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

    B. just sort the array and pick "last-first", "2nd last- 2nd"....done.

    C. find index 0<=i<j<n such that arr[i]>arr[j]. find Max= (arr[i]-arr[j]) over all such pair using prefix_max and then find least (k+1) s.t. 2^0+2^1+....+2^k>=Max. done!

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

    Div2 B: Sort the array. alternatively, put the last and first element to the end of resultant array.

    Div2 C: create a auxiliary lmax[], lmax[i]: max ele upto ith ele from beginning of the array. let cur[i]=lmax[i]-arr[i], res = OR of all cur[i], output the log2(res)

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

      Could you elucidate Div2 C, please?

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

        Notice that any integer can be formed by summations of powers of 2 (e.g. 0b1101 is just sum of 2^0 + 2^2 + 2^3 and so on) so you just have to find the max drop(i.e. max diff a[i] — a[j] where i < j). If max diff <= 0 then you already have a non-decreasing array so your done. If it's greater than zero, than just find the smallest x where 2^x — 1 >= max diff and you are done.

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

        See Here . I hope it helps

        → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    For B:
    • sort the array
    • fill result array like (a[1],a[n], a[2],a[n-1], a[3],a[n-3] ...)
    • reverse result
    • print result
    For C:
    • for all values of x in (0,35) check whether you can create non-decreasing seq
    • to check, assume you have (1<<(x+1)-1) available to be added to any element
    → Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

endless XOR……

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

How to solve div2 D?

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

Video tutorial for div2C/div1A

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

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

is DIV 2 B tough or what??

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

    Nope simple! just sort the array and pick "last-first", "2nd last- 2nd"....similarly...done.

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

I've never seen a better/prettier Problem A. Great Job!!

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

    How to solve? Was the answer just n?

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

      Yes

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

      Once you set a vertical diamond, observe that you are forced to use horizontal diamond in other places. Lets say n=3 then we will have VHH. HVH amd HHV where V is vertical and H is horizontal diamond. That's why answer is n.

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

      Yeah and by just checking how to cover the top left triangle, you get the recurrence F(n) = 1 + F(n-1) along with F(1) = 1

      Which means the answer is simply n

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

For Div2.C

76384708 — used log2() to find the most significant set bit. WA on pretest 3.

76387989 — Removed log2() and wrote a loop. Pretest Passed.

Why?

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

    Floating precision errors, maybe? It's good practice to always avoid using floating point operations unless absolutely necessary.

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

    log2 is a floating point function, so it's imprecise.

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

      Is there any other function which can be used to find the most significant set bit of a number?

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

        31 - __builtin_clz(x)

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

          __lg(x)

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

            I prefer __builtin_clz because it's actually documented and meant to be used by programmers.

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

              I'm sorry but that sounds like a really dumb reason to not use what has been provided.

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

        I ran a loop from j=0 to j=31 and checked if 2^j>number (where ^ here is power). It's not an O(1) thing but it's log(10^9) and doesn't increase the overall complexity by much.

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

    You should type cast log2, otherwise, there can be overflow on converting double to long long

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

    language precision problem —

    4.0000000 can be 3.999999999

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

    you either took floor of log or ceiling.

    If floor then floor of log(5) is 2 while the most significant bit is the third.

    If you took ceiling then ceil of log(8) is 3 while the most significant bit is the fourth.

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

    same happened to me I just put (int) before log2

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

    Same problem with me too. Loop is working

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

>tfw probably finished coding D minutes after the end

My idea for div1D: for a sequence of vertices on a path, get (sum of their degrees) — (number of adjacent pairs at distance 2) — 2 * (number of pairs at distance 1). The answer is the maximum of this value, simple DP.

UPD: Also minus (number of adjacent pairs at distance 3).

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

    Sorry if I'm missing something simple, but what does it mean to be an adjacent pair at distance 2? Doesn't adjacent imply that they are at distance 1?

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

      Adjacent in the sequence of vertices I mention — such that the vertex between them isn't in the sequence.

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

What an amazing contest ! Each of the problems required good thought (except maybe C). This is not the first time McDic held back some problems while setting up a contest. I look forward to hearing the remaining problems which were not published as part of this contest !

Also, can someone please share the solution for Div 2 $$$E$$$ or Div 1 $$$C$$$ ?

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

    Brute force, print in binary, and find the pattern.

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

    IT's a greedy solution.

    you will observer that first element of triplet is all elements of even power of two, 1,-,-,4,-,-,5,-,-,6-,-,7,-,-,16,-,-...

    after this you can get n lies in which triplet.

    convert 1st element into binary,

    subdivide binary string to set of 2 elements and replace {'11':['01', '10'], '10':['11', '01'], '01':['10', '11'], '00':['00', '00']}.

    you will get what to append at 2nd and 3rd element.

    and [1st, 2nd, 3rd][n%3] is your answer

    my sol — 76392709

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

      its the first time ever i got the write logic for div 2 E i m literally so fukin happy ...

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

Can some one suggest me some similar problems with today's div2 a, b? I didn't understand a correctly and couldn't solve b..It will be helpful. Thank you.

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

    Never seen a task similar to B. I have first set constraints of what are the possible solutions to the problem and then started juggling with different ways to traverse an array. The first intuition that I got was that probably we need to sort an array (but I wasn't sure about that). Usually, when you set some structure, that simplifies your task (whatever that task is). If you just go through indices from 0 to n or in reversed order from n to 0 in a sorted array that doesn't solve the problem. I started thinking of what is breaking when you simply traverse array in a sorted order. The next thing I tried in my mind is to traverse from some other starting point from a[i] to a[n]. That also failed. Then I thought if I have set first two elements in a sequence a[i], a[i + 1] what should the third element be in order to guarantee an increasing sequence? a[i], a[i + 1], a[x???].

    After that, somehow my brain had aha moment and came up with a sequence a[i], a[i + 1], a[i — 1], a[i + 2], a[i — 2], ....

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

      What is about? What does the problem even meant by "2 coverings are different if some 2 triangles are covered by the same diamond shape in one of them and by different diamond shapes in the other one."?

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

        What does the problem even meant by

        Oh, I also didn't understand that description and simply ignored it. I just went straight to example at the bottom and worked through it myself. Then I interpolated the example with n = 2 to n = 3 and started thinking hard about the case when n = 3.

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

D is another stupid tree dp. It seems antontrygubO_o wasn't harsh enough.

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

    I feel like this is a case when novelty of the setting justifies a somewhat standard solution.

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

      For me, "new but has a simple standard solution once you figure out a basic condition" isn't good enough for div1D. It depends on the condition and if it is what I mentioned above, that's at most div1C level.

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

        aid's concern seems to be not with the difficulty, but the problem itself. Anyway, judging by the standings it doesn't seem that poorly placed after all.

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

          Well, his comments starts with "D is", so the fact that it's D should be relevant.

          We can't compare difficulties by number of solutions alone. Most people solve A-E, so the letter and difficulties of previous problems matter. Most people will be intimidated by the fact that it's D with a geometrical statement — I know I almost was. If it was B, it would've definitely had more solutions.

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

            How else does one refer to a problem?

            If you have in mind some other requirements for a problem to be suitable, say, for a div1D, I'm curious to listen. It seems to me that a lot of people expect something along the lines of "$$$\geq x$$$ lines of code/$$$y$$$ sheets of formulas", but there are so many more interesting ways to give a good challenge.

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

              How else does one refer to a problem?

              Would "A is another stupid tree DP" sound exactly the same?

              If you have in mind some other requirements for a problem to be suitable, say, for a div1D, I'm curious to listen.

              X lines of code / y sheets of formulas would be just as bad, since it would still be "spot this standard thing and type fast". For me, the requirement for any problem is that the solution is sufficiently unique for people at its level. Some variation in this is okay, but such problems are still disappointing for me.

              I actually guessed the pattern directly from example case 2, but proved that it makes sense just in case. That's how straightforward solving it was.

              I would've swapped C and D just because of this. C wasn't that hard either but it would've probably been an interesting D for more high reds.

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

                Would "A is another stupid tree DP" sound exactly the same?

                Luckily we're not there yet for such comments to appear. =) Anyway, I didn't mean to say I knew exactly what aid was thinking.

                the solution is sufficiently unique for people at its level

                Totally second this, but isn't reducing the setting to familiar terms a crucial part of the solution? AtCoder problems are a great example of this, when it's smooth sailing after one good observation, but it can take ages to make.

                On a different point, with problems like this perceived difficulty can vary a lot. We can agree that the solution is simple, but there are lots of high-rated people who didn't solve it with an hour to go.

                My take is that the problems like this are just not commonplace, outside of the current meta. This makes discussions about "good position" and "people with high enough rating" moot since none of these correlate well enough with ability to solve such problems. I, for one, would be happy to see such problems appear more often, but that's a matter of taste, of course.

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

                  Yeah, Atcoder problems are a good measuring stick here. I can think of two that fit the "spot simple solution" mold, but have their own twists on it:

                  • AGC040 E (div1D): The $$$O(N^2)$$$ DP is simple enough, but you also need to notice that only $$$O(N)$$$ states are meaningful. I actually didn't spot it, but it's not that hard.
                  • AGC027 E (div1D-E): A lot of obvious observations (like that each resulting letter corresponds to an initial substring) led me to a simple greedy solution that's also wrong. I needed to fix it, getting a more complicated greedy.

                  A twist like that is what I'm missing in this div1D. It's okay to have such problems, they're just not very interesting to me.

                  As for difficulty, if we're really going by the number of solutions, the previous D had 21 solutions in-contest and it wasn't particularly difficult, just harder to implement if you didn't have the right tools (see my solution where I just pasted my treap). The previous D in a 5-problem div1 round (618) had 28. This one had 92.

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

    Huh, I think that understanding the setting and what the answer looks like is the main part of the problem and quite a lot of thinking. Dp is indeed extremely easy, but what's wrong with that?

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

      Well, to me this part was just looking at the picture for the first sample carefully, so I didn't find it interesting.

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

        All LGM testers failed to figure this for a hour.

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

          You shouldn't judge testing by the standings alone. You didn't talk with me and I don't know what antontrygubO_o told you, but I think that total time I spend on this problem is less than one hour.

          It doesn't mean I think that the problem is easy, or bad, or unsuitable for div1D position. I think it is on better side of this round.

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

    Dp alone is of course not fascinating, but I find the understanding of the structure in this proble quite amusing (which is of course main part of the solution) and I really liked it.

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

      My approach to solving that problem was ignoring the geometrical structure as much as possible... I guessed what to do from the sample explanation and kinda-proved that it makes sense. Basically: ok, so we want a sequence of paths with length $$$\ge 2$$$ where we can always backtrack at most 1 edge from the previous path, what happens if we backtrack more?

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

    Another comment: job of coordinator shouldn't be to reject problems that aren't amazing, it's to reject problems that are unsuitable or obviously bad. Otherwise the bar for problems will be too high.

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

      I just read the blog and saw these phrases:

      This problem is too standard.

      I don't like it.

      Isn't this obvious?

      This problem is not very interesting.

      So I had high expectations.

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

      I disagree with this; you don't want your contests to be "solve this query on tree problem for the 13245th time with minor modifications"; that's boring to everyone involved and then the standings are just a measure of how fast you can implement tedious standard problems.

      rng_58 takes the stance of not setting a contest with problems he doesn't like, and everyone not named Radewoosh seems to appreciate his coordination job a lot (both in old topcoder rounds and recent atcoder ones).

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

        It is April and AtCoder has had how many Div1 contests this year? If I count correctly, one?

        EDIT: response to below: that's partly byproduct of differences in way contest are curated, if you consider how many quality problems are featured in Div1 CF vs Div1 AtCoder in last year, CF wins at least for me. (no new comment as it's not so useful conversation)

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

          It has been 10 years and Codeforces has had how many comparable by quality contests?

          You have a point, obviously, but the other side also has.

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

          If you want more contests with problems between a very high bar and a relatively high bar, please try our ARCs (orange-circled contests). I think they are enjoyable for reds, and sometimes not too easy to solve everything.

          Of course, I'm well aware that the number of contests is not so large even if we count ARCs. I'm sorry for that — we ran out of good ideas, and I feel it's time to change the generation. So, now I'm trying to share my experience with writers and maroonrk, and next year he will give fresh ideas. I hope the situation will get better then.

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

Would this work in E?

First notice that for any node D, the edges induce a total order of the nodes that have edges towards D. That is due to that special property. Next, notice that any graph has at least one node with in-degree over N / 2. Choose the one with the highest degree and attempt some sort of centroid decomposition: divide the nodes in 2 halves based on whether they point towards D (set A) or D points to them (set B). The ones that point to D form a total order via above observation. There's plenty of complex case work for computing the min distances that are obtainable while using nodes from both sides. The main algorithm basically treats these cases and then recurses on B. By the choice of D, these are at most N / 2, so you have at most logN recursive calls on exponentially smaller subgraphs which amortizes to N^2. Also, note it's important in the casework part that you choose D to be the one with biggest indegree because this guarantees that all nodes in A, have at least one node in B they point to (if this wasn't so, then those nodes that are pointed to by D and all of B have a higher indegree so would've been a better choice of D). Considering the cases it appears that all min-distances will be either undefined (so 614N) or at most 5. It may also be the case that you need to first recurse and then consider paths that go through both A and B.

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

    It's pretty easy to show that the min distance is at most 3 or it is undefined.

    Suppose that the min-length path from $$$a$$$ to $$$e$$$ is $$$a\to b\to c\to d\to e$$$. Then $$$a,c,d,e$$$ will form the forbidden subgraph.

    EDIT: Fixed.

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

      $$$a, c, d, e$$$, not $$$b, c, d, e$$$

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

.

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

XorForces

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

Div1C is the most beautiful problem I ever solved)

UPD. OK, some people don't like 000/123/231/312 pattern

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

    Can you explain it?

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

      Let's notice that $$$4^n - 4^m$$$ is divisble by $$$3$$$. We can group numbers from $$$1$$$ to $$$4^{n-1}$$$ into triples.

      If {$$$a, b, c$$$} is the lexicographically smallest triple where $$$a \geq 4^k$$$ then {$$$4 * a, 4 * b, 4 * c$$$} is the lexicographically smallest triple where $$$a \geq 4^{k+1}$$$.

      How to find next triple after {$$$4 * a, 4 * b, 4 * c$$$}? We know that $$$(4*a) \oplus (4*b) \oplus (4*c) = 0$$$ and last two bits $$$4*a$$$ are $$$0$$$.

      It means that {$$$4*a+1, 4*b+2, 4*c+3$$$} is the next triple (after it {$$$4*a+2, 4*b+3, 4*c+1$$$} and {$$$4*a+3, 4*b+1, 4*c+2$$$})

      $$$x = ((k+2)$$$ % $$$4$$$)

      So if we want to find $$$k$$$-th triple {$$$a1, b1, c1$$$}, we can find $$$(k+2)/4$$$ triple {$$$a, b, c$$$}, multiply it by 4 (because $$$a = a1 / 4$$$, it can be proved) and add {$$$0, 0, 0$$$} (if $$$x = 0$$$) or {$$$1, 2, 3$$$} ($$$x = 1$$$) or {$$$2, 3, 1$$$} ($$$x = 2$$$) or {$$$3, 1, 2$$$} ($$$x = 3$$$)

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

I have 1 hour to solve D but still didn't complete it. After discovering my first approach didn't work, i think it seems like using LCA. Hope next time :(

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

Did some very weird thing for div-2 D and somehow worked.

First, we find the lower bound. We claim that it's equal to 1 if all leaves are an even distance from each other (indeed, just set each value equal to each other and use the fact that aXORa =0). If any two leaves have an odd distance from each other, then the lower bound is 3 (but I don't know how to prove this -- it's probably some construction).

For the upper bound, we note that if we have a sequence between two leaves that have more than 2 edges, then we can set all the values on the path distinct. If there are only two edges, we need the values to be equal. Thus, in both cases, the upper bound is equal to n-1-k, where k is the number of pairs of leaves that are 2 edges apart.

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

    Why is this weird? This just seems like the correct solution.

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

      Maybe weird was too harsh -- it's just that I barely convinced myself that this worked during the contest. I took a leap of faith and it worked I guess.

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

        Ah, the good old proof by AC. Helps for some contests but it's also useful to make sure you know the correct reasoning after the editorial comes out :)

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

          for the upper bound why is possible to give all other edges different values?

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

    For the upper bound, consider a case like

    6 1 2 1 3 1 4 1 5 1 6

    there are 5 leaves, all at a distance of 2 from each other

    answer here is 1 1

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

      Oh yeah sorry, k isn't the number of pairs. If a vertex has x children that are degree 1 and x>=2, then k+=x-1. We sum over all vertices.

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

    for the upper bound why is possible to give all other edges different values?

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

.

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

I still don't understand what is said on D2A. I have never seen a complicated line like 3rd para in D2A

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

Div2-E was similar in statement like_this Div1-D but not in difficulty.

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

MikeMirzayanov My question A was submitted twice on the Internet, all pretest pass, the submission time of the two before and after are 10 and 11 minutes, but my score is 432, obviously 50 points less, I want to know why? These are my second submissions:633div2Athe first has been skiped

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

    Successful resubmission will make previous submission as "failed submission" which costs you 50 points

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

      Ok i just knew

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

      MikeMirzayanov His two submission only differs by a new line at the end. I think this counts as repeated submission and maybe should be prevented?

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

The most pathetic contest I've ever seen. Now I know why they call you a dick.

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

    Bruh whats so pathetic about logical questions? All of div2 A,B,C had barely any lines of code if you think.

    I generally hate questions that are easier to solve but has heavy implementation like those with too many cases. This contest was honestly pretty amazing

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

Well written brief statements with nice diagrams and interesting problems!

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

The only thing that prevent me for 30 min to output just N in problem A was this 1e18 it's confusing Lol :"

It can be shown that under given constraints this number of ways doesn't exceed 1e18.

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

    problem A kinda remained me of the Apirl's Fools day's problems when I found out the solution is simply output N.....

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

    What is actually told in D2A? I understand nothing.

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

      same here..

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

      Basically it asks you to find the number of ways to fill up the shape the statement defines. For instance, when N = 2, we can only use one vertical diamond and two horizontal diamonds to shape that form, in this case we have 2 ways to do that. For other input N, there are N positions for diamonds to be vertical, but we can observe that if we make one diamond vertical, the rest can only be horizontal, so the answer is just the number of vertical positions which is N.

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

Hi setters,

I would like to be unrated this round for the following reasons. For the question div1 A, the statement was misleading before it was changed without any form of notice. The original statement had Find the smallest number k such that you can make the array nondecreasing after at most k seconds.. This was very misleading since the variable k is also used to denote the number of indices chosen. This statement led me to think that you could only perform k operations at the kth second. I had this version of the question until around 20 minutes left in the contest when I decided to reload the page. I feel like this heavily impacted my rating negatively, so I would like to request to be unrated. Thank you.

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

    Ok Boomer

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

    I can't understand why some stupid announcements about obvious things clearly written in the statement are broadcasted pretty often, but changes in the statements are treated completely silently. I was once a victim of a silently changed faulty statements as well. antontrygubO_o any comment on this?

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

      Now I agree that not to broadcast this was a huge mistake. The statement was corrected at the 3rd minute of the contest, and I couldn't see a way how problem could be understood in a wrong way (all our testers (of the last phase at least) didn't notice anything suspicious). So I decided that the broadcast wasn't necessary.

      Of course, it's better to broadcast if there is even the slightest chance that someone might be affected, I'll do so in the future.

      Sorry to everyone who was affected... But I don't see a way how we can make this unrated to those who were affected, unfortunately. I'll do my best to not let this happen again, huh

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

        Does Codeforces not have the functionality to unrate individuals? Like most people, I joined the contest as soon as it started, and never refreshed the page (what reason would there normally be to do so). I believe changing the problem statement without notice is completely unfair, especially when the statement reuses the same variable for different purposes almost directly after each other.

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

          There is no way we can check if someone was really affected by the issue or just doesn't want rating drop.

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

            You have a point. Please make sure to broadcast changes to the statement in the future, especially when it is changed for clarity. If you cannot unrate this round, I do not believe it is a big deal since rating will correlate to the user's skill in the long run regardless. Anyways, thanks for noting the mistake. I will continue to look forward to future rounds.

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

    you seem pretty smart lad. you will be up in your feet in no time. just look us poor wretched souls having a hard time..ha deary

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

      Thanks man, I'm just extremely disappointed since I had higher expectations than -98, and I believe I could have done way better without the misleading statement :/

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

    Good to know I wasn't the only one. I thought I might have interpreted the question incorrectly initially, didn't realize that the statement was corrected :|

    Doesn't affect me a lot since anyway I didn't solve it. Had a bad day today.

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

very bad problem C.

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

Did antontrygubO_o really think that Div1C was interesting?

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

    Yes. He is one of the strongest pusher of Div1C.

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

McDic Are you trying to achieve komedy?

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

76395656 Can anyone explain for me, why I got WA on pretest 3 :(

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

    Consider this test case

    1
3
1 2 4

    Check whether your solution satisfy the requirement.

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

      The result for this test case is 2 4 1 and it still satisfies the condition

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

        My bad.
        Try

        1
4
1 2 4 5

        Your solution should output 2 4 5 1, which is wrong then.

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

          aaaa, i know where im wrong @@

          My submission:

          cout << arr[mid + 1 + i] << " " << arr[mid - i] << " ";

          And just change possion:

          cout << arr[mid - i] << " " << arr[mid + 1 + i] << " ";

          and it ís accepted.

          Tks you :(

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

One more reason to skip McDic rounds

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

Am I the only one who found div2A more difficult than B and C? I solved B in ~40 mins then stuck in A for the rest of the contest. Finally just guessed the answer and got AC. When I read C at the end, I was able to come with solution in ~20 minutes. Of course time was over. What the hell is wrong with me.

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

    Same , i thought this can't be that hard but i moved on to B and C after doing them , came back to A and then did that. I had more than an hour for D , couldn't come up with a solution though

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

    I am stuck in A as well.

    Finally, I found that the answer is up to the number of the diamonds.

    But when i noticed that the answer does not exceed 1e18 as stated in the problem, i dare not submit it...

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

    I solved D2A like how April Fool problem were solved. Got nothing from statement. Looking for sequence on input output. Finally print n and got pretest passed.

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

Anyone else was confused in problem A because of this statement....? :/

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

    Yea, I saw that and figured the output couldn't be more than 10^9. I went ahead and did B and went back to A and was trying to figure out combinations before realizing that it was just n.

    IMO it was pretty misleading. TBF, the problem was 500 points, indicating an incredibly easy solution.

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

    I was one of the people against this. lol

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

    Maybe lost about 4-5 minutes for this line -_-

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

Thanks for the contest! Some notes:

  1. Maybe we should set a limit on how many times XOR can be used in the problemset? (By the way, Russian statements for B and C probably should call it "XOR" and not bitwise exclusive OR, just for clarity)

  2. Is there any good solution for C except printing the sequence and finding the pattern?

  3. Probably output section in the statement should say what the output format is, not just say "Print the answer" – then we wouldn't need to reread the statement and check the samples for that.

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

    Can you tell the pattern? I couldn't able to figure it out.

    → Reply