### RedLycoris's blog

By RedLycoris, history, 6 weeks ago,

Hello Codeforces! （你好，代码部队）

We are glad to invite you to participate in Codeforces Round 872 (Div. 1) and Codeforces Round 872 (Div. 2) on May/08/2023 15:05 (Moscow time). 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:

• +790

 » 4 weeks ago, # |   +85 awa
•  » » 4 weeks ago, # ^ |   +31 QwQ
•  » » » 4 weeks 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!!!
•  » » » » 4 weeks ago, # ^ |   +36 then my IQ would have have been decreased by :|
•  » » » » » 4 weeks ago, # ^ |   0 same feeling i have gotten...
•  » » » » 4 weeks ago, # ^ |   +98 this is high-quality shitpost, so it got upvote from me
•  » » » » 4 weeks ago, # ^ |   +15
•  » » » » 4 weeks ago, # ^ |   +45 why is this being downvoted lmao cf community has no humour
•  » » » » » 4 weeks ago, # ^ | ← Rev. 5 →   -33 :(
•  » » » » 4 weeks ago, # ^ |   +19 This is really long, any summary?
•  » » » » 4 weeks ago, # ^ |   +8 Sauce?
•  » » » » » 4 weeks ago, # ^ |   +27 The divine message was revealed to my unworthy mortal ears by the lord Sparky_Master_WCH1226.
•  » » » » » » 4 weeks ago, # ^ |   0 how is sparky master related to rotavirus
•  » » » » » » » 4 weeks ago, # ^ |   0 They are married couple.
•  » » » » » » » 4 weeks 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.
•  » » » » » » 4 weeks ago, # ^ |   0 nono I was asking sauce for the anime pic.
•  » » » 4 weeks ago, # ^ |   +6 ovo
•  » » » » 4 weeks ago, # ^ |   +3 drake?
•  » » 4 weeks ago, # ^ |   +23 You bought my participation with that anime picture XD
•  » » 4 weeks ago, # ^ |   +3 As a tester, I recommend reading all problems. GLHF!
 » 4 weeks ago, # | ← Rev. 2 →   -14 I think this is a good time.
 » 4 weeks ago, # | ← Rev. 2 →   +24 hoping for easy A this time so more people can participate otherwise they will just leave :|
 » 4 weeks ago, # |   +131 As the gray tester, I guarantee that taking last place in this round will result in negative delta.
•  » » 4 weeks ago, # ^ |   +2 Good luck in your achievement!!!
•  » » 4 weeks ago, # ^ |   +7 How did you get negative rating???
•  » » » 4 weeks 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)
•  » » 4 weeks ago, # ^ |   +2 And the first place will lead to a very positive delta.
•  » » 4 weeks ago, # ^ |   0 damn you're right
 » 4 weeks ago, # |   +2 Why there's no cyan testing?
•  » » 4 weeks ago, # ^ |   +9 Good question. Maybe this round is a BIT difficult.
 » 4 weeks ago, # |   +29 As a (former) purple tester, I secured last place in testing easily. Anyway, good luck in the round!
•  » » 4 weeks ago, # ^ |   -12 How many did you solve?
•  » » 4 weeks 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
•  » » » 4 weeks ago, # ^ |   +16 Maybe he was just pretending to be weak.
•  » » » » 4 weeks 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
•  » » » 4 weeks ago, # ^ |   +14 Actually I tested this round last year when having lunch:P
•  » » 4 weeks 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).
•  » » » 4 weeks ago, # ^ |   +8 I advise u to stop fAKing and wear girls’ clothesxD
•  » » » » 4 weeks ago, # ^ |   0 That is not possible! You should be my girlfriend!
•  » » » » 4 weeks ago, # ^ |   0 No matter what gossip I say. Wishing everyone a good ranking!
•  » » » » 4 weeks ago, # ^ |   0 um, but Lyrically is really cute... at least his voice cutely XD.
 » 4 weeks ago, # |   +65 As a tester, this round might be Chinese-friendly.
•  » » 4 weeks ago, # ^ |   0 What does that mean? Lot of people say there is too much math in chinese rounds.
•  » » » 4 weeks 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 :)
•  » » » » 4 weeks ago, # ^ |   0 Yeah, that's true. More contests at this time please!!
•  » » » » 4 weeks ago, # ^ |   0 In fact, maybe a Chinese middle school student won't have enough time to the contest.
•  » » » » » 4 weeks ago, # ^ |   0 Kely!!!
•  » » » 4 weeks ago, # ^ |   +8 Don't forget ds.
•  » » » 4 weeks ago, # ^ |   0 maybe have some well-know algorithm or trick in China?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 So Div.1 D's solution is very similar to NOIP2022 T4?
 » 4 weeks ago, # |   +23 gl hf
 » 4 weeks ago, # |   +8 Cyan's : Are we a joke to you?
