Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Lemonade255's blog

By Lemonade255, 13 months 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 50010001500175025002500.

UPD2 : Editorial

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

UPD4 : Congratulations to the winners!

Div.1 (Out of competition)

  1. Proszek_na_ludka
  2. Egor
  3. jiangly
  4. Geothermal
  5. dlalswp25
  6. antontrygubO_o
  7. I_Remember_Olya_ashmelev
  8. Maksim1744
  9. Heltion
  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

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

adedalic coordinating round will be great!

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

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

Finally kdjonty31 become tester. congrats ! :3 link

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

Love it. I keep my fingers crossed for you.

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

»
13 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Hopefully, the problems are as balanced as the color of testers.

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

will be great round definitely :D

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

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

Hope for strong pretests and not shitty problems from Lemonade255!

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

    Hard to hope for the latter

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

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Underrated comment.

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

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    Emphasize on "good strategy" part please

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

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

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

Augustforces

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

I thought the next competition was in three days, but suddenly there was a competition tomorrow.I'm looking forward to it!

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

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

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

    As a master, give me contribution, please.

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

      I gave you contribution.

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

        As a master,saying something is better than contributing something.

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

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

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

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

»
13 months ago, # |
Rev. 7   Vote: I like it -30 Vote: I do not like it

is it rated?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    ???

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

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

This round is gonna be an amazing

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

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

    I can relate xD

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

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

      I hope You’ll reach blue after This round

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

      Are you a digon?

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

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

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

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

          But can monogon be also belong to polygon? :P

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

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

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

    This same thing happened to me also

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

    I can relate bro, I was closer than you xD

»
13 months ago, # |
Rev. 6   Vote: I like it +30 Vote: I do not like it

Hope for strong pretests.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +287 Vote: I do not like it

    protests are really strong these days

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      what is this meme ?

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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

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

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

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

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

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

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

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

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

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

    I wish I could say "relationship"

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

![ ](codeForcesBabyMeme.png)

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

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

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

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

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

»
13 months ago, # |
  Vote: I like it -6 Vote: I do not like it

hey bro nice nick

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

»
13 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Good luck everyone ;-)

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

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

P.S No offense intended though

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

All hail to you brother! Keep rocking! kdjonty31

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

[..]

»
13 months ago, # |
  Vote: I like it -31 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it -89 Vote: I do not like it

Seeing the handle name anus, I first thought it's an Indian round! The name anus sounds like Indian though!

»
13 months ago, # |
  Vote: I like it -70 Vote: I do not like it

Not as a tester, give me contribution

»
13 months 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.....???

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

»
13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Just asking, Why do you want to remove these?

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

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

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

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

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

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

Donald Trump.

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

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

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

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

    I feel most of the downvotes are from newbies and pupils

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

      I also guess so , bcuz Good coders always enjoy everything ... They are cool people

»
13 months ago, # |
Rev. 7   Vote: I like it -30 Vote: I do not like it

.

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

»
13 months ago, # |
  Vote: I like it -31 Vote: I do not like it

WOW! E=F, WILL TRY BOTH!

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

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

Yeah!

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

speedforces

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

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

Very nice set of questions. :-)

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

This is how you make a round.

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

One of the most stable and decent question sets.

»
13 months 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) @@

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

Problems are good but somehow I choked so hard on B

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

    even i felt C was easier than B

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

      I made B & C, but couldn't do A. laughing after looking A's solution

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

    At least you're not choke hard on "D" *IYKWIM

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

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

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

    What do you mean?

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It's most possible boring math problems.

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

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

        D was greedy and not re-rooting.

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

          • »
            »
            »
            »
            »
            »
            13 months 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]);
            }
            
            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Ah yes of course.

              #Always_ready_to_overkill

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

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

      you come back please !!

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

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

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

Imo C was easier than both A & B.

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

    can you give a hint ?

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

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

      Make a copy of the given array and sort it. Iterate from 0 to n-1 and check if a[i] != b[i], if it is different and a[i] % minValue != 0 then there is no solution.

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

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

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

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

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

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

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

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

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

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

Can D be solved by the greedy method?

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

    Yes

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

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

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

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

    I am also interested to know.

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

    Thanks, so it must be some silly mistake

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

    hint —

    DFS + SORT

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

      • »
        »
        »
        »
        13 months 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 Jastin

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          My feelings are already dead . Just see my contribution . Any way i found the solution and it's same as yours .Thanks for helping me to verify .

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

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

