### feecIe6418's blog

By feecIe6418, 2 weeks ago,

Hello Codeforces!

On Jun/25/2022 17:35 (Moscow time) we will hold Codeforces Global Round 21.

It is the third round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2022:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2022 supported the global rounds initiative!

All problems except one are authored and prepared by me. The other problem is authored by gyh20.

We would also like to thank the following people:

Round information:

• duration: 2 hours and 15 minutes
• number of problems: 8
• score distribution: 500-1000-1500-2000-2000-2500-3250-4000

We are looking forward to your participation!

Upd Editorial https://codeforces.com/blog/entry/103479

Upd Winners!

Announcement of Codeforces Global Round 21

• +757

 » 2 weeks ago, # |   -13 Only 8 testers? Interesting.
•  » » 2 weeks ago, # ^ |   +15 I see no difference.
•  » » 11 days ago, # ^ |   +18 :(
 » 2 weeks ago, # |   +268 As a tester and an author of one problem, feecIe6418 orz.
•  » » 2 weeks ago, # ^ |   0 gyh20 orz.
•  » » 12 days ago, # ^ |   -42 orzorzorz
•  » » 12 days ago, # ^ |   -30 gyh20 orz,feecIe6418 orz.
 » 2 weeks ago, # |   +311 As a tester, I can't wait to see PinkieRabbit's performance!
•  » » 13 days ago, # ^ |   +2 interesting
•  » » 12 days ago, # ^ | ← Rev. 2 →   -17 As a competitor, I can't wait to see PinkieRabbit's performance!
•  » » 12 days ago, # ^ |   +1 Its twice I have seen this message. What does this mean?
•  » » » 12 days ago, # ^ |   0 PinkieRabbit is a very popular up (just like youtuber ) in Chinese. Sometimes the writers or testers are his fans, then he will be invited.
•  » » » » 11 days ago, # ^ |   +16 So you don’t mind if I advertise my screencast here, right?https://www.bilibili.com/video/bv1yB4y1q71A (in Chinese)
 » 2 weeks ago, # |   +107 feecIe6418 orz.
 » 2 weeks ago, # |   0 waiting for a perfect contest!
 » 2 weeks ago, # |   +45 As a tester, good luck!
 » 2 weeks ago, # |   +122 As a human, miepu is a great bot!
 » 2 weeks ago, # |   +7 good
 » 13 days ago, # |   +4 I love global rounds so much ^_^
 » 13 days ago, # |   0 Coding is love ♡
 » 13 days ago, # | ← Rev. 2 →   +42 -
 » 13 days ago, # |   +63 2:15? The only upside is that my suffering will end sooner.
 » 13 days ago, # |   0 <3
 » 13 days ago, # |   0 :D
 » 13 days ago, # | ← Rev. 2 →   -55 [DELETED]
 » 13 days ago, # |   -124 Tell me this round isn't terrible, its nothing but a Div.1, (except 3 first problem being 800 rated)
•  » » 12 days ago, # ^ |   -70 I said TELL me, not DOWNVOTE
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 This is div2. Look at D. This complexity is usually D in div2. I apologize for grammatical errors, if there are any, English is not my native language.
•  » » » » 10 days ago, # ^ |   0 Some global rounds were not balanced to all users, thats why I told it would be bad. This round was good though.
 » 13 days ago, # |   -28 I am participating in such a round for the first time, but I already feel that it will be good, who thinks so?
 » 13 days ago, # | ← Rev. 2 →   -43 [DELETED]
 » 13 days ago, # | ← Rev. 2 →   +45 Hoping to become CM this round! UPDATE: Messed up :(
•  » » 12 days ago, # ^ |   -23 You will Sir!!
•  » » 12 days ago, # ^ |   +11 Practice CP until you become candidate master, then us a time machine to comeback to this contest and easily become CM. No need to thank me
 » 12 days ago, # |   +8 It's known that global rounds used to have problems ranging from Div. 3 to Div. 1. This seems to be the first global round after Div. 4 hosted regularly. So will there be some Div. 4 problems in it?Thanks.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +25 Well, there is no 250-point question in this round, so probably not. EDIT: Alright, this may have sounded very arrogant, so sorry about that. But, do people actually think that putting Div 4 problems in a global round would benefit them? It's gonna be a more speed-oriented, unbalanced problemset imo. If you think otherwise, then please comment your thought.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +45 It's known that global rounds used to have problems ranging from Div. 3 to Div. 1. This is the first time i hear anyone has said global rounds have div 3 problems. As far as I know its simply a merged div 1/div 2 round with problems ranging from d2A to d1F.If you consider d3D to be "ranging from div 3 to div 1" then I guess you can except a d4F to be inside.
 » 12 days ago, # |   -33 Hoping to turn expert this round!
 » 12 days ago, # | ← Rev. 2 →   +112 ()
 » 12 days ago, # |   +36 As someone having a discrete maths and linear algebra quiz, i am scared
