feecIe6418's blog

By feecIe6418, 2 years ago, In English

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.me/blog/entry/103479

Upd Winners!

  1. ksun48
  2. jiangly
  3. Um_nik
  4. Petr
  5. maroonrk
Announcement of Codeforces Global Round 21
  • Vote: I like it
  • +749
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Only 8 testers? Interesting.

»
2 years ago, # |
  Vote: I like it +268 Vote: I do not like it

As a tester and an author of one problem, feecIe6418 orz.

»
2 years ago, # |
  Vote: I like it +311 Vote: I do not like it

As a tester, I can't wait to see PinkieRabbit's performance!

»
2 years ago, # |
  Vote: I like it +107 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting for a perfect contest!

»
2 years ago, # |
  Vote: I like it +45 Vote: I do not like it

As a tester, good luck!

»
2 years ago, # |
  Vote: I like it +122 Vote: I do not like it

As a human, ShuiLaoshi is a great bot!

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

good

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I love global rounds so much ^_^

»
2 years ago, # |
Rev. 2   Vote: I like it +42 Vote: I do not like it

tmp-

»
2 years ago, # |
  Vote: I like it +63 Vote: I do not like it

2:15? The only upside is that my suffering will end sooner.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:D

»
2 years ago, # |
Rev. 2   Vote: I like it +45 Vote: I do not like it

Hoping to become CM this round!

UPDATE: Messed up :(

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +45 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Hoping to turn expert this round!

»
2 years ago, # |
Rev. 2   Vote: I like it +112 Vote: I do not like it

(IMG-20220617-WA0001)

»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

As someone having a discrete maths and linear algebra quiz, i am scared

»
2 years ago, # |
  Vote: I like it -20 Vote: I do not like it

looking forward to become Specialist this round! The expectations are very high.

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

cqoier Orz

»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Is this a Chinese Poisonous OI round again?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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 :)

»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Ha! Dodged the collision with Project Euler Problem 804 without even conducting the round myself

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Looking forward to some positive delta after falling to Pupil from Expert.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

probably going to loose ratings again but ok

»
2 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Can I finally reach CM? Lets find out.

Spoiler
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

pinkrabbit

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I just hope that the problem statements tests our logic not English comprehension

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why there are always 4 out of 7 >1700 tasks in global rounds, maybe i am too stupid for that stuff...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Oh and forgot to say — GREAT ROUND!!! LOVED the problems. All of them were cool. Very cool.

»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it

How I solved E:

  1. 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)$$$.
  2. Coded the simple $$$O(\sum{a_i})$$$ idea to verify I'm not missing something.
  3. "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...

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$ :)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's not standard, but very easy to guess and solve without proof.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

E = mathforces.

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

How to solve F?

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 constant-suboptimal solution in python and had to rewrite it in c++.

UPD: nevermind, my solution was not asymptotically correct

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please give me some hint?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, so how segment tree or sparse table is being used here?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    std is $$$O(n)$$$.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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++

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep, FST 14. Should've thought and fixed it during the contest

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem A was so similar to leetcode biweekly 81 q3 which occurred at the same time its insane

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't submit D T_T btw loved A-D, even E seemed noice Great round ⊂(◉‿◉)つ

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why does Jiangly submit A, B and C almost at the same time? Gives the others a head start?

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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!

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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 :(

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      $$$\Omega\left(n^2\right)$$$, not $$$\mathcal O\left(n^2\right)$$$.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very much enjoyed orz :)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

this is my first time in the contest.although i ac one ,i am also very happy.

»
2 years ago, # |
  Vote: I like it +77 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +59 Vote: I do not like it

why there were n+1 integers in input instead of n in E?(ಥ﹏ಥ) i missed an AC due to that (ಥ﹏ಥ)(ಥ﹏ಥ)(ಥ﹏ಥ)

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I wasted 20 minutes because of the same reason

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also wasted 15-20 minutes for same reason

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 (ಥ﹏ಥ)(ಥ﹏ಥ)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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~

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

E was easier to think after linking to pascal's triangle

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Stumbling upon the orz problem was so cute! (even though it was trivial)

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Made the factorial array of 2*10^5 instead of 4*10^5(a[i]+i). Missed E! :'(

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

"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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's right. I faced the same issue yesterday. I wonder why many people are not talking about it yet.

»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it
  • 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!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does E have a solution if there is no non-increasing $$$a_i$$$ constraint?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
2 years ago, # |
  Vote: I like it +76 Vote: I do not like it

I wonder why this round is chosen to be GR. There are definitely better choices like Round 796.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In fact I found the round is tooooo standard (but D is cool).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a great contest :) thanks

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Fast tutorial and excellent problems today. Loved the contest.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why my rating get decreases from 777 to 736 though I have solved the 'A'.

»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Unofficial T-shirt winners list:

(Used the same method as: https://codeforces.me/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
8 1696 8 Radewoosh
9 1696 9 TLE
10 1696 10 hos.lyric
11 1696 11 DearMargaret
12 1696 12 fivedemands
13 1696 13 djq_cpp
14 1696 14 244mhq
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
24 1696 24 FutureGadgetLaboratory
25 1696 25 Rewinding
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
307 1696 307 TheLostCookie
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
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I just saw that I won the prize today . Please tell me how to get the prize ,thx

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why would someone in your room send your code to someone else if they could just send their own code?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please tell why my solution is giving TLE. Shouldn't N((log(N))^2) pass? My solution Problem

»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like 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.

get_tshirts.py
randgen.cpp
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
8 1696 8 Radewoosh
9 1696 9 TLE
10 1696 10 hos.lyric
11 1696 11 DearMargaret
12 1696 12 fivedemands
13 1696 13 djq_cpp
14 1696 14 244mhq
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
24 1696 24 FutureGadgetLaboratory
25 1696 25 Rewinding
26 1696 26 potato167
27 1696 27 zh0ukangyang
28 1696 28 353cerega
29 1696 29 never_giveup
30 1696 30 neal
97 1696 96 davi_bart
105 1696 104 Melusine
108 1696 108 Brovko
111 1696 110 SSRS_
114 1696 113 dfcmd
115 1696 115 ki0apa
161 1696 161 Sulfox
166 1696 166 sys.
232 1696 232 SevenDusks
241 1696 241 mjhmjh1104
307 1696 307 OIer_kzc
316 1696 316 TKT_YI
333 1696 333 HyscereXD
357 1696 356 KazmetreD
370 1696 370 Sakuyalove
378 1696 378 Ziyi_Wang1
386 1696 385 SpaceJellyfish
410 1696 410 ykl
422 1696 422 zhaotiensn
423 1696 423 anatolik