•  » » 4 weeks ago, # ^ |   +5 Yes
 » 4 weeks 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?
•  » » 4 weeks 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
 » 4 weeks ago, # |   0 orz
•  » » 4 weeks ago, # ^ |   0 orz
 » 4 weeks ago, # |   +3 unfit my schedule but still appreciate
 » 4 weeks ago, # |   0 it good time for chinese
 » 4 weeks ago, # |   +34 I really like a sentence from chinese participants:啊？()
•  » » 4 weeks ago, # ^ |   0 啊？
 » 4 weeks ago, # |   +5 Cute
 » 4 weeks ago, # |   0 What should I say.
•  » » 4 weeks ago, # ^ |   +1 HAIL KEK!
 » 4 weeks ago, # |   +1 RedLycoris Orz
 » 4 weeks ago, # |   +40 Hello, YuezhengLing and LuoTianYi!
 » 4 weeks ago, # |   +41 wow！Nan-bei！！！！（我超 南北组！！！！）
•  » » 4 weeks ago, # ^ |   +13 awa
 » 4 weeks ago, # |   0 How can I become a tester for Div2 / Div3 contests?
 » 4 weeks ago, # |   0 Lot of people say there is too much math in chinese rounds. Is this true?
•  » » 4 weeks ago, # ^ |   +1 (And many DS.)But these are all stereotypes. I think there will be many interesting problems, too. Hope to enjoy the contest!
•  » » » 4 weeks ago, # ^ |   0 Okay thankx!
•  » » » 4 weeks ago, # ^ |   0 Hoshino kawaiiiiiiiiiii
 » 4 weeks ago, # | ← Rev. 3 →   +51 wow, LuoTianyi and YuezhengLing! what year is it today 我超！南北组！今夕是何年
•  » » 4 weeks ago, # ^ |   +13 Seems a lot of OIers like vocaloid (including me).But I don't really like the style of the illustrations...
•  » » 4 weeks ago, # ^ |   +5 awa
 » 4 weeks ago, # |   0 Yet another Chinese round. Time to lose ratings.
 » 4 weeks ago, # |   -32 From the time to the theme,it's not only round by Chinese but also round for Chinese.
•  » » 4 weeks ago, # ^ |   +15 I hope its not in Chinese.
 » 4 weeks ago, # |   +26 Too much testers. Hoping for an amazing round.
 » 4 weeks ago, # |   +117 Damn, div 0?
 » 4 weeks ago, # |   0 Why am I here?
•  » » 4 weeks ago, # ^ |   +11 Just to suffer...
 » 4 weeks ago, # |   0 It's so gooooooood.I never imagined they would show up on CodeForces,and the time is very suitable for Chinese.
 » 4 weeks ago, # |   +3 Please continue this great time!And I love nanbei!
 » 4 weeks ago, # |   +9 Damn, div 0?
 » 4 weeks ago, # |   +17 As YuezhengLing, you gave LuoTianYi a dynamic tree.
 » 4 weeks ago, # |   0 %%%gezhiyuan %%%sanweitreap
 » 4 weeks ago, # |   +5 As a tester, i think this round is a good one.It is friendly to beginners.Good luck to all!
 » 4 weeks ago, # |   +19 You for participating in this round.You is very magical.
 » 4 weeks ago, # |   +8 1 up rate for cuteness ._.
 » 4 weeks ago, # |   +5 Cutest invitation/announcement I have ever seen... <3
 » 4 weeks ago, # |   0 Anime, good.
 » 4 weeks ago, # |   +1 Announcement so cute, I can't miss this contest at all.
 » 4 weeks ago, # |   +1 Return to orange again,hope not dropping this time...
 » 4 weeks ago, # |   +2 Extremely excited for this contest. Hoping for a positive delta
 » 4 weeks ago, # |   +30 As a tester, this round has beautiful problems, really loved solving them. Good luck!
 » 4 weeks ago, # |   0 Points distribution?
 » 4 weeks ago, # |   +1 W*c, Vocaloid!
 » 4 weeks ago, # |   +3 Wish rp++
 » 4 weeks ago, # |   +19 As a tester, I tested.
