### RedLycoris's blog

By RedLycoris, history, 5 months ago,

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:

1. RedLycoris, CrTsIr, Gyy_cj, SanweiTreap and GeZhiyuan for writing the problems.

2. Artyom123 for coordinating the round.

3. MikeMirzayanov for great Codeforces and Polygon platforms.

4. He_Ren, orzdevinwang for our red suns testing the round.

5. Qingyu, zimpha, themoon, Crying, rui_er, Kevin114514, Lynkcat, lgswdn, FreshP_0325, Yuu for red testing the round.

6. KbltQaQ, LHQing, Forever_Pursuit, NemanjaSo2005, geospiza, METHOD_METAFALICA, maoweishou, welleyth, EasonTAO, Rushroom, Gheal, rsj for orange testing the round.

7. Error_Yuan, fishy15, Lyrically. valeriu, yash_0402, smoke_bellew for purple testing the round.

8. LRL65, ayhan23, Zhangxuyang, Koful123, playerr17, AhmedEzzatG for blue testing the round.

9. zhy137036 for green testing the round.

10. tibinyte for gray testing the round.

11. 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:

• +780

 » 5 months ago, # |   +85 awa
•  » » 5 months ago, # ^ |   +31 QwQ
•  » » » 5 months ago, # ^ |   -224 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. CLASSIFIEDLast 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!!!
•  » » » » 5 months ago, # ^ |   +36 then my IQ would have have been decreased by :|
•  » » » » » 5 months ago, # ^ |   0 same feeling i have gotten...
•  » » » » 5 months ago, # ^ |   +98 this is high-quality shitpost, so it got upvote from me
•  » » » » 5 months ago, # ^ |   +15
•  » » » » 5 months ago, # ^ |   +45 why is this being downvoted lmao cf community has no humour
•  » » » » » 5 months ago, # ^ | ← Rev. 5 →   -33 :(
•  » » » » 5 months ago, # ^ |   +19 This is really long, any summary?
•  » » » » 5 months ago, # ^ |   +8 Sauce?
•  » » » » » 5 months ago, # ^ |   +27 The divine message was revealed to my unworthy mortal ears by the lord Sparky_Master_WCH1226.
•  » » » » » » 5 months ago, # ^ |   0 how is sparky master related to rotavirus
•  » » » » » » » 5 months ago, # ^ |   0 They are married couple.
•  » » » » » » » 5 months ago, # ^ |   +24 She is the living, breathing, coding maiden I asked out on a date, when the desire for an anime waifu became too tempting.
•  » » » » » » 5 months ago, # ^ |   0 nono I was asking sauce for the anime pic.
•  » » » 5 months ago, # ^ |   +6 ovo
•  » » » » 5 months ago, # ^ |   +3 drake?
•  » » 5 months ago, # ^ |   +23 You bought my participation with that anime picture XD
•  » » 5 months ago, # ^ |   +3 As a tester, I recommend reading all problems. GLHF!
 » 5 months ago, # | ← Rev. 2 →   -14 I think this is a good time.
 » 5 months ago, # | ← Rev. 2 →   +24 hoping for easy A this time so more people can participate otherwise they will just leave :|
 » 5 months ago, # |   +131 As the gray tester, I guarantee that taking last place in this round will result in negative delta.
•  » » 5 months ago, # ^ |   +2 Good luck in your achievement!!!
•  » » 5 months ago, # ^ |   +7 How did you get negative rating???
•  » » » 5 months ago, # ^ |   +82 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)
•  » » 5 months ago, # ^ |   +2 And the first place will lead to a very positive delta.
•  » » 5 months ago, # ^ |   0 damn you're right
 » 5 months ago, # |   +2 Why there's no cyan testing?
•  » » 5 months ago, # ^ |   +9 Good question. Maybe this round is a BIT difficult.
 » 5 months ago, # |   +29 As a (former) purple tester, I secured last place in testing easily. Anyway, good luck in the round!
