blobugh's blog

Codeforces Round #665 (Div. 2)
By blobugh, 4 years ago, In English

Hello Codeforces!

I'm glad to invite you to participate in Codeforces Round 665 (Div. 2) taking place on Aug/21/2020 17:35 (Moscow time). The round is rated for users whose rating is lower than 2100.

All problems were mainly created and prepared by me, and I'd also like to thank:

You will be given 6 problems and 2 hours to solve them. The score distribution will be announced closer to the start of the round.

Good luck, and have fun!

UPD1 : Score distribution is 500 — 1000 — 1500 — 1750 — 2500 — 2500.

UPD2 : Editorial

UPD3 : System testing has finished. We hope you enjoyed the contest :)

UPD4 : Congratulations to the winners!

Div.1 (Out of competition)

  1. tribute_to_Ukraine_2022
  2. Egor
  3. jiangly
  4. Geothermal
  5. dlalswp25
  6. antontrygubO_o
  7. ashmelev
  8. Maksim1744
  9. Sugar_fan
  10. SSRS_

Div.2

  1. gamegamewillwinioi2021
  2. altair-chan
  3. Isouau
  4. rainboy
  5. kissenok
  6. Noche_5
  7. ghj1222
  8. nitinjan06
  9. Rchen3
  10. Gotz_X
  • Vote: I like it
  • +717
  • Vote: I do not like it

Comments Comments (269)
| Write comment?
»
4 years ago, # |
  Vote: I like it +96 Vote: I do not like it

adedalic coordinating round will be great!

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

35 hours before the contest and this still isn't on the home page. Hmmm...

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

Finally kdjonty31 become tester. congrats ! :3 link

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

Love it. I keep my fingers crossed for you.

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

6 tasks for 2 hours and testers from different departments |=> well-prepared competition.

Thank you to everyone who took part in its preparation!

Successful writing!

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

As a Tester, I would like to say that the problems are really interesting, also the statements are short too. Please upvote me now! :)

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

Hope for strong pretests and not shitty problems from blobugh!

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

    Hard to hope for the latter

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

      I cracked so hard and wanted to upvote your comment. But me being a man of culture did not want to destroy the auspicious number of upvotes on your comment :)

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

        it went a little above. Had to downvote it. Sacrifices have to be made for greatness

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

<Mandatory tester comment./>
SAVE-20200820-115655

Also, the problemset's really nice and concise.

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

As a tester I would say that a good strategy will lead to positive rating.

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

    i think he meant to say A and B are tricky so try out with C and D.

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

August:

In India — the month of holidays

In codeforces — the month of contests

We already have six contests and three more to go.

Thanks Mike and codeforces.

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

Augustforces

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

.

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

As a master, I hope you good luck and high rating!

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

    As a master, give me contribution, please.

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

WEll, How many contest holds in every month, at least ??

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

As a tester i advice you to read all problems :)

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

is it rated?

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

    ???

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

      The round is rated for users whose rating is lower than 2100.

      Can you read the announcement ?

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

This round is gonna be an amazing

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

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

    I can relate xD

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

    I can feel you bro, you can check my profile I've reached 1590+ many times but never crossed 1600, 1600+ rating is still a dream for me

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

      I hope You’ll reach blue after This round

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

      Are you a digon?

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

        Oh boy! so we have a monogon here too it seems

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

        Where do you learn these weird polygons ? I never came across these in my school/college.

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

          But can monogon be also belong to polygon? :P

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

      You are at 1599 right now, coincidentally, your profile picture also has a point on the border of the circle.

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

      I'm in dilemma whether to wish you luck or not. If you cross 1600, your graph will lose the charm.

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

    This same thing happened to me also

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

    I can relate bro, I was closer than you xD

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

Hope for strong pretests.

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

    protests are really strong these days

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

      what is this meme ?

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

        It's Pretest, not Protest. — the first comment hoped strong protests.

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

      Русские поймут =)

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

        Понять-то они поймут, но здесь не политический митинг.

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

As a tester, this contest made me lose my will to live.

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

    I hope that doesn't happen to the contestants after the contest..

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

    But it did not kill your craving for contribution.

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

Glad to see specialists are also being accepted as problem setters. :)

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

Can I ask a question? What type of problems are you best at solving?

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

![ ](codeForcesBabyMeme.png)

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

Korean contest! I love it! 반가워요 :)

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

