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 tshirt.
 20 tshirts are randomly distributed among those with ranks between 31 and 500, inclusive.
The prizes for the 6round series in 2022:
 In each round top100 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:
 irkstepanov for coordination, and KAN for helping as well.
 gyh20, ShuiLaoshi, ilyakrasnovv, fengzhengwei, Vladithur, antontrygubO_o, Golovanov399, snowysecret, ak2006 for testing.
 MikeMirzayanov for polygon and codeforces.
Round information:
 duration: 2 hours and 15 minutes
 number of problems: 8
 score distribution: 5001000150020002000250032504000
We are looking forward to your participation!
Upd Editorial https://codeforces.com/blog/entry/103479
Upd Winners!
Only 8 testers? Interesting.
I see no difference.
As a tester and an author of one problem, feecIe6418 orz.
gyh20 orz.
orzorzorz
As a tester, I can't wait to see PinkieRabbit's performance!
interesting
Its twice I have seen this message. What does this mean?
PinkieRabbit is a very popular up (just like youtuber ) in Chinese. Sometimes the writers or testers are his fans, then he will be invited.
So you don’t mind if I advertise my screencast here, right?
https://www.bilibili.com/video/bv1yB4y1q71A (in Chinese)
feecIe6418 orz.
waiting for a perfect contest!
As a tester, good luck!
As a human, ShuiLaoshi is a great bot!
good
I love global rounds so much ^_^

2:15? The only upside is that my suffering will end sooner.
:D
Hoping to become CM this round!
UPDATE: Messed up :(
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
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.
Well, there is no 250point 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 speedoriented, unbalanced problemset imo. If you think otherwise, then please comment your thought.
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.
Hoping to turn expert this round!
()
As someone having a discrete maths and linear algebra quiz, i am scared
Don't worry. Send adamant in your place.
looking forward to become Specialist this round! The expectations are very high.
cqoier Orz
Is this a Chinese Poisonous OI round again?
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 :)
Ha! Dodged the collision with Project Euler Problem 804 without even conducting the round myself
Looking forward to some positive delta after falling to Pupil from Expert.
probably going to loose ratings again but ok
probably lose not loose
Can I finally reach CM? Lets find out.
Yes. I did it.
pinkrabbit
I just hope that the problem statements tests our logic not English comprehension
Good luck!
Why there are always 4 out of 7 >1700 tasks in global rounds, maybe i am too stupid for that stuff...
Not complainig (still top 1000 solving AE, 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.
Oh and forgot to say — GREAT ROUND!!! LOVED the problems. All of them were cool. Very cool.
How I solved E:
How does an educational problem like this appear in a rated contest, let alone a global round...
And also I don't know why $$$a_i$$$ is guaranteed nonincreasing?
One guess: the std solution calculates the answer by enumerating $$$x+y$$$ :)
The number of ways to a cell is not guaranteed to be $$$x + y \choose y$$$ otherwise.
Consider an input like:
The corresponding grid when visualized is:
The number of ways to each cell is:
I suppose this may be reducible by considering the ways from the previous row, but it is definitely tougher.
I see. Thanks!
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.
it's not standard, but very easy to guess and solve without proof.
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.
E = mathforces.
Maybe it's equal to Oeisforces.
How to solve F?
Why did you have to make such strict constraints in D? Why 5e5? 1e5 should be enough to prevent N^2 solutions, maybe 2e5
Couldn't fit asymptotically correct but constantsuboptimal solution in python and had to rewrite it in c++.
UPD: nevermind, my solution was not asymptotically correct
Can you please give me some hint?
Note that there is no point to generate all edges. Some of them are meaningless
If 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
Yeah, so how segment tree or sparse table is being used here?
They're not used
I thought about them and was about to used them but they're need less
All 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
std is $$$O(n)$$$.
I had some SegtreeBinarySearch 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.
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++
Yep, FST 14. Should've thought and fixed it during the contest
problem A was so similar to leetcode biweekly 81 q3 which occurred at the same time its insane
Couldn't submit D T_T btw loved AD, even E seemed noice Great round ⊂(◉‿◉)つ
Why does Jiangly submit A, B and C almost at the same time? Gives the others a head start?
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!
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 now
update: I got a + lol
i mean, it is pride month, so.
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.
The pretests make my own implementation run in $$$\Theta(n^2)$$$, but it turns out that some implementations are smarter and need other tests to break. We are sorry :(
$$$\Omega\left(n^2\right)$$$, not $$$\mathcal O\left(n^2\right)$$$.
very much enjoyed orz :)
this is my first time in the contest.although i ac one ，i am also very happy.
So, here is some feedback on the problems:
Overall, the contest was wellprepared 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.
why there were n+1 integers in input instead of n in E?(ಥ﹏ಥ) i missed an AC due to that (ಥ﹏ಥ)(ಥ﹏ಥ)(ಥ﹏ಥ)
I wasted 20 minutes because of the same reason
I think E was easy than D.
i also wasted 1520 minutes for same reason
Thnx to my slow implementation in C,D ...i just had 45 minutes to debug after coding my logik for E ... hence wasn't able to find my error till end. Its quite painful (ಥ﹏ಥ)(ಥ﹏ಥ)
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~
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 :)
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....
E was easier to think after linking to pascal's triangle
It's the yanghui triangle, sir
Stumbling upon the orz problem was so cute! (even though it was trivial)
Made the factorial array of 2*10^5 instead of 4*10^5(a[i]+i). Missed E! :'(
"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 VZ 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.
That's right. I faced the same issue yesterday. I wonder why many people are not talking about it yet.
Hyper Chinese round! Very enjoyable!
Does E have a solution if there is no nonincreasing $$$a_i$$$ constraint?
Does it really matter whether the value was n+1 or n?
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:
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
I wonder why this round is chosen to be GR. There are definitely better choices like Round 796.
In fact I found the round is tooooo standard (but D is cool).
a great contest :) thanks
Fast tutorial and excellent problems today. Loved the contest.
why my rating get decreases from 777 to 736 though I have solved the 'A'.
Unofficial Tshirt winners list:
(Used the same method as: https://codeforces.com/blog/entry/102081?#comment908978)
Sorry, I just saw that I won the prize today . Please tell me how to get the prize ，thx
I was doublechecked, 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.
Why would someone in your room send your code to someone else if they could just send their own code?
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.
In resentencing, 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.
Please tell why my solution is giving TLE. Shouldn't N((log(N))^2) pass? My solution Problem
Why didn't you restore my rank first when you reevaluated my score? Your unreasonable behavior caused me a lot of trouble. I hope you can help me solve it.
Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.