•  » » 5 months ago, # ^ |   -12 How many did you solve?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +67 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
•  » » » 5 months ago, # ^ |   +16 Maybe he was just pretending to be weak.
•  » » » » 5 months ago, # ^ |   +18 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
•  » » » 5 months ago, # ^ |   +14 Actually I tested this round last year when having lunch:P
•  » » 5 months ago, # ^ |   0 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).
•  » » » 5 months ago, # ^ |   +8 I advise u to stop fAKing and wear girls’ clothesxD
•  » » » » 5 months ago, # ^ |   0 That is not possible! You should be my girlfriend!
•  » » » » » 4 weeks ago, # ^ |   +13 No, she should be mine :)
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 4 →   -8 错了错了 别骂了
•  » » » » 5 months ago, # ^ |   0 No matter what gossip I say. Wishing everyone a good ranking!
•  » » » » 5 months ago, # ^ | ← Rev. 4 →   0 um, but Lyrically is really cute... at least his voice cutely XD.
 » 5 months ago, # |   +65 As a tester, this round might be Chinese-friendly.
•  » » 5 months ago, # ^ |   0 What does that mean? Lot of people say there is too much math in chinese rounds.
•  » » » 5 months ago, # ^ |   +38 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 :)
•  » » » » 5 months ago, # ^ |   0 Yeah, that's true. More contests at this time please!!
•  » » » » 5 months ago, # ^ |   0 In fact, maybe a Chinese middle school student won't have enough time to the contest.
•  » » » » » 5 months ago, # ^ |   0 Kely!!!
•  » » » 5 months ago, # ^ |   +8 Don't forget ds.
•  » » » 5 months ago, # ^ |   0 maybe have some well-know algorithm or trick in China?
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 So Div.1 D's solution is very similar to NOIP2022 T4?
 » 5 months ago, # |   +23 gl hf
 » 5 months ago, # |   +8 Cyan's : Are we a joke to you?
•  » » 5 months ago, # ^ |   +5 Yes
 » 5 months ago, # |   +8 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?
•  » » 5 months ago, # ^ |   +31 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
 » 5 months ago, # |   0 orz
•  » » 5 months ago, # ^ |   0 orz
 » 5 months ago, # |   +3 unfit my schedule but still appreciate
 » 5 months ago, # |   0 it good time for chinese
 » 5 months ago, # |   +34 I really like a sentence from chinese participants:啊？()
•  » » 5 months ago, # ^ |   0 啊？
•  » » 2 months ago, # ^ |   0 you are doing meme export xd.
•  » » 7 weeks ago, # ^ |   0 啊？
 » 5 months ago, # |   +5 Cute
 » 5 months ago, # |   0 What should I say.
•  » » 5 months ago, # ^ |   +1 HAIL KEK!
 » 5 months ago, # |   +1 RedLycoris Orz
 » 5 months ago, # |   +40 Hello, YuezhengLing and LuoTianYi!
 » 5 months ago, # |   +41 wow！Nan-bei！！！！（我超 南北组！！！！）
•  » » 5 months ago, # ^ |   +13 awa
 » 5 months ago, # |   0 How can I become a tester for Div2 / Div3 contests?
 » 5 months ago, # |   0 Lot of people say there is too much math in chinese rounds. Is this true?
•  » » 5 months ago, # ^ |   +1 (And many DS.)But these are all stereotypes. I think there will be many interesting problems, too. Hope to enjoy the contest!
•  » » » 5 months ago, # ^ |   0 Okay thankx!
•  » » » 5 months ago, # ^ |   0 Hoshino kawaiiiiiiiiiii
 » 5 months ago, # | ← Rev. 3 →   +51 wow, LuoTianyi and YuezhengLing! what year is it today 我超！南北组！今夕是何年
•  » » 5 months ago, # ^ |   +13 Seems a lot of OIers like vocaloid (including me).But I don't really like the style of the illustrations...
•  » » 5 months ago, # ^ |   +5 awa
 » 5 months ago, # |   0 Yet another Chinese round. Time to lose ratings.
 » 5 months ago, # |   -32 From the time to the theme,it's not only round by Chinese but also round for Chinese.
•  » » 5 months ago, # ^ |   +15 I hope its not in Chinese.
 » 5 months ago, # |   +26 Too much testers. Hoping for an amazing round.
 » 5 months ago, # |   +117 Damn, div 0?
 » 5 months ago, # |   0 Why am I here?
