Блог пользователя feecIe6418

Автор feecIe6418, 2 года назад, По-английски

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
  • Проголосовать: нравится
  • +749
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Only 8 testers? Interesting.

»
2 года назад, # |
  Проголосовать: нравится +268 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +311 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +107 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

waiting for a perfect contest!

»
2 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

As a tester, good luck!

»
2 года назад, # |
  Проголосовать: нравится +122 Проголосовать: не нравится

As a human, ShuiLaoshi is a great bot!

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

good

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I love global rounds so much ^_^

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

tmp-

»
2 года назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

:D

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +45 Проголосовать: не нравится

Hoping to become CM this round!

UPDATE: Messed up :(

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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

»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
    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.

  • »
    »
    2 года назад, # ^ |
    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.

»
2 года назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Hoping to turn expert this round!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +112 Проголосовать: не нравится

(IMG-20220617-WA0001)

»
2 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

cqoier Orz

»
2 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Is this a Chinese Poisonous OI round again?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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 :)

»
2 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

probably going to loose ratings again but ok

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

Can I finally reach CM? Lets find out.

Spoiler
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

pinkrabbit

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 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$$$ :)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

E = mathforces.

»
2 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

How to solve F?

»
2 года назад, # |
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 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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please give me some hint?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    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.

    • »
      »
      »
      2 года назад, # ^ |
      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++

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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!

»
2 года назад, # |
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 now

update: I got a + lol

»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

very much enjoyed orz :)

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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~

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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 :)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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....

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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:

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

a great contest :) thanks

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Fast tutorial and excellent problems today. Loved the contest.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -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.

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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