•  » » 12 days ago, # ^ |   +42 Don't worry. Send adamant in your place.
 » 12 days ago, # |   -20 looking forward to become Specialist this round! The expectations are very high.
 » 12 days ago, # |   -31 When i see tourist is also participating , idk i feel more energetic and excited. Maybe the feeling that we both are competing together ..
 » 12 days ago, # |   -12 cqoier Orz
 » 12 days ago, # | ← Rev. 2 →   -13 orz miepu is so good
 » 12 days ago, # |   +27 Is this a Chinese Poisonous OI round again?
•  » » 12 days ago, # ^ |   +23 The fact that it was chosen to be a global round probably means it's very high quality, let's just hope it won't be too difficult :)
 » 12 days ago, # |   +38 Ha! Dodged the collision with Project Euler Problem 804 without even conducting the round myself
 » 12 days ago, # |   +5 Looking forward to some positive delta after falling to Pupil from Expert.
 » 12 days ago, # |   0 Good luck everyone!
 » 12 days ago, # |   0 probably going to loose ratings again but ok
•  » » 12 days ago, # ^ |   +1 probably lose not loose
•  » » » 12 days ago, # ^ |   0 okay senpai.
 » 12 days ago, # |   0 hoping to become pupil this round :')
 » 12 days ago, # | ← Rev. 2 →   -6 Can I finally reach CM? Lets find out. SpoilerYes. I did it.
 » 12 days ago, # |   0 pinkrabbit
 » 12 days ago, # |   +3 I just hope that the problem statements tests our logic not English comprehension
 » 12 days ago, # |   0 There are too hard problems :( Over 2000,,,, I'll try man
 » 11 days ago, # |   0 A+B+C==my god
 » 11 days ago, # |   0 Good luck!
 » 11 days ago, # | ← Rev. 2 →   0 Why there are always 4 out of 7 >1700 tasks in global rounds, maybe i am too stupid for that stuff...
•  » » 11 days ago, # ^ |   0 Ох, как я тебя понимаю. Мне осознание D пришло в последние 10 минут раунда. Я до сих пор не верю, что я ее решил.
 » 11 days ago, # |   0 Not complainig (still top 1000 solving A-E, not bad), just venting that python DESTROYED ME this round LOL, with amount of penalties that could kill a gorilla xD. Not sure how penalties can kill a gorilla, but damn it I believe they could.
 » 11 days ago, # |   +3 Oh and forgot to say — GREAT ROUND!!! LOVED the problems. All of them were cool. Very cool.
 » 11 days ago, # |   +52 How I solved E: Realized the number of dolls that need to be moved from a white cell is just the number of paths to that cell from $(0,0)$. Coded the simple $O(\sum{a_i})$ idea to verify I'm not missing something. "Oh great Wolfram Alpha, please tell me how to simplify this equation!" How does an educational problem like this appear in a rated contest, let alone a global round...
•  » » 11 days ago, # ^ |   0 And also I don't know why $a_i$ is guaranteed non-increasing?One guess: the std solution calculates the answer by enumerating $x+y$ :)
•  » » » 11 days ago, # ^ |   0 The number of ways to a cell is not guaranteed to be $x + y \choose y$ otherwise.Consider an input like: 3 3 2 3 3 The corresponding grid when visualized is: ... .. ... ... The number of ways to each cell is: 1 1 1 1 2 1 3 3 1 4 7 I suppose this may be reducible by considering the ways from the previous row, but it is definitely tougher.
•  » » » » 11 days ago, # ^ |   0 I see. Thanks!
•  » » 11 days ago, # ^ |   +3 This problem was originally proposed as 1B, but after some changes it ended up as E.We tried to replace it, but we couldn't find any suitable problem :(I'm really sorry if you find standard.
•  » » » 11 days ago, # ^ |   0 it's not standard, but very easy to guess and solve without proof.
•  » » » 11 days ago, # ^ |   0 The main problem I guess with E is that you can do it almost immediately if you have seen a similar problem before, but you may waste a lot of time if you don't think in the right way. But the problems are good overall, I especially like F.
 » 11 days ago, # |   +18 E = mathforces.
