shishyando's blog

Codeforces Round #781 (Div. 2)
By shishyando, 3 years ago, In English

Dear Codeforces Community,

Kirill22 and I are glad to invite you to Codeforces Round 781 (Div. 2), which will take place on 08.04.2022 17:35 (Московское время). This round will be rated for the participants with rating lower than 2100

These are some great people that we would like to thank:

You will have 2 hours to solve 5 problems.

One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

The scoring distribution: 500 — 750 — 1250 — 1500 — 2250

P.S. I have been waiting for a long time to hold another contest and now this time has come. I really hope that you will like the problems, good luck!

UPD: Editorial

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

Comments Comments (93)
| Write comment?
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Me seeing a 5-problem round and this score distribution: Regular C->D->B->A tactic goes brrrrrr

Time to start solving from the beginning again. The era of valueless A's has gone!

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

    Me after upsolving: This tactic has a reason to go brrrrrr aside of the score distribution. If I started with C in contest I'd be dead meat lol.

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

As the richest tester, give me contribution.

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

Finally a div2 round. Wish everyone good luck!

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

If you downvote this comment, you will lose rating) Good score distribution, wish everyone good luck

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

Only 5 problems... Is it mean that E will be harder than usually ?

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

Excited about the interactive problem!

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

    Did you get specialist performance in the contest?

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

It is seems to be a speedround as the friendly scoring distribution qwq

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

As a tester can say, that round made by the legends!!!!

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

Only 5 questions in the round! Hope it's not a speedforces round.

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

Ivanovo is everywhere

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

I likes codeforces and contest.Good luck to all

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

This time no specialist as a tester!

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

Good luck!

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

As a friend of tester Codula ,give me contribution

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

Five problem contest (◎﹏◎) Hoping it to be a hard contest. :)

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

From Ivanovo with love!

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

As a tester i highly recommend you to read all tasks!

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

which one is the interactive problem C or D ?

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

Good luck everyone! I wish you an awesome contest. and thanks for everyone who worked hard so we can have fun after 2 hours!!

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

    tbh do u really wish the luck for everybody or u just wish a positive contribution for urself lol ;)

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

      hahaha that is a nice one! i really wish good luck. and some contribution won't be bad haha

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

I think D is a good problem.

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

The statement of problem B had some issues ..anybody else felt the same??

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

Is there a reason not to have $$$a, b \leq 3 \cdot 10^9$$$ (or lower have a smaller limit on $$$x$$$ if 32 bit integer overflow was your issue) in D?

At least for my soln, not being able to query $$$2^{31}$$$ requires me to handle the bit corresponding to $$$2^{29}$$$ being set as an edge case due to this :/

Nice problem regardless though.

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

    I agree, I got a program to almost work but I couldn't handle this edge case. What was your approach for this?

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

      Calculate for the bits till $$$2^{28}$$$, lets say we know this value is $$$y$$$. Now the possible values of $$$x$$$ are $$$y$$$ or $$$y + 2^{29}$$$.

      The latter is only possible if $$$ y + 2^{29} \leq 10^9$$$

      Also clearly for any value $$$x$$$, if I can query $$$a = x, b = 2 \cdot x$$$, the result will be $$$gcd(x + x, x + 2 \cdot x) = x$$$.

      So we can just use this to check if $$$x = y + 2^{29}$$$ is a valid answer.

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

        I did something slightly different. I calculate some mask such that x+mask is always guaranteed to be 0 upto the k'th bit.

        We create two numbers by ofc setting and unsetting the k+1'th bit.

        Now for the k'th bit I set it to be 1 and I know if the k'th bit is unset in x then gcd(x+mask, x+mask and k+1th bit set) is equal to 1<<k. otherwise it is not.

        I'm not sure why I don't run into the same issue — here's submission

        153071792

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

    That's weird — I didn't have that issue at least in pretests. What was the approach?

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

    To add, I initially didn't handle the 2^29 edge case properly and caused me to get a WA on pretest 16.

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

    I think the special case almost destory the problem.

    I have to spend a lots of time to discussion, it makes my code ugly.

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

      Yeah, it took me $$$5$$$ mins to think of the soln to the original problem and $$$10$$$ mins to figure out how to solve this edge case...

      As if to make it sillier, the edge case is longer than my core logic
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        Actually you dont need to solve this as edge case. Instead you can start from a = 1, b = 3. If gcd is 2, then the 0th bit is 1. Then similarly ask for 2 and 6. If the answer is not equal to difference, you can set that bit to zero and continue. In this way, you wont make operation greater than a = 2^29 and b = 3*2^29 which is < 2e9. submission

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

          But if you fall into the solution the first time, it is hard to drop it and get a new one. You will try fix the corner case.

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

            Yeah. Agreed. Even I was able to figure only upto 2^31. Then I was not able to come up with the case. So I cursed the author ( No offense LOL) and then thought about this solution.

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

          Can you explain how gcd is related to bits here ?

          UPD : got it

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

    Completely agree. Mindsolved the problem in about 20 seconds then messed up implementing the solution for well over an hour because of this :(

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

How to solve E?

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

logoforces minforces

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

keep getting WA 1.5h on C, I misunderstood that all sons of any specific same parent vertex v can infect like 1->2, 2->4, 4->8.

I got an AC in 6 minutes since I realize that I was wrong before.

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

DELETED. (Sorry I misunderstood something.)

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

Anyone please help me!.. How to solve C? I tried to find of the number of parent nodes with at least one child , that is the minimum number of seconds we need to infect at least one. After that i sorted the sizes of them in order of the number of children each parents have in descending order. Then found out how many extra child's i need to infect in remmaining , If the number of extra child's i need to infect in ONE parent is odd , then i can also infect the root with it in [((extra+1)/2) + infected] seconds in total. But if it is even , then i need to infect the ROOT node [1] separetly , thus needing [((extra)/2]+1) + infected] seconds in total. I take the max value over all of these.