•  » » 4 weeks ago, # ^ |   +14 The moon shines, thank the moon.
•  » » 4 weeks ago, # ^ |   +8 The moon shines, thank the moon. YueLiangHaoShan, BaiXieYueLiang.
 » 4 weeks ago, # | ← Rev. 2 →   0 This will be a great game！
 » 4 weeks ago, # |   +11 no way,is it 2023 ? last time i saw them was almost 5 years ago, rating++pls （今夕是何年）
 » 4 weeks ago, # |   0 wawawawawa!!!!!so cute!!!!
•  » » 4 weeks ago, # ^ |   +1 wa on pretest 2
 » 4 weeks ago, # |   0 Why unusual start time?
•  » » 4 weeks ago, # ^ |   +3 Maybe it's Chinese Round.
•  » » » 4 weeks ago, # ^ |   0 So the Chinese Round is only for Chinese?
•  » » » » 4 weeks ago, # ^ |   +5 No,it means it's provided by Chinese.
 » 4 weeks ago, # |   +5 Friendly time for participants.
 » 4 weeks ago, # |   0 orz%%%%
 » 4 weeks ago, # |   +1 Can I become CM today?
•  » » 4 weeks ago, # ^ |   0 D1 < C. Solve yeah you will become CM. just solve A, B, D1, C.
•  » » » 4 weeks ago, # ^ |   0 Also, remember to drink enough water during the contest. It relaxes the mind and makes you hydrated sir.
•  » » » » 4 weeks ago, # ^ |   0 I will try not to go pupil.
•  » » » » » 4 weeks ago, # ^ |   0 Thnks man, i wish you become expert too.
•  » » 4 weeks ago, # ^ |   0 Really hard to get +137
•  » » » 4 weeks ago, # ^ |   0 Yeahh i know :(
•  » » » » 4 weeks ago, # ^ |   0 It's possible if you solve 4 problems quickly in div2,I think.
 » 4 weeks ago, # |   0 Chinese round has math problems. Hope to solve at least one of them.
•  » » 4 weeks ago, # ^ |   0 Do not spam
 » 4 weeks ago, # |   0 Me saying for the 20th time, "Hope to reach cyan in this round"
•  » » 4 weeks ago, # ^ |   0 Me too! I just came down from cyan.
•  » » » 4 weeks ago, # ^ |   0 Challenge accepted. See you in standings.
 » 4 weeks ago, # |   +5 i think that will be a great round.
 » 4 weeks ago, # |   +17 as a tester I'm not, but it's a good trick to raise a contribution ( :
 » 4 weeks ago, # |   0 Upvote me to have +ve delta
•  » » 4 weeks ago, # ^ |   +3 -_-
 » 4 weeks ago, # |   0 Let's try to do great
 » 4 weeks ago, # |   0 All the best everyone.
 » 4 weeks ago, # |   +28 orz
•  » » 4 weeks ago, # ^ |   +22 orz
•  » » 4 weeks ago, # ^ |   +10 orz
•  » » 4 weeks ago, # ^ |   +3 orz
 » 4 weeks ago, # |   +5 My first Div 1 round. Hope for amazing problems)
 » 4 weeks ago, # |   0 Wow! Lyrically! btw gl!
 » 4 weeks ago, # |   0 Good luck!
 » 4 weeks ago, # |   0 I won't lose I won't lose I won't lose!!!!!!!!
 » 4 weeks ago, # |   +33 My copy of the picture in the announcement
 » 4 weeks 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.
•  » » 4 weeks ago, # ^ |   0 But it might be fit for Chinese oiers
•  » » » 4 weeks 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.
 » 4 weeks ago, # |   0 Cool ！！！qpzc qwq
 » 4 weeks ago, # |   0 can someone explain b shortly
•  » » 4 weeks ago, # ^ |   0 i mean how we add in table i didnt get the condition
•  » » » 4 weeks 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.
 » 4 weeks ago, # |   -8 wtf, div1B have mathematical expectation.
•  » » 4 weeks ago, # ^ |   0 Same buddy, I'm too weak in probability :(
•  » » 4 weeks 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.
•  » » » 4 weeks ago, # ^ |   0 i know it. I solved this problem. But B2 is unreal for me
•  » » » » 4 weeks ago, # ^ |   0 I am not sure why are you surprised/complaining then.
•  » » » 4 weeks 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.
 » 4 weeks ago, # |   0 Speedforces A,B
 » 4 weeks 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
 » 4 weeks ago, # |   +1 Thank you for this contest. (Praying that I don't fail systests)
 » 4 weeks ago, # |   +11 Why does div2C have such a weird test case? 6 6 -1 1 4 5 -1 4 WTF!!!