•  » » 5 months ago, # ^ |   +11 Just to suffer...
 » 5 months ago, # |   0 It's so gooooooood.I never imagined they would show up on CodeForces,and the time is very suitable for Chinese.
 » 5 months ago, # |   +3 Please continue this great time!And I love nanbei!
 » 5 months ago, # |   +9 Damn, div 0?
 » 5 months ago, # |   +17 As YuezhengLing, you gave LuoTianYi a dynamic tree.
 » 5 months ago, # |   0 %%%gezhiyuan %%%sanweitreap
 » 5 months ago, # |   +5 As a tester, i think this round is a good one.It is friendly to beginners.Good luck to all!
 » 5 months ago, # |   +19 You for participating in this round.You is very magical.
 » 5 months ago, # |   +8 1 up rate for cuteness ._.
 » 5 months ago, # |   +5 Cutest invitation/announcement I have ever seen... <3
 » 5 months ago, # |   0 Anime, good.
 » 5 months ago, # |   +1 Announcement so cute, I can't miss this contest at all.
 » 5 months ago, # |   +1 Return to orange again,hope not dropping this time...
 » 5 months ago, # |   +2 Extremely excited for this contest. Hoping for a positive delta
 » 5 months ago, # |   +30 As a tester, this round has beautiful problems, really loved solving them. Good luck!
 » 5 months ago, # |   0 Points distribution?
 » 5 months ago, # |   +1 W*c, Vocaloid!
 » 5 months ago, # |   +3 Wish rp++
 » 5 months ago, # |   +19 As a tester, I tested.
•  » » 5 months ago, # ^ |   +14 The moon shines, thank the moon.
•  » » 5 months ago, # ^ |   +8 The moon shines, thank the moon. YueLiangHaoShan, BaiXieYueLiang.
 » 5 months ago, # | ← Rev. 2 →   0 This will be a great game！
 » 5 months ago, # |   +11 no way,is it 2023 ? last time i saw them was almost 5 years ago, rating++pls （今夕是何年）
 » 5 months ago, # |   0 wawawawawa!!!!!so cute!!!!
•  » » 5 months ago, # ^ |   +1 wa on pretest 2
 » 5 months ago, # |   0 Why unusual start time?
•  » » 5 months ago, # ^ |   +3 Maybe it's Chinese Round.
•  » » » 5 months ago, # ^ |   0 So the Chinese Round is only for Chinese?
•  » » » » 5 months ago, # ^ |   +5 No,it means it's provided by Chinese.
 » 5 months ago, # |   +5 Friendly time for participants.
 » 5 months ago, # |   0 orz%%%%
 » 5 months ago, # |   +1 Can I become CM today?
•  » » 5 months ago, # ^ |   0 D1 < C. Solve yeah you will become CM. just solve A, B, D1, C.
•  » » » 5 months ago, # ^ |   0 Also, remember to drink enough water during the contest. It relaxes the mind and makes you hydrated sir.
•  » » » » 5 months ago, # ^ |   0 I will try not to go pupil.
•  » » » » » 5 months ago, # ^ |   0 Thnks man, i wish you become expert too.
•  » » 5 months ago, # ^ |   0 Really hard to get +137
•  » » » 5 months ago, # ^ |   0 Yeahh i know :(
•  » » » » 5 months ago, # ^ |   0 It's possible if you solve 4 problems quickly in div2,I think.
 » 5 months ago, # |   0 Chinese round has math problems. Hope to solve at least one of them.
•  » » 5 months ago, # ^ |   0 Do not spam
 » 5 months ago, # |   0 Me saying for the 20th time, "Hope to reach cyan in this round"
•  » » 5 months ago, # ^ |   0 Me too! I just came down from cyan.
•  » » » 5 months ago, # ^ |   0 Challenge accepted. See you in standings.
 » 5 months ago, # |   +5 i think that will be a great round.
 » 5 months ago, # |   +17 as a tester I'm not, but it's a good trick to raise a contribution ( :
 » 5 months ago, # |   0 Upvote me to have +ve delta
•  » » 5 months ago, # ^ |   +3 -_-
 » 5 months ago, # |   0 Let's try to do great
 » 5 months ago, # |   0 All the best everyone.
 » 5 months ago, # |   +28 orz
