McDic's blog

Codeforces Round #633
By McDic, history, 5 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.net/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

Comments Comments (382)
| Write comment?
»
5 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
»
5 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
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Is It Rated?

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

Are McDic and dick related?

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

YES

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

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

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

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

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

Looking forward to McDic x Twice round!

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

This Problem is too (censored) xD.

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

Everyone, Look out for the unusual start time

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

antontrygubO_o X McDic

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

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

.

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

Hope pretests are strong !!

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

..

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

mcdicorz

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

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

"(censored)"

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

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

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

    no

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

    Yes

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

Loved the rejection comments part

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

Hope that codeforces won't shut down tomorrow :)

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

waiting for formula and theorem forces...

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

Is iterated?

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

fan ei ae yo

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

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

tourist doesn't register the contest yet ?

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

Will there be contest today considering the server problem?

→ Reply
»
5 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
»
5 years ago, # |
← Rev. 9   Vote: I like it -141 Vote: I do not like it

233E - Doe Graphs

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

juicy round :)))

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

    OMG.

    Can you predict Div1C and Div1D of the next round? It would be very useful to me :D

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

      I will predict for you but first show me da money.

      → Reply
»
5 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
»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces

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

Please stop creating problems.

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

Statements are short, but damn are my ideas wrong.

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

ridin ba in contestaye shokhmitoon

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

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

When the first place becomes two

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

    Can you explain why? I think both were fine.

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

Wtf was pretest 3 of C?

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

gg

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

Tourist is back to the top.

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

how to do Div2.C/Div1.E?

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

    exchange 1 with 2.

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

      What's the pattern? jef

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

How to solve Div2 B and C?

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

      Could you elucidate Div2 C, please?

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

        See Here . I hope it helps

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

endless XOR……

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

How to solve div2 D?

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

Video tutorial for div2C/div1A

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

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

is DIV 2 B tough or what??

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

    How to solve? Was the answer just n?

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

      Yes

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

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

    → Reply
    • »
      »
      »
      5 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
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +14 Vote: I do not like it

        31 - __builtin_clz(x)

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

          __lg(x)

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

    language precision problem —

    4.0000000 can be 3.999999999

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

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

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

        All LGM testers failed to figure this for a hour.

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

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

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

.

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

XorForces

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

    Can you explain it?

    → Reply
    • »
      »
      »
      5 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
»
5 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
»
5 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
  • »
    »
    5 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
    • »
      »
      »
      5 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
      • »
        »
        »
        »
        5 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
        • »
          »
          »
          »
          »
          5 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
  • »
    »
    5 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
    • »
      »
      »
      5 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
  • »
    »
    5 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
»
5 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

.

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

      Ok i just knew

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

Well written brief statements with nice diagrams and interesting problems!

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

    What is actually told in D2A? I understand nothing.

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

    Ok Boomer

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

very bad problem C.

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

Did antontrygubO_o really think that Div1C was interesting?

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

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

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

McDic Are you trying to achieve komedy?

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

One more reason to skip McDic rounds

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

Div1

C: godforsaken pattern searching, dumb luck

D: provide some trivial constructs on 4d space to analyze

this is what happens when yo make a div2 round a div1 one

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

I think I don't need the examples and descriptions of problems!

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

Solving div1B (minimizing part) was extremely discouraging for me.

I got to the claim that the answer couldn't exceed 3. I spent 20 minutes proving this, and in the end, I was very proud of the proof I got.