I am failing on tc 6.

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

    I kind of lost you halfway through your explanation (though I will note that you always need to infect root manually) but I can explain my idea.

    First just count how many separate disjoint sets of nodes there exist that can infect each other. Easily it is shown that all children of a node n belong in the same disjoint set. We can then simply represent these sets by numbers — so our final result is just a vector of numbers where each number is the size of this set.

    Now clearly it is optimal to first infect a node in the largest of such set. Also you must infect at least one node in every set. So sort the list in non-increasing order and remove the nodes you infect in each set. (So if you have 7 disjoint sets, you must remove 7 nodes from the first set in the list, 6 from the second... and so on until you remove 1 from the last).

    Now, you may or may not need to spend some additional seconds (call them t additional seconds) to infect some more nodes.

    We will binary search on additional seconds t.

    Suppose you need to spend t seconds. At least all sets you can subtract t from, and you may also pick t arbitrary nodes to infect.

    So, from our sets, remove t from each node, and then see if there are less than t nodes left. If so, then we can accomplish our goal with t nodes.

    Our final answer is size of sets + t.

    153054530 for clarity.

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

      Thank you !

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

      I have a doubt.. Isn't the additional seconds equal to the total nodes left after infecting 1 node in each set and spreading in each turn.So answer should be (total_left/2+total_left%2) since at each second we can infect and spread on every node available. What's wrong in this? Adding my Code for clarity:- for(int i=0;i<n;i++){ int tc=sets[i]-(n-i-1)-1; if(tc<0) tc=0; rem+=tc; } ans+=n+rem/2+rem%2;

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

        I'm not sure what you mean. After you infect one node in each set, assuming all nodes are not infected, at each second you have two things:

        1. For all sets that are not all infected, you infect one additional node. However, it doesn't mean that the number of nodes always reduces by the number of sets. For instance in 80,1,1,1 you need to keep infecting nodes in the 80 set.

        2. You may now pick one additional node and infect it.

        The key is recognizing if you know that we have t seconds to go, we can just let t seconds elapse and then do all the 2 operations together at the end, instead of trying to do them in the middle optimally.

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

          153071780 I am a bit confused yet again, Can you see my code & tell me what am i doing wrong. , Thanks a lot

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

            Failing testcase: Ticket 3686

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

              How do you find out the contest id?

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

                Open the problem and take a look at the URL of the page you are on.

                You'll find a 4 digit number. This is the contest_id.

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

                  Oh, thanx. But this is not generating any counterexample for my last submission on Problem C

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

Implementation of Problem C is on next level.

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

cool round

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

$$$D$$$ can be solved in $$$23$$$ queries by letting $$$x=4\times 5\times 9\times 7\times 11\times 13\times 17\times 19\times 23=1338557220>10^9$$$, asking $$$(i,x+i)_{1\leq i\leq 23}$$$ and use Chinese Remainder Theorem to combine the answer.

So it's basically not falling into the paradigm of another boring interactive problem that uses binary search :)

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

Can someone tell me why https://codeforces.net/contest/1665/submission/153033033 is TLE for Problem B? The solution is O(n)...

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

Somebody leaked my solution of B from room on YouTube . I don't know what to do now . Please help !!!

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

When i submit B it passes all pretest but now, It shows tle in 13 pretest why?

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

I am getting a WA on TC 20 in problem C , can someone tell what's wrong with my code

Solution link

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

so thx for anti-unordered_things test in B :)

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

Thanks for the amazing contest, really enjoyed it. How long does it need for the rating to change?

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

Is it possible to solve E with mo's and trie?

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

Can someone tell how the answer would be 4 for this test case for Question C

9 1 7 7 7 1 1 1 7

Thank you

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

Here's a screencast of me doing todays codeforces round:))

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

Problem D is very similar to a problem from Spain's Olympiad in Informatics 2022, which was held just last weekend.

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

Thanks for the round, every task is interesting.

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

Hi,
In the second problem, when I use a hash map to get the frequency of each number, I get Time limit exceeded on test 13. But when I use a map to do the same, It's accepted. Could anyone tell me why it's time limit when using a hash map?

PS: this solution using hash map and this solution using a map.

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

    Same happened with me

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

    Because of poor default hashing function. If you wanna use unordered_map or other data structures which are using hashing, write your own randomized hash function so it will be much harder to create such bad test-case for it. In this particular problem complexity nlogn of map is good enough to pass.

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

Solved B problem using unordered_map got TLE, Upsolved B using map with the same code and got accepted.

Is this a joke or what??!! :-)

→ Reply