•  » » 4 weeks ago, # ^ |   0 What did you find weird in this?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   -26 Some Chinese people believe that 114514 is a "smelly" number.
•  » » » » 4 weeks ago, # ^ |   -13 Please stop downvoting this comment anymore!!!
•  » » 4 weeks ago, # ^ |   +16 It is a common phenomenon to use memes in test cases, in fact
 » 4 weeks ago, # |   0 How to optimize in D1B2
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -8 Edit:nevermind, i was answering for div2 b
•  » » » 4 weeks ago, # ^ |   +4 WTF ?
•  » » » » 4 weeks ago, # ^ |   +4 ah i was answering for d2b. Sorry
 » 4 weeks ago, # |   +17 Wow, today I experienced the feeling of submitting a solution last minute. Nothing can beat this feeling.
 » 4 weeks ago, # |   +8 Wrong Answer on Pretest 6.
 » 4 weeks ago, # |   +6 Amazing problems D1,D2 (B1, B2). Thanks a lot :)
•  » » 4 weeks 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.
•  » » » 4 weeks 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.
 » 4 weeks 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?
•  » » 4 weeks 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.
•  » » 4 weeks 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.
 » 4 weeks 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.
•  » » 4 weeks 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.
•  » » » 4 weeks 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.
•  » » » » 4 weeks ago, # ^ |   +2 For any odd K the answer is always 1
•  » » » » » 4 weeks 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
•  » » » » » » 4 weeks 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
•  » » » » » » » 4 weeks 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.
•  » » » » 4 weeks ago, # ^ |   0 for k = 3 Spoilercout << "1\n";
•  » » » » » 4 weeks 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; } } } 
•  » » » » » 4 weeks ago, # ^ |   +10 for $k \equiv 1 \pmod 2$ : Spoilercout<<"1\n";
 » 4 weeks 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?
•  » » 4 weeks ago, # ^ |   0 Actually how would one create a BIT to do those in O(N log N) time?
 » 4 weeks ago, # |   +1 I don't know, whether div2.C was tricky or i am dumb :)
 » 4 weeks ago, # |   0 SpecialCaseForces
 » 4 weeks 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
 » 4 weeks ago, # |   0 I like the tasks, although I'm not able to solve B2/C even after thinking a lot
 » 4 weeks ago, # |   0 This contest will be remembered. salute those setters
 » 4 weeks 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)
•  » » 4 weeks ago, # ^ |   +3 It is
•  » » 4 weeks 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.
 » 4 weeks ago, # |   +29 How to solve d1C? It's the hardest d1C I've seen in real contest.
•  » » 4 weeks 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
•  » » » 4 weeks ago, # ^ |   +5 No this is wrong, consider this: 1 2 1 3 3 4 3 5 5 6 5 7 7 8 7 9 ... 
•  » » » » 4 weeks ago, # ^ |   +8 Ahh I see.. Height can still be linear :/
•  » » 4 weeks 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.
•  » » 4 weeks 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.
 » 4 weeks ago, # |   +42 Even I got $\Delta \approx -70$, B2 is an overwhelming problem. This time I was completely defeated. Thank you for good contest!
 » 4 weeks 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!
 » 4 weeks ago, # |   -7 I might've finally reached expert!
•  » » 4 weeks ago, # ^ |   +1 After this round, I'm still a pupil.
 » 4 weeks ago, # |   0 I am expecting to become a Master excitedly!
 » 4 weeks ago, # |   0 Can anyone Please explain the solution for Div 2 C / Div 1 A . . .
•  » » 4 weeks 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.
•  » » 4 weeks 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://codeforces.com/contest/1825/submission/205103435
 » 4 weeks 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
 » 4 weeks ago, # |   0 Brainless D with only 7s TLWhat a trash experience
•  » » 4 weeks 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 😭
 » 4 weeks ago, # |   +4 oof.
 » 4 weeks ago, # |   0 miss the round because of the odd start time T_T
