Dear Codeforces Community,

Kirill22 and I are glad to invite you to Codeforces Round 781 (Div. 2), which will take place on Apr/08/2022 17:35 (Moscow time). **This round will be rated for the participants with rating lower than 2100**

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

- Artyom123 for round coordination (and KAN too!) and being in touch all the time for providing help
- Igorbunov, generic_placeholder_name, nskybytskyi, AlperenT, FairyWinx, TheScrasse, Ziware, vsinitsynav, wery0, Kotehok3, YanikusGG, Absyarka, FelixDzerzhinsky, Codula for testing and providing tons of feedback and making completely different submissions
- MikeMirzayanov for Codeforces and Polygon
- NEAR for supporting the Codeforces Community! You can find the details in this post.

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

Me seeing a 5-problem round and this score distribution:

Regular C->D->B->A tactic goes brrrrrrTime to start solving from the beginning again. The era of valueless A's has gone!

Me after upsolving: This tactic has a reason to go

brrrrrraside of the score distribution. If I started with C in contest I'd be dead meat lol.As the richest tester, give me contribution.

As a tester, please give my salary as contribution so I can be as rich as TheScrasse someday.

As an ordinary tester, give me contribution

As an ordiniest tester,give me +contribution.

As a tester, I enjoyed the round and I hope you do as well :3

As a fake tester, please give me contribution.

sure, here goes your fake contribution :)

As a contestant, give me rate

Finally a div2 round. Wish everyone good luck!

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

not if you don't participate

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

do you usually solve E?

Excited about the interactive problem!

Did you get specialist performance in the contest?

Spoilerso rofl

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

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

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

Ivanovo is everywhere

*everywhere in ivanovo

I likes codeforces and contest.Good luck to all

This time no specialist as a tester!

Thank you AHMADUL

I approve this message

Thank you ssuperunknownn

Good luck!

As a friend of tester

Codula,give me contributionFive problem contest (◎﹏◎) Hoping it to be a hard contest. :)

why so evil?

From Ivanovo with love!

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

which one is the interactive problem C or D ?

My guess is D

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

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

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

I think D is a good problem.

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

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.

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

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.

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

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

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

I think the special case almost destory the problem.

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

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

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.

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.

Can you explain how gcd is related to bits here ?

UPD : got it

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

How to solve E?

logoforces minforces

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.

DELETED. (Sorry I misunderstood something.)

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.

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.

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;

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:

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.

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

Failing testcase: Ticket 3686How do you find out the contest id?

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.

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

Implementation of Problem C is on next level.

cool round

$$$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:)Can someone tell me why https://codeforces.com/contest/1665/submission/153033033 is TLE for Problem B? The solution is O(n)...

use map instead of unordered_map

why is this happening?

maybe this blog could help u

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

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

Check this. I think using map (not unordered) may help.

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

Solution link

so thx for anti-unordered_things test in B :)

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

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

Yes, here is my python solution using trie. 153087908

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

Infect node 2,3,4,1 in the first 4 seconds.

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

When will rating be updated?

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

Thanks for the round, every task is interesting.

Hi,

In the second problem, when I use a

hash mapto get the frequency of each number, I getTime limit exceeded on test 13. But when I use amapto do the same, It'saccepted. Could anyone tell me why it's time limit when using a hash map?: this solution using hash map and this solution using a map.PSSame happened with me

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

In question B, it is mentioned that an operation is swapping 2 elements. but what if I swap a single element. Is it allowed?, will it be considered as an operation??

No, it is mentioned in the question, that an operation will be considered only if we have swapped 2 elements, neither more nor less.

I think in the first test case of B question (Array Cloning Technique), the result should be 4 operations, not 6. Please explain if I am correct or no.