Блог пользователя blobugh

Автор blobugh, 4 года назад, По-английски

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. 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
  • Проголосовать: нравится
  • +717
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

adedalic coordinating round will be great!

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Finally kdjonty31 become tester. congrats ! :3 link

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Love it. I keep my fingers crossed for you.

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

6 заданий на 2 часа и тестеры разных подразделений |=> хорошо подготовленное соревнование.

Спасибо всем, кто принимал участие в его подготовке!

Успешного написания!

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится +127 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +92 Проголосовать: не нравится

Hope for strong pretests and not shitty problems from blobugh!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +76 Проголосовать: не нравится

    Hard to hope for the latter

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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 :)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +182 Проголосовать: не нравится

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

Also, the problemset's really nice and concise.

»
4 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Augustforces

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 7   Проголосовать: нравится -30 Проголосовать: не нравится

is it rated?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

This round is gonna be an amazing

»
4 года назад, # |
  Проголосовать: нравится +184 Проголосовать: не нравится

»
4 года назад, # |
Rev. 6   Проголосовать: нравится +30 Проголосовать: не нравится

Hope for strong pretests.

»
4 года назад, # |
  Проголосовать: нравится +180 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

![ ](codeForcesBabyMeme.png)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -42 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

hey bro nice nick

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All hail to you brother! Keep rocking! kdjonty31

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

[..]

»
4 года назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -70 Проголосовать: не нравится

Not as a tester, give me contribution

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 :)

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

pic
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

UPD — It is fixed now !!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

надеюсь, ник автора контеста и качество задач не связаны

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 6   Проголосовать: нравится -28 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 7   Проголосовать: нравится -30 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

WOW! E=F, WILL TRY BOTH!

»
4 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

speedforces

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

This is how you make a round.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Problems are good but somehow I choked so hard on B

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится

    What do you mean?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      It's most possible boring math problems.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        D was greedy and not re-rooting.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +12 Проголосовать: не нравится

            You could have done it like this-

            if (not visited v)
            {
                dfs(v)
                number_of_paths_including_this_edge = size[v] * (n - size[v]);
            }
            
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -28 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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...

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

For me A was nearly as difficult as D

Will have to check the editorial to understand it lol

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Imo C was easier than both A & B.

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can D be solved by the greedy method?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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!!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve D :(

»
4 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Great contest...

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

A round with two data-structure problems!!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

F — press segment tree to win

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What was the logic behind C

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

lol!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Test case:

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

    Correct answer: $$$1555$$$

    Your answer: $$$95$$$

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Like if you sorted after taking mod

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    UPD: No need i got what i did wrong.

    Spoiler
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Without Reverse and Swap last problem is easy to solve)

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Thanks for the good samples in F though

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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".

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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 :)

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Great contest :) No shitty stories

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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"

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Query Party!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Stuck in Problem A. Orz

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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]

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      int is already defined long long in macros :)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

solved C but got stuck at B :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any small hints for problem E?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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"

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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!!

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 " ?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thank you very much for uploading editorial this fast!!

»
4 года назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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(

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

It was unrated for me — rating change 0. lol

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Here is my submision 90686316

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

why the rating changes have changed ??

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Problem D: Maximum Distributed Tree

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