As a tester I recommend you to read all problems and wish you big positive deltas!!!

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

    Thanks, really did helped as I skipped B to solve C first

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

hey bro nice nick

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

Let's hope the problem statements can be as short as this announcement.

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

Am I the only person who finds the username blobugh weird? Its like saying "Hi, I am Anus No. 1373"

P.S No offense intended though

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

All hail to you brother! Keep rocking! kdjonty31

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

[..]

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

wow! there aren't too many testers...

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

Not as a tester, give me contribution

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

I had to post this, for 71 minutes the number of comments hadn't changed, a conspiracy.....???

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

    Haha funi sex number i laughed, came, and had an epileptic seizure upon seeing this post. It is in fact so hilarious that after I showed it to my entire family they nearly died from asphyxiation because they couldn't stop laughing at this quirky post. I am currently at my mother's funeral, and the priest is unable to keep a straight face when he reads about the cause of her death.

    I'm just happy my mom died with a smile on her face :)

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

Just asking, what's the point of the 'x' button if I can't remove them?

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

    Just asking, Why do you want to remove these?

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

      Why not? It's good to have a choice and I'd personally feel better after removing some or all.

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

    You could remove them if you didn't make any submission.

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

I am scared about 5 page long queue . I hope MikeMirzayanov will fix it before the contest .

UPD — It is fixed now !!

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

    Not 5 pages but hundreds of pages .. no submissions are judges for last 4 hours(which i saw ).

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

    Where can you see the queue?

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

As a tester, this contest will be interesting and entertaining. Thanks, Codeforces.

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

.

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

Only two hours left before the contest, score distribution should be published. blobugh

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

wishing all coderforces family luck and fortune . May god bless you all @Erica

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

    I feel most of the downvotes are from newbies and pupils

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

.

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

    This meme isn't new(actually, it's common), so it's likely to get downvoted.

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

WOW! E=F, WILL TRY BOTH!

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

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

speedforces

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

I suppose everyone here wants to learn. So the test cases must help us to think regarding the problem.

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

This is how you make a round.

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

When I'm sure my logic is correct but WA on pretest 2 (x4) @@

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

Problems are good but somehow I choked so hard on B

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