•  » » 11 days ago, # ^ |   0 Maybe it's equal to Oeisforces.
 » 11 days ago, # |   +31 How to solve F?
 » 11 days ago, # |   0 can anyone explain the last test case in first question
 » 11 days ago, # | ← Rev. 2 →   +3 Why did you have to make such strict constraints in D? Why 5e5? 1e5 should be enough to prevent N^2 solutions, maybe 2e5Couldn't fit asymptotically correct but constant-suboptimal solution in python and had to rewrite it in c++.UPD: nevermind, my solution was not asymptotically correct
•  » » 11 days ago, # ^ |   0 Can you please give me some hint?
•  » » » 11 days ago, # ^ |   0 Note that there is no point to generate all edges. Some of them are meaninglessIf next greater element is i and next smaller element is j and i < j, it is enough to draw links between current and argmin(i...j), this one will be able to reach in one hop anything you skipped. Similarly is i < j
•  » » » » 11 days ago, # ^ |   0 Yeah, so how segment tree or sparse table is being used here?
•  » » » » » 11 days ago, # ^ |   0 They're not usedI thought about them and was about to used them but they're need lessAll you need is to be able to find next smallest or largest and maximum on the interval. You could use sparse table here but simple greedy implementation suffice
•  » » 11 days ago, # ^ |   +32 std is $O(n)$.
•  » » 11 days ago, # ^ | ← Rev. 2 →   +16 I had some Segtree-Binary-Search algo with $O(N \log^2 N)$ as first attempt which did TLE. Optimising it to $O(N \log N)$ passed afterwards. Probably they wanted to break such solutions, though it's surely a pain for python users...Edit: Oh, that's exactly what is mentioned in the editorial.
•  » » » 11 days ago, # ^ | ← Rev. 4 →   0 Now that I think about it my solution will probably fail a system test. Though it should be possible to optimize it :sadlaugh:So probably it was a legit reason for my python solution not to pass and I just didn't understand it and pushed it through c++
•  » » » » 11 days ago, # ^ |   0 Yep, FST 14. Should've thought and fixed it during the contest
 » 11 days ago, # |   0 Problems were very interesting. I really enjoyed it.
 » 11 days ago, # |   0 problem A was so similar to leetcode biweekly 81 q3 which occurred at the same time its insane
•  » » 11 days ago, # ^ |   0 Can you explain logic of problem A ? Why there is no effect on value of z by the operation z=ai&z
•  » » » 11 days ago, # ^ |   0 Because and(bitwise) operation give value either less than the minimum number or equal to minimum number.
•  » » » » 11 days ago, # ^ |   0 Oh okay,thank you
 » 11 days ago, # |   0 Couldn't submit D T_T btw loved A-D, even E seemed noice Great round ⊂(◉‿◉)つ
 » 11 days ago, # |   +6 Why does Jiangly submit A, B and C almost at the same time? Gives the others a head start?
•  » » 10 days ago, # ^ | ← Rev. 2 →   0
 » 11 days ago, # |   +6 I bet most of the submissions for problem B would have received WA on pretest 2 (includig me..XD)! They had us in the first half!
•  » » 11 days ago, # ^ |   0 absolutely lol; fun fact, the moment i hit submit...it struck me that 2 should be the max always lmao
•  » » » 11 days ago, # ^ |   0 i still did not get it. can you explain
•  » » » 11 days ago, # ^ |   0 shit i just got it WTF how did i miss that!
 » 11 days ago, # | ← Rev. 2 →   0 Nice questions! A and B were not straight, yet they were easy I couldnt do C tho...and I was about to finish D but looks like getting the minimum was problematic lol, maximum was working fine (time complexities considered)... :((( Could have been a long jump I guess xD But looks like i will take a minus nowupdate: I got a + lol
•  » » 11 days ago, # ^ |   +17 A and B were not straight i mean, it is pride month, so.
•  » » » 11 days ago, # ^ |   0 damn!!!
 » 11 days ago, # |   0 The question was Amazing, thnx for making such exciting questions, and I hope we will get the tutorial early.
 » 11 days ago, # |   +22 D has weak pretests. In the worst case, my first submission takes $O(N)$ time to find the next vertex, so its overall complexity is $O(N^2)$, but it passed pretests.
