Hello Codeforces! （你好，代码部队）
We are glad to invite you to participate in Codeforces Round 872 (Div. 1) and Codeforces Round 872 (Div. 2) on 08.05.2023 15:05 (Московское время). Please note the unusual start time.
This round is rated for all the participants. You will be given 5 problems (one of which is divided into two subtasks) and 2 hours to solve them in each division.
Assume you are YuezhengLing, and in this round, your best friend LuoTianYi will give you several problems to solve.
(LuoTianYi is the left one and YuezhengLing is the right one)
We would like to thank:
RedLycoris, CrTsIr, Sunset1028, SanweiTreap and Gellyfish for writing the problems.
Artyom123 for coordinating the round.
MikeMirzayanov for great Codeforces and Polygon platforms.
He_Ren, zhoukangyang for our red suns testing the round.
Qingyu, zimpha, SeeleVollerei, Crying, rui_er, Kevin114514, Lynkcat, lgswdn, FreshP_0325, mzen for red testing the round.
KbltQaQ, LHQing, Falashiro, NemanjaSo2005, geospiza, Kohaku, maoweishou, welleyth, EasonTAO, Rushroom, Gheal, rsj for orange testing the round.
Error_Yuan, fishy15, Lyrically. cadmiumky, yash_0402, smokebellew for purple testing the round.
LRL65, ayhan23, Zhangxuyang, Koful123, playerr17, AhmedEzzatG for blue testing the round.
zhy137036 for green testing the round.
tibinyte2006 for gray testing the round.
You
for participating in this round.
UPD: Scoring distribution:
Div.1: 500 – (500+750) – 1750 – 2250 – 3000
Div.2: 500 – 1000 – 1500 – (1000+1250) – 2750
UPD: Editorial is available here
UPD: Winners!
Div 2:
Div 1:
awa
QwQ
People of Codeforces! This is an extremely urgent PSA.
You are all aware about the strangely incessant efforts of the anime weebs to push anime propaganda upon us in recent times. From images of cute anime waifus, comments containing jokes with anime references, to entire blogs about anime. It must have puzzled you. Some of you must be wondering that what could, after all be the reason for this unholy weeb mass indoctrination.
Till yesterday, I too was unaware of the dark truth behind this mystery. However, I recieved shocking intel from my contacts in the CIA, and I am compelled to share this information with you, as the fate of the world hangs in the balance right now.
Last year, top-secret clinical trials were conducted by the NSA, which revealed that watching anime decreases the IQ of the viewer by 69, and the only way to reverse this is to listen,or should I say be enraptured by ethereal songs of the divine Rucka Rucka Ali. (Link to the study.)
This alone should be cause for alarm, but unfortunately, there is more bad news. The weeb takeover of our great platform was originally started by the Illuminati, at the behest of none other than their Supreme Chancellor, Herr Pewdiepie himself. The Illuminati recognized that the people of Codeforces were the only force capable of stopping their plans for world domination with ad-hoc problems, and conspired to land a devastating blow to us by crippling the intellect of a large (and sadly ever-increasing) part of our population.
I understand that the situation seems dire, but it is not too late to vanquish the debauched and immoral anime armies of the Illuminati. The Lord Sparky_Master_WCH1226 has had counsel with The Reptile king LeafyIsHere, Queen rotavirus, and the Archangel Donald Trump and has come to the conclusion that it still isn't too late.
The lord Sparky_Master_WCH1226 has tasked me, his prophet to deliver the following passage to his followers:
Verily, whenever thou art beset by the alluring temptation of anime tiddies, close thine eyes and allow the vjudgian segment tree to lazily propagate its divine power throughout thy soul. When the desire for an anime waifu doth become too tempting, turn thine eyes to the realm of reality and seek the companionship of a living, breathing, coding maiden. Shouldst she refuse due to you being a total loser, thou must explain to her the sacred necessity of naming the firstborn in every household 'Bitset'. And shouldst thou ever feel that you are retarded, remember that you probably fucking are.Know that it is your duty to follow this passage until your very last breath, without waiver or hesitation. Let its words guide you through life and beyond, and may you find peace and salvation in their wisdom.
Remember brothers, we are the last line of Earth's defense against anime, and it is our reverent duty to utterly fucking annihilate the hordes of the weebs in this unholy war that they have started. SAY NO TO ANIME!!!
then my IQ would have have been decreased by :|
same feeling i have gotten...
this is high-quality shitpost, so it got upvote from me
Hail Sparky_Master_WCH1226
why is this being downvoted lmao cf community has no humour
This is really long, any summary?
Sauce?
The divine message was revealed to my unworthy mortal ears by the lord Sparky_Master_WCH1226.
how is sparky master related to rotavirus
She is the living, breathing, coding maiden I asked out on a date, when the desire for an anime waifu became too tempting.
nono I was asking sauce for the anime pic.
ovo
drake?
You bought my participation with that anime picture XD
As a tester, I recommend reading all problems. GLHF!
hoping for easy A this time so more people can participate otherwise they will just leave :|
As the gray tester, I guarantee that taking last place in this round will result in negative delta.
Good luck in your achievement!!!
How did you get negative rating???
Submit fail hacks on people in your room some 80 times or more to get negative delta in contests. (Scared the shit out of me last contest when I saw 74 unsuccessful hack attempts on my C submission xD)
And the first place will lead to a very positive delta.
damn you're right
Why there's no cyan testing?
Good question. Maybe this round is a BIT difficult.
As a (former) purple tester, I secured last place in testing easily. Anyway, good luck in the round!
puts on glasses Theoretically you should not be telling this information to the participants since several individuals may theoretically be able to find out about the topics of the problems of this round by getting the statistics of topics where you're good at or not based on your performances on CF, please don't blame me if this situation will happen
Maybe he was just pretending to be weak.
Sir but the task of testers is to test the round so that based on their opinions every problem in the final problemset is of appropriate difficulty, and if a person deliberately didn't solve problems on their full strength the quality of the round may worsen
Actually I tested this round last year when having lunch:P
Lyrically is a cute boy. I met him in Nanjing. He only studied OI for less than a year, but he can easily become a candidate master. This is incredible. From this, we can conclude that he is pretending to be weak (fAKe).
I advise u to stop fAKing and wear girls’ clothesxD
That is not possible! You should be my girlfriend!
No, she should be mine :)
错了错了 别骂了
No matter what gossip I say. Wishing everyone a good ranking!
As a tester, this round might be Chinese-friendly.
What does that mean? Lot of people say there is too much math in chinese rounds.
I think he means that the unusual contest time is friendly to Chinese, as we don't have to stay up late to participate in this round :)
Yeah, that's true. More contests at this time please!!
In fact, maybe a Chinese middle school student won't have enough time to the contest.
Kely!!!
Don't forget ds.
maybe have some well-know algorithm or trick in China?
So Div.1 D's solution is very similar to NOIP2022 T4?
gl hf
Cyan's : Are we a joke to you?
Yes
As a newbie I don't know much about how codeforces ratings work, but which of the two contests can I give and expect a change in my rating? Div1 or div2? Or will both not affect my rating?
Yot can't participate in div 1 because your rating is lower that 1900, but you can freely participate in div 2 and it will affect you'r rating
orz
orz
unfit my schedule but still appreciate
I really like a sentence from chinese participants:啊？()
啊？
Cute
What should I say.
HAIL KEK!
RedLycoris Orz
Hello, YuezhengLing and LuoTianYi!
wow！Nan-bei！！！！（我超 南北组！！！！）
awa
Lot of people say there is too much math in chinese rounds. Is this true?
(And many DS.)
But these are all stereotypes. I think there will be many interesting problems, too.
Hope to enjoy the contest!
Hoshino kawaiiiiiiiiiii
wow, LuoTianyi and YuezhengLing! what year is it today 我超！南北组！今夕是何年
Seems a lot of OIers like vocaloid (including me).
But I don't really like the style of the illustrations...
awa
Yet another Chinese round. Time to lose ratings.
From the time to the theme,it's not only round by Chinese but also round for Chinese.
I hope its not in Chinese.
Too much testers. Hoping for an amazing round.
Damn, div 0?
Why am I here?
Just to suffer...
Please continue this great time!And I love nanbei!
Damn, div 0?
As YuezhengLing, you gave LuoTianYi a dynamic tree.
%%%gezhiyuan %%%sanweitreap
As a tester, i think this round is a good one.It is friendly to beginners.Good luck to all!
You
for participating in this round.You
is very magical.1 up rate for cuteness ._.
Cutest invitation/announcement I have ever seen... <3
Anime, good.
Announcement so cute, I can't miss this contest at all.
Return to orange again,hope not dropping this time...
Extremely excited for this contest. Hoping for a positive delta
As a tester, this round has beautiful problems, really loved solving them. Good luck!
Points distribution?
W*c, Vocaloid!
Wish rp++
As a tester, I tested.
The moon shines, thank the moon.
The moon shines, thank the moon. YueLiangHaoShan, BaiXieYueLiang.
no way,is it 2023 ? last time i saw them was almost 5 years ago, rating++pls （今夕是何年）
wawawawawa!!!!!so cute!!!!
wa on pretest 2
Why unusual start time?
Maybe it's Chinese Round.
So the Chinese Round is only for Chinese?
No,it means it's provided by Chinese.
Friendly time for participants.
Can I become CM today?
D1 < C. Solve yeah you will become CM. just solve A, B, D1, C.
Also, remember to drink enough water during the contest. It relaxes the mind and makes you hydrated sir.
I will try not to go pupil.
Thnks man, i wish you become expert too.
Really hard to get +137
Yeahh i know :(
It's possible if you solve 4 problems quickly in div2,I think.
Chinese round has math problems. Hope to solve at least one of them.
i think that will be a great round.
as a tester I'm not, but it's a good trick to raise a contribution ( :
Upvote me to have +ve delta
-_-
All the best everyone.
orz
orz
orz
orz
My first Div 1 round. Hope for amazing problems)
Wow! Lyrically! btw gl!
Good luck!
I know that some Chinese people hold this contest. But as a Chinese middle student, I don't think it's a good time to start the contest. Chinese students especially high school students have nearly no time to participate the contest on Mondays. I'm just in Grade 7 but I have too much homework to do. I usually finish my homework after 10:30 p.m.
But it might be fit for Chinese oiers
The round started at 20:05(UTC+8), That's great. But today is Monday. Because of that, I can't participate this contest.
wtf, div1B have mathematical expectation.
Same buddy, I'm too weak in probability :(
It's not really about expectation. I mean it is but you don't have to know anything.
For k = 1 answer is obviously 1, for k = 3 the answer is also 1 (there is one point central point which is the intersection of paths A-B, A-C and B-C; this is the island you are looking for, if you move one step from it you can get closer to one island but further from 2 others).
So you need to solve only for k = 2. Calculate the sum of path lengths with standard tree dp and divide by number of paths (n-1)*n/2.
i know it. I solved this problem. But B2 is unreal for me
I am not sure why are you surprised/complaining then.
Arguing local behavior is not enough to ensure global optimality. One needs to argue that the function is convex (both for B2 as well as here, but here it's easy to see it by taking cases) for that to be enough (which can be done), but I found that the most important part that I almost missed.
Speedforces A,B
I'll never write div1 again!.. until I can solve d1C-D. div2 on my second account is way better than two hours of complete hell and a decent rating loss, which is what happens 99% of the time
Thank you for this contest. (Praying that I don't fail systests)
Why does div2C have such a weird test case?
WTF!!!
What did you find weird in this?
It is a common phenomenon to use memes in test cases, in fact
How to optimize in D1B2
Edit:nevermind, i was answering for div2 b
WTF ?
ah i was answering for d2b. Sorry
Wow, today I experienced the feeling of submitting a solution last minute. Nothing can beat this feeling.
Wrong Answer on Pretest 6.
Amazing problems D1,D2 (B1, B2). Thanks a lot :)
I solved D1, for odd n answer is 1, how to solve D2,i know what to do but can't optimize it.
Each edge of A- B counts as a sum of exactly C(down[B],k) * C(n — down[B], k), here down[X] is how many vertices lie in subtree X if hanging on vertex 1. (Here I consider that B is strictly deeper than A). Actually, in my solution of D1 I could have changed only 2-3 lines to get D2, but I noticed this only later. С(n,k) — binomial coef.
In problem $$$B2$$$. Let's calculate for every vertice number of good combinations for it, and then sum them. Look at vertice $$$v$$$. Let $$$a_1, \dots, a_p$$$ be sizes of its subtrees. The combination is good if and only if there is no subtree with more than $$$\frac{k}{2}$$$ vertices in combination. So if $$$v$$$ is not in the combination (if it is, there is a little change) the answer is:
How to calculate it?
Consider the set of good vertices for fixed locations of the $$$k$$$ nodes. This set of good islands is always connected and, if there are $$$m$$$ good islands, between them there are $$$m-1$$$ edges. Try to calculate the expected number of edges between the good nodes instead of the expected number of the nodes. Or more specifically, try to calculate how many times each edge will be between two good nodes. The answer will be this plus 1.
Let's find the number of bad combinations with vertex $$$v$$$. Notice, that there should exists only 1 subtree with number of vertices from combination greater than $$$\frac{k}{2}$$$. So let's fix that subtree. Suppose size of this subtree is $$$s$$$. Then the number of bad combinations is $$$\sum_{i=1}^{k} \binom{s}{k+i} \binom{n-s}{k-i}$$$. We fix the number of vertices from combination in that subtree: $$$k+i$$$. Then choose them with $$$\binom{s}{k+i}$$$ ways. And multiply it with $$$\binom{n-s}{k-i}$$$ — number of ways to place other $$$k-i$$$ vertices not in that subtree. We need to calculate this sum for $$$O(n)$$$ sizes. You can rewrite this sum as $$$\sum_{i=k+1}^{s} \binom{i-1}{k} \binom{n-i}{k-1}$$$. Why? Consider the binary array with size $$$n$$$ and $$$k$$$ ones. Then this sum is the number of way to have $$$ \gt \frac{k}{2}$$$ ones in the first $$$s$$$ positions. Let's fix the position of $$$k+1$$$ ones — call it $$$i$$$. Then we need to have $$$k$$$ ones on the left and $$$k-1$$$ on the right. Number of ways to choose left ones is $$$\binom{i-1}{k}$$$, on the right is $$$\binom{n-i}{k-1}$$$. The binomial coefficients do not depend on $$$s$$$, so you can calculate it fast with prefix sums.
Honestlly, I felt like div2. Problem D1 was like regular D problem. It's points should have been more at least 1750. Definitely NOT 1000 points problem.
How? That's way easier than regular D's. It's just counting total number of paths in a tree, and it's a very standard problem.
For K = 2 , it would have been WAY EASIER THAN REGULAR D.
but when u add K = 3, things become little complex. You have to add prefix Sum DP.
suppose all the neighbours of node are having subtree of size a1,a2,a3,a4,a5...
now, we need to find pattern of prefix sum DP where
Converting these three for loops into LINEAR TIME was definitely challenging for me, I don't know about others.
For any odd K the answer is always 1
LOL vgtcross, I sense sarcasm in that comment. And no, for k = 1 , it wasn't as difficult as regular D problem xD
Um... what? For any odd K, including K = 3, the answer is ALWAYS 1. No exeptions. You don't need any of that complicated stuff for D1 since for K = 1 and K = 3 the answer is always 1.
205099808
For any odd K, answer will be always 1 ,
I couldn't prove it myself, so I calculated it with program. I hope my program passes. Anyways, Can you please help me understand the proof, why for all odd K, answer is always 1 ? ( actually, I knew how to solve for even K , for even K > 3 , but I was stuck on solving odd K , when K > 3 ) . Alas, my little brain couldn't come up with above
answer = 1 when k = odd. vgtcrossUPDATE : WHEN K is odd, we will always have single center in tree.
for k = 3
cout << "1\n";well, I could not deduce that, and I honestly dont know how to calculate that. So, what I did is,,, converted these three for loops into one single for loop with suffixSumDp, which was really hard to find.
for $$$k \equiv 1 \pmod 2$$$ :
cout<<"1\n";D is a standard problem that consists of two phases:
add $$$k$$$ for rectangle area ($$$O(N)$$$ times)
after all addition, calculate the sum for rectangle area ($$$O(N)$$$ times)
I know it is can be done in $$$O(N \log N)$$$ by Binary Indexed Tree, but I did not want to think it deeply and wrote lazy propagation code with same time complexity which is TLE due to big constraints ... Is it intended?
Actually how would one create a BIT to do those in O(N log N) time?
I don't know, whether div2.C was tricky or i am dumb :)
SpecialCaseForces
I like the tasks, although I'm not able to solve B2/C even after thinking a lot
Isn't B1 answer just 1 if k = 1 or k = 3 and if k = 2 answer is sum of lenghts of all paths? (by lenght I mean number of verticies)
It is
I did not realize that lol. I took each node and determined how many different paths have that specific node as a valid one and summed all that up.
How to solve d1C? It's the hardest d1C I've seen in real contest.
For C, I try this: Every non-leaf node which does not have more than 1 child can be compressed into it's descendant. I think if we do this we might be able to pass with dp[node][val], which gives minimum moves to make all leaves in subtree of node equal to val. Because height of tree after compressing is logarithmic. Idk if it will work I fail to implement in time
No this is wrong, consider this:
Ahh I see.. Height can still be linear :/
hi, so the idea i got (and did not have time to implement in contest)
let dp[u][x] = min number of moves to get x as common xor among all paths from leaves upto u
then dp[u][x ^ a[i]] = min(dp[u][y] + 1, sum(min(dp[v][x], dp[v][z] + 1)))
You notice that all the dp values are atmost 1 off from each other, so you store min and the values of the state which achieve this min. Then you can do subtree merging.
Do dfs to solve subtrees.
When solving a subtree, basically you have the children subtrees that might be solved using OPTIMAL number of changes to some values and OPTIMAL+1 to the rest.
Merge that by looking at which values appear as optimal the most in the children subtrees.
Optimize the solution by using small to large merging.
It's a pretty standard idea tbh.
Even I got $$$\Delta \approx -70$$$, B2 is an overwhelming problem. This time I was completely defeated. Thank you for good contest!
I might've finally reached expert!
After this round, I'm still a pupil.
I am expecting to become a Master excitedly!
Can anyone Please explain the solution for Div 2 C / Div 1 A . . .
Suppose u 1st sitted the person at xi whose xi was greater than 0 then choose this as pivot point and make other people sit accordingly like persons with -1 will sit left to it and persons with -2 will sit right to it while persons with xi>0 are independent to sit at xi.
We have 3 cases to consider:
For the first 2 cases, we see that if we start at 1 we can never pick the left guys, same for if we start at m we can never pick the right guys
Now we just need to iterate over all possible middle values x, and fill up the guys to the left of x, and the right of x. We take the number of middle values < x and the number of option 1s, and number of middle values > x and number of option 2s
This can be done by sorting our array of middle values and doing some index checking.
https://codeforces.me/contest/1825/submission/205103435
that n==k case in B2 gave me a mini heart attack for my B1. relief when I understood that it gets handled automatically XD
Brainless D with only 7s TL
What a trash experience
I feel your pain
Bro tried everything 😭
oof.
Div2 D testcase == 'heng heng heng aaaaaaaaaa'
^ ^
Nice Problems
Chinese culture export
Strong pretests, but the successful hacking rate out of all valid attempts is 100%! Fascinating.
Nice Contest, especially on div2 d1, d2! Btw, I was so unlucky to get in top 100 because of modular mistake on d2 :(
Amazing problem Div1B (Div2D). I was struggling for "points" idea, that is, try to find number of configurations that can split two group of points and assign k//2 to each of them, and get stuck on it until the end of the contest (for almost 90 minutes). When system testing, a word "edges" came into my mind, and I only need to change two lines in my code to get accepted.
Gosh!It's so close to get a positive delta in div1. Why I am doing so bad at div1?
I managed to solve D1 but i dont have any idea how to solve D2.
How to solve D2?
Check edutorial. Generally speaking, if you think of a "correct" solution (look at the edges and not the vertices) of D1, it is immediately clear how to convert it to D2:)
How to solve div2 B problem...
Put the $$$\min(a_i)$$$ on $$$(0, 0)$$$ and put the $$$\max(a_i)$$$ on $$$(0, 1)$$$ or $$$(1, 0)$$$ depending on $$$n$$$ and $$$m$$$ which is greater, and you are very close to the answer. Just be greedy. Tutorial
what if the given array is .... a[] = {-1 , -2 , -3 , 10} here putting -3 on (0,0) would give me a max value of 28 but i can get a max value of 38 if i use 10 on (0,0). i guess i'm right ?
You are right, it's my fault. T_T I think it's actually about the maximum difference and the secondary maximum difference in the array, just make the difference between (0, 0) and (0, 1) and the difference between (0, 0) and (1, 0) to be those two maximum difference in an order depending on m and n which is greater. It can be proven that the pair of the secondary maximum difference contains at least one $$$max(a_i)$$$ or $$$min(a_i)$$$
I didn't think so clearly about that while programming to solve the problem because it's not important to decide which number to place in (0, 0). Actually the important thing while programming is to get the secondary maximum difference
This contest did show me the mirror after I became too much confident upon solving 6 problems in the last div4 contest. Was only able to solve A in this one :(
I hope I can become specialist
When will the rating be? Why won't these be preliminary results. Can anyone explain the distribution of points and how they will be calculated?
round approved
How is it possible that the guy from the first place on div2 did 3 tasks in the 9-th minute?
I don't think that this is possible too.
it seems to me that they know all the answers in advance and immediately send[maybe they can be cheaters]
I think that they will review this. It happens that they suddenly roll back all the ratings of the past rounds and then edit some things then you get back your rating; I think in that time, they review all kinds of things that might make the round unfair, so we'll just wait.
Problem B,C,D have completely different coding style/format. Hex_10EFFB_ is definitely suspicious.
I apologise for the fact that more than one person finished the race together. I am willing to be disciplined accordingly and promise that this will not happen again. Sorry！
gooooood contestttttttt___akfla
I am unable to digest this fact that, F1shHead who had a rating of 1359 and got a rank of 3984 got -1 delta, whereas I had a rating of 1338 and even got a better rank of 3556 but still got -23 delta. I don't find this appropriate. Can anyone help me figure out what am I missing!?
You get a fixed amount of extra rating during your first six contests. Notice that this contest was their sixth contest, meaning that they got extra rating. You have done more than six contests, you don't get extra rating.
(This is not how the rating system works exactly, but it's a decent simplification.)
Thanks a lot for the clarification. I was just wondering that, in general, does the performance in the first six contests affect the rating in the future contests also?
immediately, obviously yes, but not in the long run.
Is it possible I'm still grading grades. your first six rated contests are grading your grades.
Chinese: 很符合我对中国场的想象！
It fits my imagination of a Chinese round!
Div1 A is a great classification discussion trash question!
Div1 B is a classic counting garbage problem!
Div1 C is a large code volume classic dsu rubbish problem!
Div1 D is classic Chinese data structure with super large code volume and weak intelligence litter problem!
Div1 E is a waste problem because only one passed it!
I agree with you. And your English is GREAT!
.
Why
as a person who lost rating due to div1B, i think its one of the best problems i have seen.
I think it is a classic problem. If you know the theory of tree centroid, this question should be relatively simple. But if you don't really understand it, it may be a great question for you, but I don't think that makes it a good question for everyone.
And about Div1 E, it is a traditional CNOI problem. Huge code volume, huge data structure, but only two hours of competition time, so it's not comfortable for CF.
"I think it is a classic problem."
I would believe you if you didnt create an alt for shitposting
Stop showing off your pitiful level, it will only make you look like a loser.
I'm not showing, but criticizing the competition.
I love not being able to open codeforces in public without looking like a weaboo
Why is div 1 and div 2 held separately instead of 1 open?
Most of the problems are identical and for the ones that aren't either a div 1 user will do both in <= 10 mins or a div 2 user will not get that far.
Why is there 2 separate contests then instead of 1 open contest?
What's the issue with CF. Its opening on phone but not on pc.
I was reminiscing about Luo Tianyi's Vocaloid while solving the contest.
I'm a little curious about why Yuki__S2008 used inline assembly to solve both problems D1 and D2. However, on the first 3 wrong answers on D1, he or she used normal C++ codes (refer to this submission). Can anyone explain a little?
i suppose his nickname must be like: assembly fun fun fun