•  » » 5 months ago, # ^ |   +22 orz
•  » » 5 months ago, # ^ |   +10 orz
•  » » 5 months ago, # ^ |   +3 orz
 » 5 months ago, # |   +5 My first Div 1 round. Hope for amazing problems)
 » 5 months ago, # |   0 Wow! Lyrically! btw gl!
 » 5 months ago, # |   0 Good luck!
 » 5 months ago, # |   0 I won't lose I won't lose I won't lose!!!!!!!!
 » 5 months ago, # |   +33 My copy of the picture in the announcement
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 But it might be fit for Chinese oiers
•  » » » 5 months ago, # ^ |   0 The round started at 20:05(UTC+8), That's great. But today is Monday. Because of that, I can't participate this contest.
 » 5 months ago, # |   0 Cool ！！！qpzc qwq
 » 5 months ago, # |   0 can someone explain b shortly
•  » » 5 months ago, # ^ |   0 i mean how we add in table i didnt get the condition
•  » » » 5 months ago, # ^ |   0 I didn’t participate but I think that you get n*m numbers and you need to fill the table with them. Quick solution I think might work: Find minimum and maximum of all numbers, this pair will give you the highest score, which means that you need to put this pair in such a way that it occurs in the biggest possible number of subtables.
 » 5 months ago, # |   -8 wtf, div1B have mathematical expectation.
•  » » 5 months ago, # ^ |   0 Same buddy, I'm too weak in probability :(
•  » » 5 months ago, # ^ | ← Rev. 5 →   0 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.
•  » » » 5 months ago, # ^ |   0 i know it. I solved this problem. But B2 is unreal for me
•  » » » » 5 months ago, # ^ |   0 I am not sure why are you surprised/complaining then.
•  » » » 5 months ago, # ^ |   +3 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.
 » 5 months ago, # |   0 Speedforces A,B
 » 5 months ago, # | ← Rev. 3 →   +42 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
 » 5 months ago, # |   +1 Thank you for this contest. (Praying that I don't fail systests)
 » 5 months ago, # |   +11 Why does div2C have such a weird test case? 6 6 -1 1 4 5 -1 4 WTF!!!
•  » » 5 months ago, # ^ |   0 What did you find weird in this?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -26 Some Chinese people believe that 114514 is a "smelly" number.
•  » » » » 5 months ago, # ^ |   -13 Please stop downvoting this comment anymore!!!
•  » » 5 months ago, # ^ |   +16 It is a common phenomenon to use memes in test cases, in fact
 » 5 months ago, # |   0 How to optimize in D1B2
•  » » 5 months ago, # ^ | ← Rev. 2 →   -8 Edit:nevermind, i was answering for div2 b
•  » » » 5 months ago, # ^ |   +4 WTF ?
•  » » » » 5 months ago, # ^ |   +4 ah i was answering for d2b. Sorry
 » 5 months ago, # |   +17 Wow, today I experienced the feeling of submitting a solution last minute. Nothing can beat this feeling.
 » 5 months ago, # |   +8 Wrong Answer on Pretest 6.
 » 5 months ago, # |   +6 Amazing problems D1,D2 (B1, B2). Thanks a lot :)
•  » » 5 months ago, # ^ |   0 I solved D1, for odd n answer is 1, how to solve D2,i know what to do but can't optimize it.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 5 months ago, # |   +13 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: $\sum_{0 \le b_i \le min(a_i, \frac{k}{2}), \sum{b_i}=k} {k \choose b_1, \dots, b_p}$How to calculate it?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 5 months ago, # ^ |   +16 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 $> \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.
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   +5 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.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -14 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 int total = 0; for(int i = 0 ; i < a.size() ; i++) { for(int j = i+1 ; j < a.size() ; j++) { for(int k = j+1, j < a.size() ; k++) { total += (a[i] * a[j] * a[k] % MOD); total %= MOD; } } } Converting these three for loops into LINEAR TIME was definitely challenging for me, I don't know about others.
•  » » » » 5 months ago, # ^ |   +2 For any odd K the answer is always 1
•  » » » » » 5 months ago, # ^ |   0 LOL vgtcross, I sense sarcasm in that comment. And no, for k = 1 , it wasn't as difficult as regular D problem xD
•  » » » » » » 5 months ago, # ^ |   0 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
•  » » » » » » » 5 months ago, # ^ | ← Rev. 5 →   -7 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.
•  » » » » 5 months ago, # ^ |   0 for k = 3 Spoilercout << "1\n";
•  » » » » » 5 months ago, # ^ |   0 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. int total = 0; for(int i = 0 ; i < a.size() ; i++) { for(int j = i+1 ; j < a.size() ; j++) { for(int k = j+1, j < a.size() ; k++) { total += (a[i] * a[j] * a[k] % MOD); total %= MOD; } } } 
•  » » » » » 5 months ago, # ^ |   +10 for $k \equiv 1 \pmod 2$ : Spoilercout<<"1\n";
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 Actually how would one create a BIT to do those in O(N log N) time?
 » 5 months ago, # |   +1 I don't know, whether div2.C was tricky or i am dumb :)
 » 5 months ago, # |   0 SpecialCaseForces
 » 5 months ago, # |   0 nice contest, I would have been first to solve A if I realised the reason my program is outputting 0s is because I am using the input file from another problem lol
 » 5 months ago, # |   0 I like the tasks, although I'm not able to solve B2/C even after thinking a lot
 » 5 months ago, # |   0 This contest will be remembered. salute those setters
 » 5 months ago, # |   +2 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)