After getting AC, I see that it 800 contestants had solved it. I got really disappointed, because I knew like 99% of them didn't prove anything. They just came up with the claim, prayed a hail mary, and submitted. This was very depressing because I really felt I performed well in that problem, but I was beaten by hundreds out of mere luck.

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

    agree. the proof part is much harder (and more interesting) than the guessing part. However, proof part worth 0 points :(

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

      If the problem had involved reconstructing the answer, I bet you anything the AC's would be half what they actually were.

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

        yeah, this modification would make this task better. Though i don't know if it is doable for maximum case, as my construction is using some really big integers(like $$$2^{K}-1$$$ where $$$K$$$ is a large integer). but the construction of minimum case is really cool imo.

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

        Why is this downvoted? I am in Div 2 and I spent one hour trying to find construction for the minimum case, tried sorting by preorder and looking for something, tried assigning 1 to everything and then "fixing" by changing leaf edges.

        I could have just assumed something labeling with 1, 2, 3 will work and got AC. Can someone share core ideas of proof? I couldn't do it.

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

          Pick a leaf as the root, DFS, keep the root-to-current-node prefix xor, try to keep it non-zero before you reach the leaf. When traversing through an edge, pick any number different from your current prefix xor so the new prefix xor is still non-zero. When you reach leaf, pick the number equivalent to your prefix xor.

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

        Why would you come to that conclusion? You came up with the construction yourself, and probably half of the Div1 folks who solved B are rated higher than you.

        I'm not saying rating is absolutely indicative of strength, but why are you underestimating everyone else?

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

          My point is not related to skill. I was pretty sure the claim was correct the second it came to mind, out of "intuition". But I didn't submit because I don't like to send something I'm not sure about. Others (maybe more skilled than me) just didn't care, and went for proof by AC.

          And you're right, reconstruction was not impossible and most people might have come up with it eventually, but they would've taken longer. Instead I just got more penalty than them for trying to be thorough.

          Notice I'm not complaining. "I got really disappointed" were my exact words. I wanted to express my experience and see if anyone else felt the same way.

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

      Come on, it's not so hard to prove compared to guessing. 3 seems so random to me, I would never be able to "guess" it just because it was in the samples or something. IMO you need some insight to the problem to understand where the 3 would come from. And the construction that always gets 3 is not that far from there anymore.

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

    I am quite sure your claim with 99% is way off. I actually think it would be hard to get enough understanding of this problem to get it accepted but not being able to prove that answer does not exceed 3. But maybe I am missing something.

    EDIT: Ah, ok. Distinguishing the case with f=1 is pretty obvious and if you keep your finger crossed that f is never two and doesn't exceed 3 you are good to go.

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

      let the value of leaf be 0, and do black and while colorings for remaining vertices. (black=1, white=2). value for edges are the xor of corresponding vertices.

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

      I agree. If anything I think finding the maximum is a bit more susceptible to proof by AC, but I don't think it's easy to guess that the minimum doesn't exceed 3 without more or less having an idea of how it should be done.

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

        The proof consists of 3 steps

        1. Observe the cases that 1 is not enough

        2. Observe that 2 is also not enough for the case

        3. Show that 3 is enough for this case

        The third step is not that trivial, but it seems very likely that it's correct after you get 1 and 2. It's easy to prove, but it's even easier to guess without proving.

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

          Why would you just guess "oh answer is not 1 or 2 so it must be 3"? It seems like total nonsense to me unless you have some sort of idea of how 3 can be achieved.

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

            I have a and b, I notice that I might need a^b sometimes, I don't know if there's any corner cases which might cause some problems, but it's not unreasonable to guess that "it just works"

            Edit: To clarify, I proved it. But before I proved it I already expected it to be correct.

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

              Well, imo if you're already thinking that you should use a, b, a^b as weights you're not unreasonably far from a proof, but sure, if you disagree I see how this problem can feel "guessy".

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

                The problem itself is interesting so I don't think being a little guessy makes the problem bad. I'm just saying this guy's point is not unreasonable, especially when speed matters a lot.

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

    Still I'm happy with the fact that I proved it.

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

    I thought about this for past several days. I am sorry about this.

    I will force participants to make certain constructions in this kind of problems next time, so I can give much more advantages to who prove this.

    Thank you.

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

      I want to highlight that the problems were interesting and the contest was very nice. And I always appreciate the hard work problem setters do voluntarily for the community. My comment had the sole intention of sharing what I felt while participating. So absolutely no need to apologize.

      I'm very impressed that even having done such a good round, you still take the time to think about how to improve even more. You're a clear example of what a great problem setter should be like.

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

Did everyone understood Div2A? I just made a guess of printing the input itself after trying to understand the question for more than 1 hr and was shocked too see it passed the pretests.

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

    From what i got , a normal diamond(no rotation)can be fixed in n positions and if we fix that diamond , we are forced to use others , we can't vary any other positions. So a filling can have only 1 normal diamond . We can vary its position , from first to last giving us n

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

Am I the only one who solved Div2C using Binary search? After reading other solutions,mine seems like an overkill.

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

Div2A — There will always be exactly one vertical diamond. Therefore the answer is just n.

Div2B — Sort the array. Then the answer is a[1], a[n], a[2], a[n-1], a[3], a[n-2], and so on reversed.

Div2C/Div1A — Using our moves, let's change every number from a[x] to max(a[1], a[2], ... a[x]). The answer is then equal to the highest bit that is found in any of max(a[1], a[2], ... a[x]) — a[x].

Div2D/Div1B — If the parity of the depth of all leaves are equal, then the smallest value of f is 1; otherwise it is 3. To compute the maximum, observe that if two leaves have the same parent, the the values written on the edges associated with these two leaves must be equal. All other edges can have different values.

Div2E/Div1C — Write a brute-force solution which prints answers in base 4, and look for a pattern after grouping the output into triples.

I do not know yet how to solve Div1D and Div1E.

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

    Can you please explain If the parity of the depth of all leaves are equal, then the smallest value of f is 1; otherwise it is 3

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

      Well if there exists a path from one leaf to another leaf having odd length, the answer is 3 else it is 1.

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

        How did you come up with this?

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

          XOR-ing the same value an even number of times gives 0, so if there are only even length paths, you can give all edges the same weight and you are done.

          For an odd path, for example of length 5 $$$a \oplus b \oplus c \oplus d \oplus e$$$, obviously a single value $$$x$$$ is not enough (because the xor sum will be $$$x \neq 0$$$). If you try to do it with 2 values, you'll split the odd length into an even length and an odd length (for example, you assign $$$a = b = c = x$$$ and $$$d = e = y$$$) and, as previously noted, add odd path cannot be done with a single value. Therefore, 2 is not possible either.

          It is always possible with 3, by picking all but 2 values to be the same, for example $$$a = b = c = x$$$, then $$$d = y \neq x$$$, and finally $$$e = x \oplus y$$$.

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

        there are many leafs how do i find distance between each pair or is there any smarter way?

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

          That was a tricky part!

          That's why the above guy talks about parity, the thing is that you needn't find distance between every pairs, but only from one leaf to all others, if this leaf has even distances from all other leaves, all pairs would have even distances (this is easy to see why).

          Moreover, for the max part, if two leaves are at a distance of 2, then they would have same parent(a leaf has only one parent :). So you find out parents for all leaves and simply sort them and voila!

          Hope it helps :)

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

            ok, for the first part. just asking, did you figure it(even distance part) out during the contest or did you know that thing before the contest?

            Sorry, I didn't get the sorting part. Why do we sort them? and you asked for finding the parent of all leaves(only leaves not other nodes) right?

            Suppose, in my dfs function, I choose a leaf node as the parent node, then do i need to take it's parent too? I don't think so. What do you say?

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

              Yeah, I did figure it out during the contest itself, that was simple because I couldn't do B and misunderstood C as well so all my time went on D :D.

              You only want to know how many leaves have same parents. That is easiest to do in $$$O(n log n)$$$ by sorting and then comparing successive values.[We don't want $$$O(n^2)$$$ :]

              A leaf can't be a parent of another leaf simply because n is atleast 3.

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

                The last part that I was asking that I'm calling my dfs function with dfs(1) (I'm assuming 1 as the root of the tree) but this 1 can be a leaf node.

                For eg — 1 2 2 3 3 4 2 5 5 6

                So, I'm calling dfs as dfs(1)(considering 1 as the root of the tree), but 1 is leaf so technically 2 becomes the child(although not a leaf) but in doing this way I miss 1 as being a leaf. So, should I also take care of this thing too(that dfs for that node should be called which is not a leaf)?

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

                  A leaf is only adjacent to one vertex so that must be the parent, so you don't need to do a dfs :)

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

    Can you please explain Div 2 C in detail? Thank you.

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

      Just keep the track of maximum element traversing array from start,If the current element is smaller then the maximum than compute the power of 2 greater than or equal to the difference and keep track of such powers and output the maximum power among them. For reference- https://codeforces.net/contest/1339/submission/76379511

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

        what will be the answer to the test case: 8 7 8 7

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

          |8-7| = 1 (7 needs 1 to satisfy a1<=a2)

          |8-8| = 0 (8 needs 0 since a2 will be 8)

          |7-8| = 1 (7 needs 1 to satisfy a3<=a4)

          max = 1 (taking max because ques asked for minimum time required)

          log2(1) = 0 + 1 (+1 since 2^(x-1) where x>=1)

          ans = 1 seconds

          If max is odd, just use ceil(log2(max)) (seconds can't be in floating points)

          if max is even, use log2(max)+1 (since 2^(x-1))

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

          could be 8 8 8 8 thus on 1st second

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

    in Div2D can you explain why for maximum we give all other edges can have different values?

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

      There are infinitely many possible weights I can put on. Suppose, there is a leaf to leaf path where I have already put weights like... 2-3-5-1-x-6, now, you need to fix a value for x. to make 2^3^5^1^x^6 = 0, x should be 2^3^5^1^6^0 = 3. Now you see, I have already used 3, so what...now I decide that I'm not gonna use 3 there and change the value to maybe 10...which has not been used yet. So, now x shall be 2^10^5^1^6^0... I'm gonna use such a number for which I get a completely different value of x. This is possible as we can infinitely many options of weight.

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

        I got it thanks bro so much

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

        ok seems fine. what if some 2 leafs have distance = 2. Then we'll have to use the same edge weight.

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

    Shouldn't the answer for B be the reversed order?

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

      No. Try this case. 1 2 3 4 4 5 your answer --> 5 4 4 3 2 1--> difference= 1 0 1 1 1(Does not follow the condition)

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

        No you misunderstood my idea. My answer would be 3 4 2 4 1 5.

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

      Sorry, it has been fixed.

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

    any reason that the edges associated with the 2 leaves must be equal?

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

Another round with zero solution-hacks! Missing those golden days when hacks used to be a key point in getting a good rank. Hoping for a round full of hacks in near future.:p

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

    I hope it wont happens but having no solution-hacks is not acceptable.

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

Hi,

In the original problem statement for A, there were two ks: the first one for the size of the set you choose, and the second one for the number of seconds you used. These two k's were the same (both lowercase) and nothing differentiated them. As a result of this issue, I was unable to solve A until they fixed the problem statement later in the contest (changed one k to T) and ended up with a lot of extra penalty due to this. There was also no announcement stating that this was changed. Would it be possible to unrate me?

I'd also like to point out that I solved C before A, which should serve as some sort of evidence that I was affected by the statement :(

Thanks!

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

Thank you McDic and antontrygubO_o for making problems in such a way that minimizes checking time and making such nice problems for D2A-D2B-D2C, sadly D2E wasn't as good as expected, the problem was fine but not the gap, hope you will decrease thinkforces for your next rounds.

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

nice contest

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

Good round, great problems! But weak pretests on D. Test 31 is very short, but wasn't used in pretests...

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

When I solve B and C but unable to solve A
download

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

McDic tzuyu_chou Is it allowed?

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

QUick Check tourist is gonna take the throne again.

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

tourist is back to 1 .woah.

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

For good or for worse the contest (at least div 2) is an implementation-light, mathy contest. I personally enjoyed it. Others may not have. But it's hard to deny that McDic, in his contest style and his detailed editorial, showed the spirit of a person who is truly passionate about the art of problem setting.

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

Am i the only one who misunderstood the statement of problem C? The whole contest I believed that the indices should be consecutive xDDD.

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

    I made like 4 wrong submissions before i realised lol

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

    no you aren't the only one and it got me wrong on pretest 3(wasted almost one hour and 35 minutes on the same problem). The statement was very confusing and it's written in such a way that it leads people to believe that the indices are consecutive. If the statement was clear , I would have definitely tried maximum gap of power of two :-(

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

    Oh My God. I was trying for the past 2 hours , wasted an hour in the contest, read the editorial.Then randomly started viewing the comments and now I realized that. Thanks Man!

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

This guy register another account for him to hack, check this out 76401969 and 76394268. That's not nice!

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

it was a second round with problem A harder then B+C for me... it isn't good(

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

****great contest i hope if every contest have this style****

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

Good statements, no bullshit

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

76379586 what is wrong with this? I lost so many points because i did not solve problem B and i don't know why...

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

I started with div2 C & got confused on statement because of k which is later changed with T. I lost 1 hour because of it and also got two wrong answer. Later I solved it in 19 minutes. That was a bad contest for me. I got so unlucky today. Hopefully i'll do better in future. BTW, great problems.

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

    Everybody got confused I guess including me

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

      Yeah, I didn’t even reload. But they are human too. They did great. It’s common to have some issues. They will do better for sure.

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

I have been wrongly accused of submission of similar code for Problem D.

Your solution 76385031 for the problem 1339D significantly coincides with solutions Kimur/76379805, overstart/76379879, Gaas/76379895, ChudiChudiTeriMaaChudi/76379984, abc090/76380479, genndq/76380572, tecca/76380750, c0d3mu/76380908, darshan___/76381314, bokunopico/76381382, driver425/76381996, Sardar_Ji/76382048, use_me/76382134, rustic_coder/76383553, teri_maa_ka1/76384665, amishbharti1999/76385031, robinsharma1599/76388701, xDxD/76388978, rmodi9942/76392243, asdfghjk123456/76395936, akshay_kumar646/76397440, sir_dawnblade/76398130, ppulkit2707/76399332, ashtechinc/76401095, ankush_3107/76401176, anupamsri/76402758 **** I don't code on any online compiler with public access. So I don't understand the Coincidence of any similarity with such a large no. of people. Admin please see to it since all my submissions for the contest has been skipped.

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

    Did you take a look at the submissions by the users you mentioned? Do you find any similarities?

    And also, I see that some of those submissions listed were made before 76385031.

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
Help Noob please !!!
why in problem C
this testcase give ans 31

1
3
1000000000 0 -1000000000

system ans is 31 
but i guess to satisfy index 2,3 we need 2^31 
so my ans is 32 .. 
have i read the question wrong !
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2^30 = 1073741824 which is bigger than 1000000000 . so should be enough

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

      sorry corrected the testcase ..plz tell now

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

        2^0 + 2^1 + .. . 2^30 = 2^31 -1 which is bigger than 2*10^9

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

          in 30 seconds we increase by 2^31 — 1

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

[deleted] Wrong blog

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

HELP!

Hi, everyone! My friends has some trouble in his solutions, He has submitted this solution 76367506 during the round, However, after the system pending test, He did not get an AC, but still the Pretest passed. The score for this problem was not added to my friends. He has submitted totally the same code just now, 76438866, and get an AC. Why did this happen? It has effected on my friends ratings, Where can I find the administor to solve the trouble? (sorry for my poor english)

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

nice!

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

I solved B C but didn't get the meaning of A TAT, by the statics I know outputing the input directly...Could anyone explain it? Thanks!

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

When I click on the handle of sorry_dreamLolita from this blog's top rankers, why does it redirect to dreamLolita ? I'm not getting it.

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

One of the Best Contest I've ever had. :)

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

I see many people aren't satisfied with the pattern finding solutions of Div2D/Div1B and Div2E/Div1C. Here are some ideas:

Div2D/Div1B:

Let's give each vertex $$$u$$$ a value $$$f(u)$$$, having the property that weight of edge $$$u-v$$$ is equal to $$$f(u) \oplus f(v) $$$. Observe that fixing the values of $$$f$$$ for all vertices gives unique values of edge weights and for each way of fixing edge weights, we have some corresponding values of $$$f$$$ (Infact fixing all edge weights and $$$f(u)$$$ for a single vertex produces a unique graph).

This trick of converting edge weights to vertex weights and vice versa is quite useful in lot of tree problems.

Now, observe that $$$\text{xor}$$$ along all edges of any path from $$$u$$$ to $$$v$$$ is equal to $$$f(u) \oplus f(v)$$$. Thus, if we want $$$\text{xor}$$$ along path between any $$$2$$$ leaves to be $$$0$$$, then values of $$$f$$$ for all leaves must be same, let's set them equal to $$$0$$$. Now, we can give any value for all non-leaf vertices, so long as no $$$2$$$ adjacent vertices have the same value (as edge weight cannot be zero).

Now, it's not that hard to see that if we assign, say the value $$$2^i$$$ to the $$$i$$$th non-leaf vertex, then all edges between non-leaf vertices will be distinct. So, this way we can calculate answer for the max case. For the min case, we "color" the non-leaf vertex with $$$2$$$ colors. If only one of these colors is ever adjacent to a leaf, we can let the other color be equal to the color of the leaf vertex, thus, all edges will be of the same weight. Otherwise, all $$$3$$$ colors come in contact with each other, so we have to use $$$3$$$ different edge weights for each pair of colors.

Edit: Deleted Div2E/Div1C explanation because it eas wrong.

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

As I described in update 4, check some of excluded problems at here!! Thank you!

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

Can anyone please help me figure out why my Python solution of Div 2 D gets a runtime error on test 6? I've even tried generating random trees and running my program on them and never got a runtime error. Been trying to fix it for the whole day :( You can look at submission 76578084, for example. I've determined that the error happens somewhere in min_f method, but haven't figured out where.

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

    The problem was I was using a recursive algorithm to find all distances from root to leaves, and python cannot into many recursion layers. Rewrote it to use a while loop with a stack, and now it works.

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

Is it just me or this submission https://codeforces.net/contest/1339/submission/76360407 shows pretest passed as verdict?

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

Can we expand the 1D to the ordinary undirected graph？

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

    Wow, I didn't seriously tried, but sounds hard problem.

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

Is this handle tzuyu_chou and this are/is the same people?

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

can anyone explain how does this test case problem Div1 A : n=5 array={5 -10 2 -9 -5} give 4 and not 5. I think i didnt understood question properly if its 4. Plz help

→ Reply