•  » » 11 days ago, # ^ |   +23 The pretests make my own implementation run in $O(n^2)$, but it turns out that some implementations are smarter and need other tests to break. We are sorry :(
•  » » » 11 days ago, # ^ |   -8 $\Omega\left(n^2\right)$, not $\mathcal O\left(n^2\right)$.
 » 11 days ago, # |   0 very much enjoyed orz :)
 » 11 days ago, # |   +8 this is my first time in the contest.although i ac one ，i am also very happy.
 » 11 days ago, # |   +77 So, here is some feedback on the problems: A: Ok easy problem. B: Ok easy problem. C: Nice and clean. Somewhat educational, but still enjoyable. D: Cool problem, with the appropriate difficulty. I saw rather quickly the main observation (it is convenient to go greedy) and then I spent an eternity implementing it. E: Uhm, rather standard. First thought after reading: this must be related to the number of path from $(0, 0)$ to something. Then, after ~15 minutes I could pinpoint exactly to what paths it is related to. Felt a bit easy as an E (but actually also B, C, D felt a bit easy, so it fits). F: First, mandatory attachment: What a run! I hope I pass systests, since it would be the closest-call (10 seconds) I have ever experienced on cf. Wonderful problem, it was hard for me and I am proud of myself for solving it. I spent quite some time thinking and realized only after more than 40 minutes how to detect a leaf. Then I (barely) managed to implement it before the end of the contest. Overall, the contest was well-prepared and the statements were clear. Even though I am not a fan of the first 5 problems, which are somewhat standard, I had so many emotions solving F that I liked the whole contest a lot! Thanks to the authors.
 » 11 days ago, # |   +59 why there were n+1 integers in input instead of n in E?(ಥ﹏ಥ) i missed an AC due to that (ಥ﹏ಥ)(ಥ﹏ಥ)(ಥ﹏ಥ)
•  » » 11 days ago, # ^ | ← Rev. 2 →   +10 I wasted 20 minutes because of the same reason
•  » » » 11 days ago, # ^ |   +6 I think E was easy than D.
•  » » 11 days ago, # ^ |   0 i also wasted 15-20 minutes for same reason
•  » » » 11 days ago, # ^ |   +1 Thnx to my slow implementation in C,D ...i just had 4-5 minutes to debug after coding my logik for E ... hence wasn't able to find my error till end. Its quite painful (ಥ﹏ಥ)(ಥ﹏ಥ)
 » 11 days ago, # |   0 Feel so good to solve E, at least pass the pretests! After running nowhere with some vague idea of formal power series or polynomials, I started to notice the pattern of Binomial coefficients when drawing on paper some examples, and then search around for binomial identities and finally find a match! Never feel so certain that I still have potential to improve my mathematics skills~Hope no FST~
•  » » 11 days ago, # ^ |   0 Upon brainstorming on both D and E, I honestly felt D was tougher for some reason. Anyways, I couldn't solve either so there's a lot to learn rn, will try to upsolve them now... Hope you successfully pass Main Tests :)
•  » » » 11 days ago, # ^ |   0 Well, I think D has a greedy solution: just use farthest next hop, but I couldnot prove it, greedy problems are tough for me, no idea how to grasp the essentials, most of the time I just feel lucky to come around with ideas....
 » 11 days ago, # |   0 contest Gone GREAT :)
 » 11 days ago, # |   0 Really amazing contest! Great problems, had a fun (although stressful) time trying them out. Kudos to feecIe6418 gyh20 and the rest of the team!
 » 11 days ago, # | ← Rev. 2 →   +8 E was easier to think after linking to pascal's triangle
•  » » 10 days ago, # ^ |   0 It's the yanghui triangle, sir
 » 11 days ago, # |   +7 Stumbling upon the orz problem was so cute! (even though it was trivial)
 » 11 days ago, # |   +1 Made the factorial array of 2*10^5 instead of 4*10^5(a[i]+i). Missed E! :'(
 » 11 days ago, # |   +4 "Find the maximum possible value of the maximum value in a after any number (possibly zero) of operations."In Problem A this line mislead me into thinking that we have to maximize the maximum value of the original array, so I took the maximum value say "V" in the array and expected V|Z to be the answer, but after spending like an hour and half I realized that the answer would be the maximum attainable value of any value in the array, I would like to request the authors to write clearer statements to avoid such confusion, like the line mentioned above could be replaced by, "Find the maximum possible value in a after any number (possibly zero) of operations." Those who faced the same difficulty can upvote the post so that it reaches the authors. Peace.
