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 brrrrrr
Time 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 brrrrrr aside 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?
so 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 contribution
Five 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
I think so, too
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...
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
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.
Thank you !
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 3686
How 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
Well that sucks :(, thanks for letting me know...
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:))
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 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.
Same happened with me
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.
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??!! :-)