•  » » 4 weeks ago, # ^ |   0 How lucky you are.
•  » » » 4 weeks ago, # ^ |   0 sounds like a very terrible round?I will take a vp later
 » 4 weeks ago, # |   -33 Div2 D testcase == 'heng heng heng aaaaaaaaaa'^ ^
 » 4 weeks ago, # |   +1 Nice Problems
 » 4 weeks ago, # |   +8 Chinese culture export
 » 4 weeks ago, # |   0 Strong pretests, but the successful hacking rate out of all valid attempts is 100%! Fascinating.
 » 4 weeks 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 :(
 » 4 weeks 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?
 » 4 weeks ago, # |   0 GOOD problems, STUPID me, QAQ
 » 4 weeks ago, # |   0 I managed to solve D1 but i dont have any idea how to solve D2.How to solve D2?
•  » » 4 weeks 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:)
 » 4 weeks ago, # |   0 How to solve div2 B problem...
•  » » 4 weeks 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
•  » » » 4 weeks ago, # ^ |   0 Thankyou... Got solved
•  » » » 4 weeks 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 ?
•  » » » » 4 weeks 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)$
•  » » » » » 4 weeks ago, # ^ |   0 cool , thanks tho .
•  » » » » 4 weeks 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
•  » » » » » 4 weeks ago, # ^ |   0 i just looked up your code it was crisp and smooth .... that was great implementation i did a lengthy straight forward code .
 » 4 weeks 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 :(
 » 4 weeks ago, # |   0 I hope I can become specialist
 » 4 weeks 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?
 » 4 weeks ago, # |   +3 round approved
 » 4 weeks ago, # |   0 How is it possible that the guy from the first place on div2 did 3 tasks in the 9-th minute?
•  » » 4 weeks ago, # ^ |   +1 I don't think that this is possible too.
•  » » 4 weeks ago, # ^ |   +1 it seems to me that they know all the answers in advance and immediately send[maybe they can be cheaters]
•  » » » 4 weeks 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.
•  » » 4 weeks ago, # ^ |   +17 Problem B,C,D have completely different coding style/format. Hex_10EFFB_ is definitely suspicious.
•  » » » 4 weeks 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！
•  » » 4 weeks ago, # ^ |   0 He solved A in 2 minutes, which means it took him only 7 minutes to solve B, C, D1 Spoiler
 » 4 weeks ago, # | ← Rev. 2 →   0 Good round.
 » 4 weeks ago, # |   0 cool
 » 4 weeks ago, # |   0 Finally i became cyan again,very good round!
 » 4 weeks 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. :-(
 » 4 weeks ago, # | ← Rev. 3 →   -15 .
 » 4 weeks ago, # |   0 Can Someone explain d2C ?
 » 4 weeks ago, # |   -11 gooooood contestttttttt___akfla
 » 4 weeks ago, # |   0 awaQwQ
 » 4 weeks 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!?
•  » » 4 weeks 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.)
•  » » » 4 weeks 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?
•  » » » » 4 weeks ago, # ^ |   0 immediately, obviously yes, but not in the long run.
 » 4 weeks 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!
•  » » 4 weeks ago, # ^ |   +56 I agree with you. And your English is GREAT!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -37 .
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +18 Why
•  » » 4 weeks ago, # ^ |   +16 as a person who lost rating due to div1B, i think its one of the best problems i have seen.
•  » » » 4 weeks 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.
•  » » » » 4 weeks ago, # ^ |   -25 "I think it is a classic problem."I would believe you if you didnt create an alt for shitposting
•  » » 4 weeks ago, # ^ |   -23 Stop showing off your pitiful level, it will only make you look like a loser.
•  » » » 4 weeks ago, # ^ |   +15 I'm not showing, but criticizing the competition.
 » 4 weeks ago, # |   +5 I love not being able to open codeforces in public without looking like a weaboo
 » 4 weeks 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?
 » 4 weeks ago, # |   +2 What's the issue with CF. Its opening on phone but not on pc.
 » 4 weeks ago, # | ← Rev. 2 →   -6 All problems ..?
 » 4 weeks ago, # | ← Rev. 2 →   +5 I was reminiscing about Luo Tianyi's Vocaloid while solving the contest.
 » 4 weeks 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?
•  » » 4 weeks ago, # ^ |   0 i suppose his nickname must be like: assembly fun fun fun
 » 4 weeks ago, # |   0 ERCIYUAN ZHENXIATOU
 » 4 weeks 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)
 » 13 days ago, # |   0 qwq
 » 12 days ago, # |   0 May be I will have rating on summer holiday
 » 11 days ago, # |   0 Problem A,B,C was Nice, But unfortunately I missed the contest.