•  » » 11 days ago, # ^ |   0 That's right. I faced the same issue yesterday. I wonder why many people are not talking about it yet.
•  » » » 11 days ago, # ^ |   0 Yea man maybe it was obvious for others, or maybe they didn't stress to much on that statement and moved on with their intuition, but the statement could have been written more clearly.
 » 11 days ago, # |   +52 Weird statements swap(D,E) Weak pretests for D E is classical F is boring and implementation is annoying G is classical(get the duel problem and solve it) and implementation is much more annoying Hyper Chinese round! Very enjoyable!
 » 11 days ago, # |   0 Does E have a solution if there is no non-increasing $a_i$ constraint?
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Does it really matter whether the value was n+1 or n?
 » 11 days ago, # |   0 I tried to solve D with pie for pie (bfs trick) + sparse table but it gets TLE on test 2. Can somebody explain why? Thanks in advance. Submission link:
 » 11 days ago, # |   +8 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 11 days ago, # |   +76 I wonder why this round is chosen to be GR. There are definitely better choices like Round 796.
•  » » 11 days ago, # ^ |   +10 In fact I found the round is tooooo standard (but D is cool).
 » 11 days ago, # |   0 a great contest :) thanks
 » 11 days ago, # |   +1 Fast tutorial and excellent problems today. Loved the contest.
 » 11 days ago, # |   +1 why my rating get decreases from 777 to 736 though I have solved the 'A'.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 deleted
 » 11 days ago, # |   0 Global round,it seem interesting.
»
11 days ago, # |
+32

Unofficial T-shirt winners list:

(Used the same method as: https://codeforces.com/blog/entry/102081?#comment-908978)

List place Contest Rank Name
1 1696 1 ksun48
2 1696 2 jiangly
3 1696 3 Um_nik
4 1696 4 Petr
5 1696 5 maroonrk
6 1696 6 Alice_foo_foo
7 1696 7 tourist
9 1696 9 TLE
10 1696 10 hos.lyric
11 1696 11 kiwikiwi
12 1696 12 fivedemands
13 1696 13 djq_cpp
14 1696 14 mhq
15 1696 15 Isonan
16 1696 16 Elegia
17 1696 17 Maksim1744
18 1696 18 ecnerwala
19 1696 19 Rebelz
20 1696 20 Endagorion
21 1696 21 kotatsugame
22 1696 22 Rubikun
23 1696 23 sjcsjcsjc
25 1696 25 slime
26 1696 26 potato167
27 1696 27 zh0ukangyang
28 1696 28 353cerega
29 1696 29 never_giveup
30 1696 30 neal
97 1696 97 Everule
105 1696 105 zhangguangxuan99
108 1696 108 FormalPowerSeries
111 1696 111 huangzirui
114 1696 114 PurpleCrayon
115 1696 114 dfcmd
161 1696 161 blackyuki
166 1696 166 lightseba
232 1696 232 Davoth
241 1696 241 Flying2021
316 1696 316 SPD_9X2
333 1696 333 titia
357 1696 357 dlhham
370 1696 367 Hakiobo
378 1696 378 BlueBottle
386 1696 386 berekuk
410 1696 409 AlternatingCurrent
422 1696 422 subscriber
423 1696 423 gleb.astashkin
 » 10 days ago, # |   0 Hey Codeforces admins! My submission was denied! My submission ID is 161777846. Please recheck it, there is no way I could steal code from someone! At least prove it, before banning me.
•  » » 10 days ago, # ^ |   0 Please, check once! I banned for nothing, sad, very sad!
 » 10 days ago, # |   0 I was double-checked, but I submitted the code 16 minutes earlier than the other person. Code 161763398,161770959. I don't know anyone else, but I suspect that someone found my code in room and sent it to someone else. Hope for a retrial.
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 Why would someone in your room send your code to someone else if they could just send their own code?
•  » » » 10 days ago, # ^ |   0 But other than that possibility, I can't think of any reason why my code would be similar to someone I don't know, and I made sure that my code wasn't sent to anyone else during the race.
 » 10 days ago, # |   0 In re-sentencing, please restore my ranking first, rather than according to a question did not pass the ranking calculation. I could have gained 75 points, but now I've lost 175.
 » 9 days ago, # |   0 Please tell why my solution is giving TLE. Shouldn't N((log(N))^2) pass? My solution Problem
 » 9 days ago, # |   -10 Why didn't you restore my rank first when you re-evaluated my score? Your unreasonable behavior caused me a lot of trouble. I hope you can help me solve it.