Ari's blog

Codeforces Round #561 (Div. 2)
By Ari, history, 6 years ago, In English

Hi Codeforces!

We are happy to invite you to take part in Codeforces Round 561 (Div. 2). The contest will be held on May/17/2019 18:05 (Moscow time).

You will be given 6 problems and 2 hours to solve them. The round will be rated for all contestants with rating below 2100. As usual, participants from the first division are welcome to join out of competition.

The problems were written and prepared by Jefe and me. We owe a huge thanks to KAN for coordinating the round, to Lewin and mohammedehab2002 for testing, and of course, to MikeMirzayanov for the great Codeforces and Polygon platforms.

Good luck and have fun!

UPD: A huge thanks to neal, dreamoon_love_AA, and antguz for help with additional testing.

UPD2: Thanks for participating! System tests have finished. Congratulations to our winners!

Div. 2

  1. iristran911

  2. Sigyn

  3. HaylayWilliams

  4. albertg

  5. Tianhen

Div. 1 + Div. 2:

  1. 244mhq

  2. Um_nik

  3. uwi

  4. iristran911

  5. HIR180

Editorial will be available soon.

UPD3: Editorial is up!

  • Vote: I like it
  • +348
  • Vote: I do not like it

Comments Comments (136)
| Write comment?
»
6 years ago, # |
  Vote: I like it +44 Vote: I do not like it

A lot of rounds recently! That is awesome!

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

    But the next round is after 2 weeks. That is not awesome.

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

      I suppose next round will be earlier than in two weeks. It just hasn't been announced yet.

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

Hope I become CM after this round.

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

Hope it will be harder than before

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

i wish i could solve 2 or more problems this time :)

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

hope is a good thing..

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

I Hope the statement will be short and nice like the announcement .

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

Auto comment: topic has been updated by Ari (previous revision, new revision, compare).

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

(https://imgflip.com/i/316rg9)

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

round done by weeb... ... ..... .. ....... .... ... i am scared to try it!!

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

    How come you haven't been blocked yet? I intentionally commented about 10 bad comments and Codeforces already threatened me.

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

Oh Mexico Round SMT new

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

Is there any plan to announce the scoring distribution?

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

Thanks for div2. I want to be Master.

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

I know , U know, what if I told u...

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

I will try to do screencast with live commentary in English. If everything will go smoothly, you will be able to check it out on my YouTube channel some time after the round. Warning: English will be bad.

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

So what's the score for each problem?

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

where is score distribution

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

1166C - A Tale of Two Lands remind me of gravity falls :D

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

I was glad that the problems seemed good to me, but actually from my extra registration I can't submit my code, and it just alerts "You have submitted exactly same code before", though I didn't succeed to submit anything... Lost the chance to climb up qwq

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

Good Contest.

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

TestCase 12 for C?

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

    If I'm not mistaken, test case #12 for C is the test where the answer is bigger than 2^31-1.

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

      I was handling it. Let me check again. :/

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

Yay! A chance to be master if system tests won't reject me :P

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

    congo...

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

      Thx! Took me 3 years :D

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

        I m struggling in green and grey...:'(

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

          It has been only 3 months you have been participating! See my rating graph and look how I was struggling in newbie. By the way, I was newbie when I changed to that handle ;)

          Just choose a good practice way and reaching to expert is really easy after having enough experience and algorithmic skills.

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

            Right bro, @PikMike is also good example like you...

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

    You can't even imagine how much I understand you ;)

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

      Well, you also had some time in the very top of CM so I think that means a real potential to be master in the next contests! Good luck!

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

Mathforces???????????????????????????????????

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