•  » » 5 months ago, # ^ |   +3 It is
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   +29 How to solve d1C? It's the hardest d1C I've seen in real contest.
•  » » 5 months ago, # ^ |   -8 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
•  » » » 5 months ago, # ^ |   +5 No this is wrong, consider this: 1 2 1 3 3 4 3 5 5 6 5 7 7 8 7 9 ... 
•  » » » » 5 months ago, # ^ |   +8 Ahh I see.. Height can still be linear :/
•  » » 5 months ago, # ^ |   0 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 uthen 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.
•  » » 5 months ago, # ^ |   +8 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.
 » 5 months ago, # |   +42 Even I got $\Delta \approx -70$, B2 is an overwhelming problem. This time I was completely defeated. Thank you for good contest!
 » 5 months ago, # |   0 Nice contest! I solved both A and B, and had an idea for C. However, for C, I ended up not fully understanding the problem correctly and wasn't able to fix my solution after I realized the mistake. I think that I was somewhat slow on A and B, but I guess I learned to be a little more relaxed rather than stressed from the recent Divison 4 contest. I should probably try and find a balance between slow and fast, any tips?Also, which delta tells me the rating that I will gain -- the sole delta or the delta with the words "just now"? I need to know whether I made pupil or not! :concerned: Thanks!
 » 5 months ago, # |   -7 I might've finally reached expert!
•  » » 5 months ago, # ^ |   +1 After this round, I'm still a pupil.
 » 5 months ago, # |   0 I am expecting to become a Master excitedly!
 » 5 months ago, # |   0 Can anyone Please explain the solution for Div 2 C / Div 1 A . . .
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +1 We have 3 cases to consider: start at seat 1, then our answer will be number of option 2s + number of distinct option 3s start at seat m, then our answer will be number of option 1s + number of distinct option 3s. We start at a seat x that is not 1 or m. In this case, we must fill up the "gaps" to the left and right of the seat x that we start at. 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 guysNow 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 2sThis can be done by sorting our array of middle values and doing some index checking.https://mirror.codeforces.com/contest/1825/submission/205103435
 » 5 months ago, # |   0 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
 » 5 months ago, # |   0 Brainless D with only 7s TLWhat a trash experience
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 I feel your pain Spoiler#pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC diagnostic error "-std=c++11" #pragma GCC target("avx") #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") Bro tried everything 😭
 » 5 months ago, # |   +4 oof.
 » 5 months ago, # |   0 miss the round because of the odd start time T_T
•  » » 5 months ago, # ^ |   0 How lucky you are.
•  » » » 5 months ago, # ^ |   0 sounds like a very terrible round?I will take a vp later
 » 5 months ago, # |   -33 Div2 D testcase == 'heng heng heng aaaaaaaaaa'^ ^
 » 5 months ago, # |   +1 Nice Problems
 » 5 months ago, # |   +8 Chinese culture export
 » 5 months ago, # |   0 Strong pretests, but the successful hacking rate out of all valid attempts is 100%! Fascinating.
 » 5 months ago, # |   +3 Nice Contest, especially on div2 d1, d2! Btw, I was so unlucky to get in top 100 because of modular mistake on d2 :(
 » 5 months ago, # |   +4 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?
 » 5 months ago, # |   0 GOOD problems, STUPID me, QAQ
 » 5 months ago, # |   0 I managed to solve D1 but i dont have any idea how to solve D2.How to solve D2?
