Hello, Codeforces!
dannyboy20031204 and I are glad to invite everyone to participate in Codeforces Round 772 (Div. 2), which will be held on Feb/20/2022 17:35 (Moscow time). This Round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems.
We would like to thank:
- 74TrAkToR for excellent coordination of the round and translating the statements.
- 244mhq, generic_placeholder_name, null_awe, ptd, Fysty, 8e7, yungyao, Devil, amano_hina, Dragonado, DIvanCode, voventa, plagues, Marslai24, FHVirus, saarang, olyazyryanova, marzipan, Prokhor08, sam571128, efimovpaul, ColtenOuO, zarubin, sus for testing this round and providing very useful feedback.
- generic_placeholder_name for providing an awesome problem idea
when our problems are rejected by the coordinator. - 8e7 for verifying our statements and tutorials, correcting many mistakes and making it easier to read.
- MikeMirzayanov for great Codeforces and Polygon platforms.
Score distribution: $$$500 - 1000 - 1500 - 2250 - 2250 - 3000$$$
I hope all of you will enjoy the problems and have a positive delta. GL & HF ^^.
UPD1: Thanks for your participation! Editorial is out.
UPD2: Congratulations to the winners:
Div1 + Div2:
Div2:
As a tester, I will tell you one possible solution to the problems:
If you hire the infinite monkeys, one will complete works of William Shakespeare, and another will give you all the code you need for this round. And if the two decide to work together, you might get something cool like this: 138874533.
Anyways, good luck and enjoy the problems!
As a tester, this round is really worth to participate in
Yeah, problems were really interesting ,thanks abc864197532,dannyboy20031204, all the testers, coordinators and everyone who contributed in this round.
clashing with feb cook off
update : cook off posponded to 21 feb.
Codechef never wanna fight with Codeforces..
CodeChef did'nt want to lose participants.
As a tester, I'll say that I think this round is very good!
As a tester, I think the problems are very interesting. May the force of positive delta be with you!
As a tester, I think the problems are very interesting. Good luck and have fun!
As a participant, I want to make my color blue :-)
You'll do great!
Thank you!
As not a tester, I hope participating this contest won't make my social credit and my rating decrease just like my contribution
I wanted to upvote your comment, but this stopped me from doing so :)
...
... Few peeps upvoted and changed the count :/
abc864197532 is a favorite to make it in the national IOI team and he will get gold medal in IOI 2022!
\abcorz/
BurnedChicken is also a favorite to make it in the national IOI team and he will also get gold medal in IOI 2022!
Fysty is also a favorite to make it in the national IOI team and the national IMO team and he will also get two gold medals in IOI 2022 and IMO 2022!
orzabc
As a tester and a statement verifier, I highly recommend participating in this contest! The problems are concise and well balanced, and I hope you'd find the problems (and editorial) easy to read.
\8wcporz/
\8wcporz/
\8wcporz/
\8wcporz/
\8wcporz/
\8wcporz/
\8wcporz/
\8wcporz/
As a tester,
I want everyone to play osu!I hope everyone will enjoy this Taiwanese round.As a tester, I made the observation that this contest may or may not have problems. Unless you take the contest, you will never be able to find out.
Good luck and have fun!
\abcorz/
\abcorz/ \gzcporz/
\gzcporz/
\gzcporz/
\abcorz/
As a friend of a part of testers, why didn't I even hear this contest before this post :(
Never mind, it's time for me to participate :)
\8wcporz/
too few 1600-1900 problems in recent div2's, anyone?
The ideal order of the first three problems should be 800-900 -> 1100-1300 -> 1400-1700 I think
Yea, going to be speedforces for me unless I get enlightened by algod.
Good luck everyone for the round. May every newbie become green in this round.
May you become newbie again.
Why would you wish something like that? May every green coder also becomes a specialist.
gagan_sharma Why did you reply to your comment with your another account and reply to your another account with your account again?
I saw your code, and you two are the same person
https://upload.cc/i1/2022/02/18/7tcUsB.png
What a Multiverse of Madness!!!
Nope that's not my account, maybe a prank account by some friend. I don't care if you get it banned or anything.
Interesting self-loop :)
...
As a tester, I can confirm that the problems are all interested and worth reading. Good luck!
null_awe porz
o wow congrats on CM!!!
tyty uwu
It's timing is clashing with IND vs WI match and Barcelona vs Valencia match on Sunday :(.
Then, it will clash with my murtastanbig time.
why is this blog still not at home page? eagerly waiting for this round , have always loved taiwanese contest problems :)
XDDDDD
I think this contest is gonna be cool.
Which is the lie the mask or my face
Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1! Taiwan No.1!
taiwan pog
i8d more like i8deez nuts.
amogus
monke
Codeforces contest question's are really good as compared to all other platforms.
who ask ???
I asked.
It seems that there are some problems with the country filled in someone(who sets the theme)'s profile?
I have never seen a Chinese who does not fill in the motherland as China.
Then you must havn't seen tibetan people who doesn't fill in the motherland as Tibet.
But the Taiwan independence elements took the opportunity to make trouble :).I still think there are some problems.
i missed the part where thats our problem
Where is my money ?
I hope to achieve new division as well as all participants
In this round, I will solve the problems and have some Waimai~
As a CPer, I don't care about politics at all. Let's just talk about problem quality/style/solution and make codeforces a CP community.
I noticed that abc864197532's profile picture is Kou from Arcaea which is great
He has two stars in Arcaea.
\abcorz/
dXqwq also has two stars, and their rating are also very high
feel bad when I realize that my best play is barely 12.5 :(
As not a tester, can we forcus on the contest, but not the authors?
Stop talking about Taiwanese Round and Chinese Round please, let's just participate in this round and you'll find out if it's interesting or not. By the way, Codeforces is not a place to talk about politics.
wow. I remember old dannyboy20031204 post about his fast level up in cp. And now he is problemsetter. Not Bad.
\dannyboyorz/
abc round on cf XD
Codeforces is not a place to talk about politics ， if you want to talk about Taiwanese Round and Chinese Round , You are challenging China！
As a person writing a comment, I hope other people who write comments also write comments.
Remember that Codeforces is not used to talk about politics.It is home to people who like programming from all over the world.
Are you pretest 2,because i am not getting what's wrong with you
Can we just focus on the contest instead of the controversial political problems?
operationforces!
sadly Speedforces and I'm not fast enough :/
100 points could get me 600 higher position
my today contest scenario :3
How to solve the type of problems like D ?
I just used dynamic programming where $$$dp_i$$$ stands for number of elements between the range $$$[2^{i-1}, 2^{i})$$$. Then, $$$dp_i = dp_{i-1} + dp_{i-2}$$$.
I think pretests of E are very weak. In my solution, I did two topsorts for each component and even tho I forgot to clear the adjacency list after the first top-sort, it passed pretests and I resubmitted.
Also, Problem A-E for me in this round was 5 mins of thinking and all the rest time spent in coding. Problems were not nice [A-E].
literally solved first 3 pblms by simply guessing. Hope pretests were strong.
how to do F? Is it some DnC magic?
You can find that when the pair (x,y) is optimal , only if $$$\forall_{x<i<y} w_i>max(w_x,w_y)$$$.
the number of such pair is $$$O(n)$$$.
Logic for C?
Hints for Problem D: Infinite Set
Solve for the following testcase:
In other words, we start out with an array of length $$$1$$$ containing $$$a_i = 1$$$ as the starting element. How many elements can be constructed such that they are strictly less than $$$2^p$$$
Think in terms of binary, what does operations (2) and (3) look like in binary?
Operation (2) is appending $$$1$$$ at the end of the binary representation. Operation (3) is appending $$$00$$$ at the end of the binary representation.
Define $$$f[i]$$$ as the count of numbers in the set when we append exactly $$$i$$$ bits to the end. Can you find the transition for $$$f$$$? Does it resemble any known function?
$$$f[i]$$$ is, in fact, Fibonacci numbers, as $$$f[i] = f[i - 1] + f[i - 2]$$$ (i.e, you either appended 1 to a binary string of length $$$(i - 1)$$$ or you appended $$$00$$$ to a binary string of length $$$(i - 2)$$$
Now that we have the count of numbers of each length, define $$$dp[i]$$$ as the count of numbers with binary lengths $$$<=i$$$. Find out the transition for this DP.
$$$dp[i] = f[i] + dp[i - 1]$$$
If you create the tree by simulating the process, you'll notice that every element has 2 children. However, any element can have only 1 parent.
Suppose $$$a$$$ and $$$b$$$ are present in the original set and $$$a < b$$$. If $$$b$$$ appears as a descendant of $$$a$$$'s tree, we can simply ignore $$$b$$$. If it doesn't, it means that their trees will never overlap.
Since an element only has one parent, we can keep moving up the tree to see if we encounter an existing number. It'd take at most 32 steps, since at each step, we'd either chop off $$$1$$$ or $$$00$$$ from the end.
Process all the elements in a sorted order. For each element, check if it is a descendant of any previous element's tree. If it is not, add it to the set of root vertices. The answer for each root vertex is independent now, and is similar to the answer for tree of vertex $$$1$$$.
This is impressive ! Thanks !
Would be more than grateful if someone could point out what I'm missing in my following submission to C: https://codeforces.net/contest/1635/submission/147096871
nvm i'm an idiot :D
It was a blood lesson to use log instead of logf in the C++ 11 and later standards.
Was the idea of E something like this —
I didn't use step 3 and 4, but I did use a pseudo topsort where I first arbitrarily set one set of vertices of the bipartite graph as cars moving to the right, and the other set to be the cars moving to the left. Then, whenever a car moving to the left has destined cars all placed or a car moving to the right has irrelevant cars all placed already, we put this car into the queue.
Yes, but not exactly.
In step 3, the direction depends on both the type and bipartite colouring of u / v. Basically our colouring means L / R right? So we want L before R for type 2 and L after R for type 1. So we need to check the colour of u / v to set this direction correctly.
Except for that one change, your post exactly describes what my submission does — 147085911
I did almost the same you are describing, except that instead of toposort I used posorder in the dag (easier to code in my opinión).
Problem C, submited in 1:59:57..., and got accepted. Never give up. QAQ
Same here. I submitted C in 1:59:49 and I also got AC! These last moment's AC gives so much joy.
My idea for D :
Now how to count what are elements "connected" to $$$a_i$$$, this is what I did :
But I get wrong answer on pretest 5, can you spot it where my idea / implementation might be wrong? My code : 147094782
I guess the recursion should've been $$$dp[x] = 1 + dp[x-1] + dp[x-2]$$$
Umm why is that?
let's say $$$p=4$$$ and you have a number $$$1$$$, which is $$$0001$$$ (in binary form) you can also have $$$0100$$$ and $$$0011$$$, and the possible numbers are thus $$$dp[1] + dp[2]$$$, but you still have to count the $$$0001$$$ itself, which yields $$$dp[3] = 1 + dp[2] + dp[1]$$$
Yeah I also think about that.. but why wouldn't the sum of fibonacci numbers solve this?
while(tmp > 1){
Shouldn't this line be while (tmp > 0)?
I don't think that's the issue... because I check if $$$tmp = 1$$$, then I check whether 1 is in the set
But it's also impossible since it is guaranteed that $$$a$$$ is distinct
Try this test:
4 3
1 3 4 7
Thanks for your test case! I got it accepted. It is a silly mistake that I made
Oh, I had this pretest getting me 7 times. I think there's a problem in choosing the correct i to summarise first I fibonacchi numbers: if i-th element of A is a degree of 2, (x-th), then you have to count first p-x-1, since our number has x+1 digits in binary system. Otherwise there are x digits and we have to count first p-x. Sorry if I'm wrong, but I think that's the problem.
Hmm.. but I used the MSB function to get the leftmost digit in binary. Shouldn't it be the same?
Oh, I guess it is. Yeah, sorry
No worries! Thanks for helping tho. Because this is very bother my mind :')
Very interesting problems.
Thank you writers, testers and coordinators so much!
How does B work, there is some "trick"?
my greedy approach is:
Process from left to right. whenever we meet a peak at $$$a[i]$$$, set $$$a[i+1] = max(a[i], a[i+2])$$$ and keep moving.
Ah, ok, I see.
A local maximum counts only then as a local maximum if it differs from both adjacent elements, ie
2 3 3 2is not a local maximum.I tried to solve a more complex problem :/
always change next item A right after local max to max(local max from left, item right from A)
Why is the output for Problem E test 2 'No'?
because here is cycle(1-2-3-1) of odd length. but directions changes between neighbors.
Where is it given that directions changes between neighbors
Because if two irrelevant cars share directions, one have more speed than the other, they will meet.
Good problems but presets were weak
unfortunately ran out of time for problem D. anyone else solved it with sum of sums of fibonacci for unique items (in terms of reachable by 2*y+1 and 4*y)? will try submitting after system testing
yes
if someone is interested in solution 147106550
sus likes to give feedback for contests instead of giving contest, after becaming pupil :)
Giving?
missed some observations on C and ended up submitting a complicated solution very late
expecting a big rating drop, but it's also a good opportunity to find out my weaknesses
Great contest with interesting problems! plus amazingly fast rating changes!
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Rating only increases by one when cheaters are removed , so are there very less cheaters?
thanks for the fast editorial!
observationforces
Can anyone help me out with the 4th problem. I calculated the Fibonacci series and recalculated the sum in the vector v.Then simply for every val in the array calculated the possible root val and if its not visited previously marked it and added the precomputed val to the ans.147109778 . Its giving was on test 5
D is a great problem!
Finally some rating gain yay
Thank you for great problems and fast editorial. I really enjoyed solving D and E. Very good round!
I enjoyed this contest solved A,B and C
Bro I am sorry if I demotivate you(I am just curious) , you have solved a lot of problems , how are you still green?
Yeah bro! same question i asked from myself :(
I think at this point , you should just start giving virtual contests instead of practicing from problem set. You already have learnt all the topics , now focus more on performing good in real contests.
As a first-time contestant for CF but years of experience on other CP contests, I kindly feel annoyed with that all problems in the contest are greedy related. Is this some norm for CF?
There was a fantastic round :) thanks.
D was a great question!Need both logic and algorithm ability.I like this problem.But somehow,as the rating contribution reflects,the gap between C and D are a bit big.