I need proof for E

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

    How to solve E?

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

      Necessary condition for the solution to exists is : Any two days must have a store in common.

      Seems like, it is the sufficient condition too.

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

      This is really intuitive solution, which I came up with in last five minutes: iff there's any element that are contained in all $$$m$$$ days, you can make the number extremely big prime so that you will get larger LCM. Is it true?

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

        seems to be false, sorry

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

          Counterexample = 2 3 5 with her buying (2,3) (3,5) (2,5) from stores.

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

          This is true (it's sufficient), but it is not necessary. Other cases can be valid as long as there is no pair of days on which Dora visits two disjoint sets of stores.

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

        An example that your argument is not holding for "only if"

        3 4  
2 1 2  
2 2 3  
3 1 3 4

        Valid sequence :
        7 5 7 2

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

      Check if for any $$$2$$$ different days sets of shops Dasha visited have nonempty intersection

      But I don't know how to prove that it's a sufficient condition

      Actually, I just submitted that because I saw how much people got it accepted, so it has to be something really stupid O_o

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

        I did the same thing... didn't believe it will actually work...

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

    Let's take $$$m$$$ different primes, one for each query. Start with array of 1, and then multiply all the numbers in one query by the prime of this query. In each query LCM of our numbers will be product of all primes and LCM of all other numbers will lack prime of this query.

    Of course, this is true when all queries are pairwise intersecting.

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

    If there exist two disjoint sets, answer is obviously no. If every pair has common element we can do the following: First set all numbers to one. Lets consider one set: a1,a2...aS. We may multiplay all numbers a1,a2...aS by arbitrary large prime number. It will guarantee us that this set is correct. On the other hand, we dont make our situation worse, for other sets(days), i think it is clear why ( from definition of LCM).

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

    If on any day the set of stores visited by Dora is a subset of the set of stores visited by Swiper on any other day then it is impossible, else it is possible.

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

ALL THE PROBLEMS WERE BEAUTIFUL EXCEPT FOR C

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

D is hard to implement.

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

    Well, I didn't know my solution is $$$O(k^3logm)$$$ for each query before submitting it. Time to pray for not getting TLE :P

    What I did was choosing the numbers greedily (the maximum I can put).

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

    And I started with D only, took me 1 hr 40 mins, RIP rating.

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

Constructforces :v

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

For question C what is going wrong with this approach? https://codeforces.me/contest/1166/submission/54311053 thanks.

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

Is it just me or was problem A description confusing? I still don't get how three chatty students paired together are considered three chatty pairs, while two students together are considered one chatty pair

how does this generalise for n > 3 ?

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

    Number of (unordered) pairs of n elements: n * (n - 1) / 2. That's a well-known formula :)

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

    From three students A, B and C, we get three pairs which are — (A,B), (B,C) and (A,C).

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

how to solve E?

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

    The answer is possible if and only if there exists no pair of days on which Dora visits two disjoint sets of stores.

    The proof that no other cases work is trivial; the proof that all of these cases do is less so.

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

      Proof by construction -> for each set have unique prime and multiply all values visited on that day by the prime. Values start with 1 on day 1. Because each set contains its own prime and all primes of others, LCM in it will be maximum possible. On the other hand, if there is some value between stores that this set did not touch and its value is maximum possible, then it must contain all primes (I mean, number stored in it is divided by all those primes) and so each set contains it, contradiction, we said it was outside some set.

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

Problem C. Testcase:

4

1 1 2 2

What is the answer?

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

    All of the potential values are guaranteed to be distinct, so this is an invalid case.

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

      It never said they are distinct. "unordered pairs formed by two different elements", does not specify that, are two numbers distinct if they have the same value or different index? I went for the solution that counts such case just and it got accepted.

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

        The second line contains n pairwise distinct integers...

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

          Thanks, I see. It should be part of problem, not "Input" part then. I think, input is for constraints on sizes, not number properties.

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

Thanks, Codeforces for another good round! Although, unfortunately, it will take a long time until the next round...

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

IMHO, problems D and E should have been valued equally. I didn't solve E, but I can see in the comments that there is a simple idea behind the solution (and more people solved it than D). On the other hand, D was a rather implementation-intense problem, it took 40 minutes to code the solution :)

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

    I came up with Idea for E but did not submit it, it looked too easy. Seems I had right solution tho. I'd not say the idea is simple, but implementation really is.

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

for problem D isn't is hold? Any number between lower bound and upper bound form by current state a solution can be find ,i just did binary search by this but failed

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

    My solution to D relied on the fact that through messy casework, we can prove that two numbers x and y with |x| <= |y| form a valid pair if and only if |y| <= 2|x|. I thus created a vector containing the absolute values of all the datapoints, sorted this vector, and then did two pointers.

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

    just found it was small mistake on bound ,modify it then got AC

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

thx 4 fast testing)

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

I read comments, many users have solved problem D with greedy algorithm. My solution is constructive, works in O(k^2) per query. I missed couple of minutes to submit:(((, but I believe I have a proof for my solution. Has anyone else solved it with a not greedy algorithm?

UPD: It turns out that my solution was wrong :( sometimes it doesn't find any solution), which is a pity as my solution was quite beautiful.

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

What is the point on setting too much math problems? >:(

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

    Do you think that implementing boring algorithms is better than nice, math problems with short and clean code?

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

      Yes. Precisely building your answer through hard thinking and combining algorithms is much prettier than just solving an inequation on paper and then passing it to boring code. This is not IMO but ICPC

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

Did anyone else solve E by constructing a DAG based on subsets, and checking for existance of topoloical order in that graph?

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

    This argument is valid, but I think you will need additional observations for dealing with memory issues (to make sure not too many subsets are being considered) It is enough to ensure that there are no conflicts — i.e, there are no set A and B of given sets, such that $$$A \subset B^c$$$. What you said is equivalent to this, but using some unnecessary subsets.

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

    ba iharke Paron Pashinyan

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

My first contest after a loooong time! Hello again Codeforces! ^^

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

Can someone tell me why I got WA on tc 20 for C 54289806

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

    Sorry, i cant understand java code completely, but did you count pairs {0,0}? It seems like not

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

      All numbers are pairwise distinct. {0, 0} won't appear.

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

    Collections.binarySearch() is of no use when finding index if there is repetitions.

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

When both you and the problem setter do the math wrong...

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

    How come in problem C for the test case 3:

    2
0 1

    The answer is 1? Shouldn't the answer be 0?

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

Did you guys know that a = b.flip() on bitsets changes value of b??? I guess I'm lucky to catch that bug while participating out-of-contest :D

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

I recommend you two pointers method for problem C. In my opinion so easier way than binary searches.

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

Auto comment: topic has been updated by Ari (previous revision, new revision, compare).

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

I cheated this contest and i am sorry for my behaviour, but i am still in the official list of participants and i think that i don't deserve to be in the official standings.

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

It’s a pity that I didn't become winner of div.2 qaq~

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

Auto comment: topic has been updated by Ari (previous revision, new revision, compare).

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

I suggest from now on everyone who cheats to get last place in the contest as punishment, like i did and got -181.

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

Codeforces must fix at least 1 contest every week. If possible 2-3 would be great!

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

The second test case for D problem is wrong as it is clearly mentioned in the question that ri>=1

juckter

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

    how is it wrong? The sequence only has one number so $$$r_i$$$ is not relevant.

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

Can someone please tell me why my codeis giving runtime error the only thing i did was to replace the first scanf for no. of test cases to cin

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

    You shouldn't mix scanf/printf with cin/cout if you're using ios_base::sync_with_stdio(false); , removing that line would fix it. Also, this blog post is for round #561, not #560.

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

Me during the contest:

(for those who don't know, they are pinyin for the Chinese words "yes" and "no" and I speak Chinese as a native language)

→ Reply