•  » » 5 months ago, # ^ |   +12 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:)
 » 5 months ago, # |   0 How to solve div2 B problem...
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 months ago, # ^ |   0 Thankyou... Got solved
•  » » » 5 months ago, # ^ |   0 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 ?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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)$
•  » » » » » 5 months ago, # ^ |   0 cool , thanks tho .
•  » » » » 5 months ago, # ^ |   0 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
•  » » » » » 5 months ago, # ^ |   0 i just looked up your code it was crisp and smooth .... that was great implementation i did a lengthy straight forward code .
 » 5 months ago, # |   +3 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 :(
 » 5 months ago, # |   0 I hope I can become specialist
 » 5 months ago, # |   +5 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?
 » 5 months ago, # |   +3 round approved
 » 5 months ago, # |   0 How is it possible that the guy from the first place on div2 did 3 tasks in the 9-th minute?
•  » » 5 months ago, # ^ |   +1 I don't think that this is possible too.
•  » » 5 months ago, # ^ |   +1 it seems to me that they know all the answers in advance and immediately send[maybe they can be cheaters]
•  » » » 5 months ago, # ^ |   +1 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.
•  » » 5 months ago, # ^ |   +17 Problem B,C,D have completely different coding style/format. Hex_10EFFB_ is definitely suspicious.
•  » » » 5 months ago, # ^ |   -40 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！
•  » » 5 months ago, # ^ |   0 He solved A in 2 minutes, which means it took him only 7 minutes to solve B, C, D1 Spoiler
 » 5 months ago, # | ← Rev. 2 →   0 Good round.
 » 5 months ago, # |   0 cool
 » 5 months ago, # |   0 Finally i became cyan again,very good round!
 » 5 months ago, # |   0 After a 10 min submission I thought i will not take more than an hour to solve B! Later on the only thing i did with my paper written few cases and try to figure out any pattern and contest is over. :-(
 » 5 months ago, # | ← Rev. 3 →   -15 .
 » 5 months ago, # |   0 Can Someone explain d2C ?
 » 5 months ago, # |   -11 gooooood contestttttttt___akfla
 » 5 months ago, # |   0 awaQwQ
 » 5 months ago, # |   0 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!?
•  » » 5 months ago, # ^ |   +3 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.)
•  » » » 5 months ago, # ^ |   0 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?
•  » » » » 5 months ago, # ^ |   0 immediately, obviously yes, but not in the long run.
 » 5 months ago, # |   +36 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!
•  » » 5 months ago, # ^ |   +56 I agree with you. And your English is GREAT!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -37 .
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   +18 Why
•  » » 5 months ago, # ^ |   +16 as a person who lost rating due to div1B, i think its one of the best problems i have seen.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +22 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.
•  » » » » 5 months ago, # ^ |   -25 "I think it is a classic problem."I would believe you if you didnt create an alt for shitposting
•  » » 5 months ago, # ^ |   -23 Stop showing off your pitiful level, it will only make you look like a loser.
•  » » » 5 months ago, # ^ |   +15 I'm not showing, but criticizing the competition.
 » 5 months ago, # |   +5 I love not being able to open codeforces in public without looking like a weaboo
 » 5 months ago, # |   0 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?
 » 5 months ago, # |   +2 What's the issue with CF. Its opening on phone but not on pc.
 » 5 months ago, # | ← Rev. 2 →   -6 All problems ..?
 » 5 months ago, # | ← Rev. 2 →   +5 I was reminiscing about Luo Tianyi's Vocaloid while solving the contest.
 » 5 months ago, # |   +13 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?
•  » » 5 months ago, # ^ |   0 i suppose his nickname must be like: assembly fun fun fun
 » 5 months ago, # |   0 ERCIYUAN ZHENXIATOU
 » 5 months ago, # |   0 I was not aware that testing code from other account before submitting it from another account is illegal. I did this in my contest. In my view its not illegal because i am not cheating. Its just little bit greed of 50 points which i can loose if i submitted directly. But still if codeforces believes it illegal i will not practice this thing anymore but i request to @codeforces please don't penalize me for this mistake this time later i will never repeat it again. I hope codeforces will respond and do proper justice because i have not cheated or copied any one else's code its my own logic and my own way of solving code. Codeforces Round 872 (Div. 2)
 » 4 months ago, # |   0 qwq
 » 4 months ago, # |   0 May be I will have rating on summer holiday
 » 4 months ago, # |   0 Problem A,B,C was Nice, But unfortunately I missed the contest.