is it educational round or what? why problems havent any idea

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

    What do you mean?

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

      It's most possible boring math problems.

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

      Problem D which decided the rank of majority was standard re-rooting. And I guess problem F was some modification of segtree but I haven't looked very seriously into the problem.

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

        D was greedy and not re-rooting.

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

          Of course it was. But at least in my solution, I used re-rooting to find edge weights.

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

            You could have done it like this-

            if (not visited v)
{
    dfs(v)
    number_of_paths_including_this_edge = size[v] * (n - size[v]);
}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Ah yes of course.

              #Always_ready_to_overkill

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

    +1, I understand that maybe this problems can be Educational for Div2 but they seem uninteresting.. :(

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

      I prefer this problem set. Only one I really thought was too boring was D, but better than having non-diverse round. ABC were even an ur style problems...

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

For me A was nearly as difficult as D

Will have to check the editorial to understand it lol

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

Imo C was easier than both A & B.

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

    can you give a hint ?

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

      Just sort the original array and check to see which ones are out of order, if all the ones out of order are divisible by the minimum element the answer is yes otherwise no.

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

    and I can't solve C, I'm too bad :(

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

After getting 4 WA in D, here are the cases to take care of.

  1. Don't take mod of last greatest values when m > n — 1 and insert in list because mod might make the value smaller. Instead take product of those and add to our answer ASAP.

  2. While computing how many times edge can be part of various paths, don't forget to take it as long long and also list as long long. And don't mod because again value might become smaller.

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

    oh fuck I think I fell victim to both of these... RIP

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

    Oh wow, I think now I know why my solution get WA

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

    Shit..Too bad I couldn't figure out during the contest :(

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

    for point 1, how about sorting p array first, then assigning the values, that way the array is always in sorted order, and no need to care of mod making the value smaller.

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

Can D be solved by the greedy method?

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

    Yes

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

    Yes, I think the author's solution bases on Greedy approach

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

    Yep, greedily assign the maximum weight to the most used edge (found using dp to get size of subtrees)

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

    Thanks, so it must be some silly mistake

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

    hint —

    DFS + SORT

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

      Don't give hint , either tell full solution or don't , we can wait for editorials .What you are telling everyone knows.

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

        My approach —

        find number of times an edge is coming in a path.

        (n1 elements)--(edge)--(n2 elements) => number of times = n1*n2 (I found n1 = number of elements in subtree of n1 and n2= n — n1)

        and then fill max factor in maximum edge.

        my sol — 90611208

        I have used iterative DFS, because I thought I might get TLE.

        Sorry to hurt you feeling bully....maguire

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

Completely exhausted after the contest. I got stuck in the 4th problem. There may be some property that will be used. A lot to learn this from contest. A NICE CONTEST with short problem statements!!

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

How to solve D :(

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

Wasted all the time with problem D pretest 5, finally I found that i am sorting after taking the numbers module mod :(

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

    Same here :(

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

    ‎

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

      LOL so glad to know I'm not alone

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

    I had the same problem too but wasn't able to notice this. I even solved E mentally and would probably have had time to implement it if it weren't for this mistake. :(

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

      I should have quit it too, but it's really hard to leave a problem solved by about 2K users and go to other harder problem :(

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

    I've done this but still got WA5 90613994 :(

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

      z.push_back((n - s[u]) * s[u]);

      Overflow will happen here, as both $$$n$$$ and $$$s$$$ are declared int.

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

    Thanks for this comment, wasn't able to find the bug in my code until i saw this

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

    ahhhh thanks! after 22 times getting WA on test 5 i just saw your comment. god damn it :(

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

Problems, at least problem statements, were too mathy/formal to my taste

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

    It was pure math homework contest. I am surprised as how much people seems to like that kind of problems.

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

      WitchOfTruth and spookywooky if you want to be good at competitive programming , trust me soling math problems will help you a lot .

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

        Math problems per se may not be that bad, but here we had A-B-C three math problems in a row, And then D, which was not math, but the problem statement was so dry and full of formulae that it felt like one.

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

Great contest...

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

A round with two data-structure problems!!

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

    And both of them will most likely have difficulty 2000+. So for most of the real div2 participants there were no ds problems.

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

F — press segment tree to win

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

    But how to do? Lazy-tag can't work!!

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

      Maintain left and right childs and a tag for each level if they have to be swapped. Reverse operation is same as swapping at all levels below current level.

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

      Observation — order of the operations doesn't matter, so just write amount of each operation for each k. So when pushing from vertex, just look at the number of operations for the current level k. Swap is just swapping children, and Reverse can be done lazily.

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

        Alternatively, notice that all operations are xoring the indices and segment tree works really nicely with xor.

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

        Is it obvious?During the contest I doubted whether the order matters .:(

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

What was the logic behind C

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

Today for the first time I had to implement Segment Tree from scratch lol.

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

lol!

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

I'm curious that how one would solve C? if the gcd of two element of array is not needed to be the minimum element of array.

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

    I was stuck with this logic. But say array is 2, 8, 4 and you want to swap (8, 4), you can just swap (2, 4) (8, 2) and (4, 2) again.

    Basically 4, 8, 2 -> 4, 2, 8 -> 2, 4, 8.

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

    if gcd can be anything (i.e. no conditions on gcd) then according to me its always possible to sort the array, just like swapping every possible pair.

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

      so true..then the problem will not even be considered as prob A

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

      no I didn't mean that gcd can be anything it's like that the gcd should belong to the array but it's not need to be the minimum element of the array.

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

    if you have one element whose gcd is always equal to min with others (like — minimum number) and those numbers if gcd != min are in right position than you can always arrange that array.

    ex — 2, 6, 5, 4

    if min = 2, and you want 4 to be in 2nd position, but gcd(6, 4)!=min, then you can

    swap —

    2-6 => 6, 2, 5, 4

    2-4 => 6, 4, 5, 2

    2-6 => 2, 4, 5, 6

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

what's wrong in this? https://codeforces.net/contest/1401/submission/90616241 (problem D)

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

    Test case:

    1
4
1 2
2 3
3 4
5
2 3 5 7 11

    Correct answer: $$$1555$$$

    Your answer: $$$95$$$

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

      Why the answer is 95? we give the following value: 11*7*5 in the edge between 2-3, 3 in the edge between 3-4, 2 in the edge between 1-2; then answer should be 4*(11*7*5) + 3*(3) + 3*(2) = 1555; Correct me where I am wrong!

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

        Yes, the correct answer is 1555, but instead of do 4*11*7*5 i did 4*11+4*7+4*5

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

    you should consider the cases in which m is larger than n-1.

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

Like if you sorted after taking mod

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

    I even didn't do that stil got WA. Please help to debug.

    UPD: No need i got what i did wrong.

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

I kept on getting RTE on test 6 of D. Thanks a lot to python!
https://codeforces.net/contest/1401/submission/90611250

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

GCD is resounding in all directions ——when i solved D but not C and only 30 mins left

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

Solved F first and didn't have enough time to debug E :(

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

solution of C https://codeforces.net/contest/1401/submission/90579190

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

Without Reverse and Swap last problem is easy to solve)

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

Thanks for the good samples in F though

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

Can anybody tell me why my solution for D is failing on pretest 5? It looks like the logic is correct, comparing it to people who got it accepted. Submission link

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

    Alright, so I realised my mistake, one of the arrays I had sorted after taking modulo. I crie. TT

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

What is the correct approach for problem E? I guess there would be some magical trick.

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

Please help!
Can anyone tell me why I'm getting TLE on problem D? I switched to c++ from python recently and I really thought these things won't happen anymore :<<<

I really feel my solution is perfect.
Is it about memory allocations? Should I have created an array for the adjacency list instead of creating a new vector or something?
One of the submissions: 90617571

Main part of the solution
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you should put vvi &adj instead of vvi adj in dfs()

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

      You think that one copy made all the difference? Oh.. As I'm writing this comment, I realize every dfs copies it, because it's recursive :|

      Well it was the first dfs problem I solved since switching to C++. There have to be some bumps in the road I guess.

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

    You need to declare vectors given as parameters as references. Here, you copy the array adj each time dfs is called.

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

For problem D, do we have to greedily arrange the m factors on each edge based on which edge is most visited?

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

    Yes!! But how will we know which edge is visited most? I was stuck in this part only!!

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

      It will be equal to number of times a particular edge xan be used in a path from u to v which will eventually the product of number of elementsin the subtree and other the nodes As that edge will come only if you have a node other than the nodes in the subtree and the other node is in the subtree.

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

What's wrong with my solution for C? 90603416 I created a copy of the given array and sorted it. Next, for each index, if the elements in the original array and the sorted one aren't equal, I checked if their gcd was equal to the minimum element. If it is different, I print "NO", else "YES".

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

    If the arr is 2, 8, 4, then the sorted array is 2, 4, 8. GCD of 4, 8 isn't 2, but it's still possible to fix this. Swap 2 with 4, swap 2 with 8, swap 2 with 4.

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

    You need to check if it is multiple of min element, because that is enough. Every two multiples can be triple-swaped with each other using the smallest element.

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

I felt like a math exam, didn't like this contest at all

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

Amazing round ! Clear statements with no stories, hopefully strong pretests. This has to be one of the least constructive rounds I have seen in recent times on CF :)

EDIT: And fast editorial as well :)

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

Great contest :) No shitty stories

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

In C, i just took all elements which were not in the correct place after sorting in another array arr2, and found the gcd of arr2. whats wrong in this??

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

    First: Find minimum element.

    Second: Find elements that not in their place.

    Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.

    So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"

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

Query Party!

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

Stuck in Problem A. Orz

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

how to solve c????????/ please help

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

    I won't tell you how to solve it directly, but I can give you 3 similar problems to today's C:

    1) 432C - Простые обмены

    2) 1365B - Проблематичная сортировка

    3) 1148C - Crazy Diamond

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

    my solve: we can never move elements, which are not divisible by min_of_array, so we should check if they are in their "sorted" place. Lets call other elements divisible. after that we can always sort the array with this logic: gcd(min_of_array, any divisible) = min_of_array, with that we can swap for ex min_of_array with the last element and then with min_of_array with max, with that iteration we decreased size of our array to sort by one (we sorted biggest divisble in its right place) and can continue with that logic.

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

    First: Find minimum element.

    Second: Find elements that not in their place.

    Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.

    So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"

    By "swap any 2 elements using minimum element as a buffer" I mean this. U have a1 a2 ... aN . A1 is minimum element (aM), GCD(aM,aX) == aM. So, if we want to swap aX and aY. We can do like this:

    [aM,aX,aY]->[aX,aM,aY]->[aX,aY,aM]->[aM,aY,aX]

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

Could anyone help me,why is my solution for D is TLE. I think my answer is perfect. 90615633

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

    pass the "tre" by reference in dfs function.Because in your code the vector is copying itelf everytime dfs is called

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

    Had the exact same problem. Need to pass 'tre' as a reference (or do like all the experiences ones and declare it as a global variable).
    Every time you call 'dfs' you copy the whole vector.

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

This was the first time I solved 2C and still am able to get a +3 according to predictor. :(

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

Can someone please tell me why this is giving RTE. link

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

    In dfs function you are using int val = sub[x] * (n — sub[x]); but you shoud use long long int as it (sub[x] * (n — sub[x])) may exceed the limits of int

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

      int is already defined long long in macros :)

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

        Okay, I didn't see that earlier. But now I have found the mistake. for(int i = n — 1; i >= 0; i--){ cal[i] %= mod; factors[i] %= mod; int temp = (cal[i] * factors[i]); temp %= mod; ret += temp; ret %= mod; }

        In above for loop you should start i with (n-2) not with (n-1)

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

          okay got it...Thanks. But why my code didnt fail on pretest 1?

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

            I am also wondering, why it was not failing on pretest1. But I didn't came up with any answers.

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

Can anyone detect why this code gave WA on pretest 2 in problem D , I am not able to understand the issue in it. 90570026

PS:- Finally done , I was missing case when m>n!

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

Off 5 blue participants in my friendlist 4 did not submit any solution. And the one who did won't be blue next contest.

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

    how to check who took part and didn't submit?

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

      On the contest page you can click the number which shows the participants to get the list of all registered ones. Then there is a friends button.

      Same friends button is in standings table.

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

solved C but got stuck at B :(

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

Any small hints for problem E?

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

problem c: n=5. 8 8 4 4 2 why the sample is correct? (this smaple printed "yes" in some codes)

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

    Because 8, 8, 4, 4 are all divisible by 2 (the minimum), so they can easily be swapped to create a sorted array.

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

    For C , If input is n = 5

    2 12 8 32 24

    min = 2, gcd = 4, My ans : "YES" passed, actual ans should be "NO"

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

      Answer is YES. cause using 2 you can swap any element .you have to find just 2 element gcd not all..

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

Did anybody else feel this contest was so smooth? I mean.. I got my "Wrong answer on pretest 2" the second after I made my submission. Kudos to the platform! Jokes apart, it was nice problem set!! Thanks overall!!

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

SO, what does the "1-s" mean ??? I didn't get it, so I lose Problem D. Can't you just write directly " 1s " or " '1's " ?

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

Thank you very much for uploading editorial this fast!!

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Those who are getting WA in D like me m can be greater then n , it have to be considered! I got WA in 2 facepalm!

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

During the contest, I submitted solution for F, but quickly realized that it works in $$$O(2^n \cdot q)$$$, though it was easy to fix so I resubmitted. But then I submitted initial slow solution after the contest again, and it passed systests! So I quickly hacked it 90619845 But I'm quite disappointed that systest didn't manage to break my initial slow solution(

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

when my rating was increased in last contest they updated it afer 6 hours or more and today my rating was going to decrease they updated it inside one hour
why?

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

My screencast of the round, where I start to give up on templates, horribly screw up D, continue my curse of never full-solving, and explain solutions for A-E

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

I have a new record !!! 2000+,I am waiting for your congratulations!!!!

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

No announcement for any problems in the round is the best evidence to prove an expilcit and clear round.

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

It was unrated for me — rating change 0. lol

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

.

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

    You are saying that it has nothing to do with gcd just because you figured out how to solve it without explicitly finding any gcd?

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

Please help me why this solution get error out of bound at line 59?

Here is my submision 90686316

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

please someone help me. I am getting Runtime error in TC 6 in Q.4("Maximum Distributed Tree"). here is my code in Python 3

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

Anyone with W/A on Problem D, test case 5, don't take mod while calculating the frequency of edges.

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

why the rating changes have changed ??

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

Thanks for the fast editorial. this was my second time to take part in codeforces rounds and I'm very happy that I managed to solve one problem at least.

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

Could someone help me figure out why am I getting Run time Error in 2nd test-case of Problem D. I have found one mistake of taking mod when i multiply the values and then sort, but that doesn't resolve the run time error[submission:90755994]. Thanks in advance!

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

Problem D: Maximum Distributed Tree

Can anyone please explain why my code is giving wrong answer on test 5? Please... Solution

→ Reply