How to solve D :(

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

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

    Same here :(

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

    Holy shit, I'm dumb af

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

      LOL so glad to know I'm not alone

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

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

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

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

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

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

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

»
13 months ago, # |
  Vote: I like it -54 Vote: I do not like it

Video Tutorial for D. Maximum Distributed Tree

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

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

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

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

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

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

Great contest...

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

A round with two data-structure problems!!

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

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

Explain solution for d please?

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

F — press segment tree to win

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

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

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

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

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

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

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

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

What was the logic behind C

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The numbers which are misplaced must have their common gcd equal to the smallest element in the array. Edit: Just have to check that all misplaced numbers are divisible by the smallest number or not.

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

    Consider the sorted list. Compare to actual list. In the places which differ, check if modulo min of the list.

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

    you can always sort the array as long as all elements which you want to move is multiple of min element of array. because if that's not the case, gcd(element,min element)!=min element. so you can't change its position.

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

      Shit!!!Got where my logic was wrong.Btw Thnax!!

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

Could E be solved using a linesweep and avl tree?

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

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

lol!

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

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

    Consider the sorted list. Compare to actual list. In the places which differ, check if modulo min of the list.

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

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

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

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

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

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    13 months 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$$$

    • »
      »
      »
      13 months 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!

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

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

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

For C,

I made a vector of elements which had gcd(minOfArray, element) = minOfArray. sorted them and then placed them again in the array in the places where the above condition holds in increasing order. Then checked if array is sorted.

Can't understand the fault in the logic!!

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • 4 2 6 7 8 5-
    • so your vector is {4,2,6,8}
    • sort : {2,4,6,8}
    • place : 2 4 6 7 8 5
    • is this what you did ?
    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yah EDIT: Actually logic is correct, I declared the minElement globally. I was doing it for the first case. Forgot to shift it inside the loop.

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

Like if you sorted after taking mod

  • »
    »
    13 months 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
»
13 months 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.com/contest/1401/submission/90611250

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

Can anyone tell who user SorryNotSorry (who got the first rank) might be by his coding style?

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

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I am beginner here on codeforces can anybody tell me if my submission will be counted, I submitted my file at the last moment and it ran on the pretests and showed 'pretests passed' after which the time ended, will my code be further evaluated so as to get accepted?

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

have you left a question because you just don't want to type that?

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

Without Reverse and Swap last problem is easy to solve)

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

Thanks for the good samples in F though

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

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

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

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

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

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

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

  • »
    »
    13 months 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!!

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

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

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

    even I did the same :(

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

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

    Try the test case consisting of 3 elements, 16 2 8. Your code will fail. Correct answer is "YES". __

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

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

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

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

Great contest :) No shitty stories

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

what a contest!!

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

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

    If we have the array = [2,8,4]. Your gcd array will be [8,4] and its gcd is 4 which isn't equal to 2. But still, the array can be arranged in non-descending order.

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

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

Query Party!

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

Stuck in Problem A. Orz

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

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

  • »
    »
    13 months 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 - Prime Swaps

    2) 1365B - Trouble Sort

    3) 1148C - Crazy Diamond

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

  • »
    »
    13 months 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]

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

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

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

»
13 months 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. :(

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

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

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

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

      int is already defined long long in macros :)

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

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

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

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

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

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

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

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

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

    Yeah and they are the people who will fail when time comes due to lack of courage. I have many a times solved first problem in > 1 hour and then B,C,D in < 1 hours . If you really love CP you won't see al these things.

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

solved C but got stuck at B :(

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

Any small hints for problem E?

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

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

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

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

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

        you can swap if two elements if their gcd is equal to min element.

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

»
13 months 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 " ?

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

    By the way, the other problems are good. Thanks for your contest.

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

Thank you very much for uploading editorial this fast!!

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

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

»
13 months 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(

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

»
13 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Hello I've passed pretest 1 of first problem of this round, but failed on pretest 2. May I know where was I wrong? ~~~~~

include<bits/stdc++.h>

using namespace std;

int main(){ int no_of_times; cin>>no_of_times;
for(int l = 0;l < no_of_times;l++){ int n,k; cin>>n>>k; if(n == 1 && k == 1){ cout<<1<<"\n"; } else if(n == 1 && n > k){ cout<<1<<"\n"; } else if(n > k){ if(n%2 == 0 && k%2 == 0){ cout<<0<<"\n"; } else if(n%2 == 0 || k%2 == 0){ cout<<1<<"\n"; } else{ cout<<0<<"\n"; } } else{ cout<<(k-n)<<"\n"; } } } ~~~~~

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

What becomes problem C if instead of having the rule "you can swap elements if their gcd is equal to the minimum element of the array" you have "you can swap elements if their gcd is equal to x" where x can be any number (in particular x may not be in the array) ?

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

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

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

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

Amazing Problem statements. Loved problem A very much. Fantastic round!!! Kudos to authors and Mike for fantastic round.

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

It was unrated for me — rating change 0. lol

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C has nothing to do with the greatest common divisor. We only need to consider whether each number not in the correct position can be divided by the smallest number in the sequence.

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

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for problem A

2∗x=a+k

For what minimum value of a , x<a ? k is constant (can be either even or odd). x , a , k >= 0

does the above equation has any mathematical formula?

my code

»
13 months ago, # |