liouzhou_101's blog

By liouzhou_101, history, 2 years ago, In English

Hello, Codeforces Addicts!

On 30.09.2022 17:35 (Московское время) we will host Codeforces Global Round 22.

Codeforces Global Round 22 is the $$${\textbf{2}} \cdot {\textbf{2}} = 4$$$-th 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!

The problems were written and prepared by antontrygubO_o, Milesian and me.

We are extremely grateful to the following people who made this round possible:

Round Information:

  • Duration: 2 hours and 30 minutes
  • Number of problems: $$${\textbf{2}} \cdot {\textbf{2}} \cdot {\textbf{2}} = 8$$$
  • Score distribution: 500 — 1000 — 1500 — 2000 — 2500 — 2750 — 3000 — 4000

Kind Tips:

We are looking forward to your participation!

UPD. Editorial

Congratulations to the winners!

  1. cnnfls_csy

  2. ksun48

  3. maroonrk

  4. orzdevinwang

  5. ko_osaga

  6. tourist

  7. jiangly

  8. noimi

  9. peti1234

  10. Maksim1744

And for the winner of each problem:

A. tourist

B. tourist

C. wind_cross

D. tourist

E. tourist

F. 300iq

G. ksun48

H. rainboy

Announcement of Codeforces Global Round 22
  • Vote: I like it
  • -112
  • Vote: I do not like it

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

I don't know how I should feel about this bug...

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

    funny how I guessed you were going to be here before opening the blog, lol.

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

      funny how I guessed you were going to be here before opening the blog, lol.

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

        funny how I didn't guess you were going to be here before opening the blog, lol.

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

          funny how you didn't guess i'm marinush, lol.

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

Good luck & have fun & Orz !
2022 = 2222 - 222 + 22 = 22(22) * 22(22) - 22(22) * 2 - 2 !

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

As a tester I <strong></strong>

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

but why isn't global on weekend? ):

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

    The weekend is most commonly considered the period between Friday evening and the end of Sunday.

    from Google

    So, maybe Codeforces consider Friday as weekend, emmmm, half-weekend at least.

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

      It's indeed on Friday but it's not in the evening for probably one half of the earth due to timezones.

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

        Any time is not evening for more than half of timezones...

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

    Maybe it's because .... 2 days before the week...end?

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

Can we please make the contest 8 minutes shorter for the memes?

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

    If the system had allowed it, it'd be good to make problem D or E worth 2222 points as well, but sadly we can't

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

    Great idea! Can't agree more!

    But it seems we cannot do that. What a pity

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

    222 + 2*2*2

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

    150 minutes shorter might have been better I think

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

As a tester, I'm glad that a bad problem was removed from this contest.

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

 :D

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

The emphasis on 2 is hinting at WA on pretest 2

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

2 much 2 in 2morrow's contest

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

As a tester, this contest has a couple of nice problems, but the overall quality is worse than average.

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

    Lol

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

    As a participant, I am surprised to see a useful tester comment.

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

    Very interesting, also as a tester, the first time I saw a tester say that the problem is not good, generally speaking, as a tester, no matter what the problem is, I will praise the problem, if the problem is good, I would rate it higher, but I like your personality.

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

    Thank you for your honesty. Your suggestions will make our rounds better in the future.

    Anyway, wish everyone will find something interesting in this round.

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

      But why didn't their suggestions make your current round better?

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

        From where do you see that their suggestions did not make our round better?

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

    As a tester, I second this.

    Tired to see testers just praise every contest...

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

    I should have trusted you:)

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

    I don't like testers giving any information on the contest before the round. You felt entitled to do it and the community heavily upvoted you, but such a behavior is outside the scopes and the rights of the tester.

    The usual "Best contest ever" comments by testers are childish and annoying, but they are empty. Your comment is actually giving information. If I were the author I would be very pissed as you have likely reduced the number of participants.

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

      I don't like testers giving any information on the contest before the round.

      I didn't give any information that can be used to get a better result, did I? I don't think that providing such kind of information is worse than providing the names of the authors, which CF does every time.

      The usual "Best contest ever" comments by testers are childish and annoying, but they are empty.

      What do you mean "empty"? What's the difference between saying "the contest is good" and "the contest is bad" from the perspective of providing information? It seems to me like you are applying some imaginary rules. It's like you must answer "I'm good, thanks" to "How are you?". I don't do small talk.

      If I were the author I would be very pissed as you have likely reduced the number of participants.

      I couldn't care less.

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

        I didn't give any information that can be used to get a better result, did I?

        True, but it's not the point.

        I don't think that providing such kind of information is worse than providing the names of the authors, which CF does every time.

        Possibly true, but it's not the point. Codeforces, being the organizing platform, is entitled to do whatever it wants. A tester should respect the not-imaginary-but-implicit-and-useful rule: if someone is given a private information for a specific purpose, he cannot share the information.

        What do you mean "empty"?

        I don't deduce anything on a round when a random tester says that the contest is wonderful. It's exactly as saying "I am fine, thank you" when asked "How are you?" as you mentioned. On the other hand, when you write what you wrote, I deduce information about the round (and in fact, a posteriori, I think that your comment is correct). It's because writing "The problems are amazing" is a trend among testers, it's also because I know that you are more reliable than a random tester.

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

      If I were the author I would be very pissed as you have likely reduced the number of participants.

      I assure you that didn't happen. For example, I participated from alt account

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

As a comedian Codeforces Global Round 10110

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

Fun. Why not "200 t-shirts are randomly distributed among those with ranks between 31 and 5000, inclusive". Then I wish to win a t-shirt with probability 200*1/4970

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

Does it rated?

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

Fun fact about the number 22 I just found out:

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

The BPM of Freedom Dive by xi is 222.22.

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

Good luck and have fun! Hope it won't be unrated :D. I have been waiting for a great global round for a long time ^_^.

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

is this round rated

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

You people are too obsessed with 22 number.

Grow up kids

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

no need for factorial at the end of the equation)

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

Hope it won't be unrated!

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

Hoping for lesser cheating

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

Hope Pretest 2 would be strong enough!

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

    I wasn't :)

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

      Yeah! you could be strong.. so many B and C were Hacked/FSTed :(

      B could contain the edge case k = 1 in either samples or pretests, sadly I got FST too :(

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

hoping for +ve delta

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

I hope there are no copied problems this time.

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

i need dalex to butthurt about how statements are hard to understand

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

    I retired from everything related to CP

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

C is the worst problem I've seen.

Stop taking these Chinese style shit problem into cf.

edit: Sorry D is worse

edit: Sorry E is worse

edit: Sorry H is worse

edit: Statements are too long. I think authors could use spoiler to fold some definition. F is great. Gaps are too small.

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

    i guess you are the only one who is worse and ugly here LOL : (

    if it is worse who said you to do it

    dont do it if you dont like it

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

      Because I love both rating and joy of solving problems you such sore loser ^_^

      Red is much more beautiful than grey I think.

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

      If you can't say which problem is good and which is worse then u are a loser.

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

    Can't agree more

    Weak pretest on B and C ... That's even worse when I get FST on C :(

    ([hit_call]dx[hit_call])

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

ReadingForces

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

Why is this contest so hard? :(

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

    Worse than just that, the difficulty distribution is very flat. I felt like all problems among BCDEF had pretty much the same difficulty, instead of seeing gradually harder problems.

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

Is this WA on pretest 2 contest !? o((⊙﹏⊙))o
I think all will get negative delta after this round!!

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

This contest is only good for those with high IQ or great observation skills. Banging my head smh.

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

    great observation skills

    C is about as standard as it's possible to be, with no observation skills required.

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

      I apologize, I didn't see the constraints. I was thinking of standard even-odd formula.

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

why does C give negative elements (sweat)?

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

    Did you mean B? In C, all that matters is whether elements are even or odd, so negative elements should not be an issue.

    Negative elements in B were a bit annoying though.

    EDIT: nvm, I forgot that a negative odd number mod 2 produces -1 in C++ (and probably some other languages too). I actually dodged a bullet by checking for evens instead of odds (which were covered by the else).

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

wrong-answer-on-pretest2-forces

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

Really difficult contest TAT.

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

I guess, no more The problems were written and prepared by antontrygubO_o rounds for me. Worst contest ever...

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

idk

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

How to solve E?

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

I mean come on, samples for E were just evil. I think it would have been better ff samples would have been a bit stronger,

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

How to solve Q2....

WA 17 times...

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(k == 1){
      YES
    }
     
    if((n-k+1)*(s[1] - s[0]) < s[0]){
      NO
    }
     
    for(int i=0; i<k-2; i++){
      if(s[i+1] - s[i] > s[i+2] - s[i+1]){
        NO
      }
    }
     
    YES
    
»
2 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Thanks to Codeforces Global Round 22 and Educational Codeforces Round 136 I will return back to specialist.
very bad contests just constructive problems depends only on mentality skills!!!

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

D >>>>>> A > E > F > B > C. Change my mind. I have no idea how E&F have 4 times less solves when D is legendary hard.

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

I don't think problems are bad but I somehow performed really bad :(

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

Great problems! I especially enjoyed C!

I couldn't manage to solve D tho :(

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

Problem H is straightforward and tedious application of eertree with ridiculous constraints that won't allow $$$O(n \log^2 n)$$$ solutions to pass. Otherwise, the main idea (at least the one that I have used) almost completely repeats this and this problems.

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

    I bet you will be surprised when seeing the intended time complexity.

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

      Why linear when you can do it polylog way more easily :(

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

        Indeed, I don't want to make only $$$O(n)$$$ pass. Just allow some $$$O(n \log n)$$$ to pass.

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

        I passed pretests with $$$O(n \log n)$$$, but the experience is soul-crushing, as I couldn't just submit $$$O(n \log^2 n)$$$ solution that I had from some earlier problems and it ultimately consumed too much time for any meaningful recovery on other problems after passing it :(

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

Is F easier than E? I found there are many participants who solved F much faster than E.

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

    The logic for F is easy compared to E. It's just that people have hard time understanding interactive problems

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

      I would say the opposite. The logic of E seems much easier than F, but the implementation is kind of a pain and at least in my implementation there was a special case that I missed (I kind of convinced myself that the logic for 0 0 0 and 1 0 0 0 1 is the same, but it's not). Meanwhile, F was actually kind of clean for an interactive problem.

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

    Is AGC easier than some large-coded data structures like 917E - Обратная сторона?

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

got hacked on B yesterday and today as well, I would have reached pupil otherwise, any suggestions to avoid hacks?

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

Is there any simple solution for A?

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

i just feel c samples would have been better i feel its just useless why didn't it cover more scenarios?

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

Errrrrrrrrr... Not bad

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

How to solve H:

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

    How could I have remembered that while I was not feecle6418. :(

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

    I bet you will be surprised when seeing the intended time complexity.

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

      I know that in some year's (edit:2017) Chinese IOI Training Essays, there exists a paper that claims "PAM can support arbitary pushfront pushback popfront popback operations in complexity same with only pushfront pushback". (However I have never seen an implementation of it) So I guess it indeed can be solved in less complexity.

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

      The thing that surprised me the most is that the alphabet size is larger than logn.

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

        Never mind. I just don't want $$$O(n \log n)$$$ to fail.

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

    How to solve H:

    • Find that this problem is weaker than range query
    • Google/Baidu/Bing the range query version
    • Get the problem id on LOJ
    • Copy & Paste
    • AC

    Edit:

    Some of my friends complained that if you find the solution of BZOJ version you might get TLE.

    However this situation should be checked before the contest, authors and testers should ensure that there is no googleable problem.

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

      Got it! Next time I will let all non $$$O(n)$$$ solution fail. Then, it's not googleable at all. Do you like it?

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

      Could you point to the problem? Intended solution to this one is $$$O(n \log^2 n)$$$ and it gets TL.

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

        I actually copypasted main ptz solution to BOJ 19026 (fearful is my alt), then opened the fastest solution by cyanic and constant-optimized it a bit.

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

road to pupil

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

Sad. The thinking was somehow enjoyable though.

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

D had so much reading comprehension, the solution ended up being kinda nice but not worth the like 1 hour of just brute forcing patterns.

C was literally you know DP or you don't, unless there's a greedy solution?

A and B were kinda insane for A's and B's

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

    I saw some people in my room doing c using a bunch of if conditions,idk if that solution is right tho...

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

    For problem C, DP is not necessary.

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

    I did DP too. Then I printed the array over amount of zeroes and ones. We get regular 2x4 Blocks:

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

    Somebody in my room solved C as follows:

    Let $$$n_o$$$ be the number of odd elements and $$$n_e$$$ be the number of even elements.

    If $$$n_o \bmod 4 = 2$$$, Bob wins. If $$$n_o \bmod 4 = 1$$$ AND $$$n_e$$$ is even, then Bob also wins.

    Otherwise, Alice wins.

    Proof: No freaking clue, but I printed my 100 x 100 DP table, and the results seemed consistent...

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

    C is a bunch of ifs

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

    C was literally you know DP or you don't

    Can you elaborate?

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

Why it was too tough for me ?

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

    Problem A was really too difficult to be A for others too.

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

      Note that this is actually a Div1 contest (i.e., rated for everybody), not a Div2 (like most of what we've been having recently), so a bit of challenge is actually justified here imo. I don't feel like this one is too hard by Div1A standards.

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

        I see that you have not given any global round so far. Even in global round, problem A is very simple

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

          Ah, I see, my bad. I was under the impression that any contest that's rated for everyone is a Div1 contest, so I didn't actually realize that there was a difference.

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

    dont worry, problem A and B were harder than usual

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

Pupil I am coming

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

Is there a way to solve C other than 4d DP? 4 dimenion = dp[odd][even][alice][needOdd].

D is straight forward greedy right?

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

    yes it's simple bruteforces method. my code : 174150204

    explain: first of all you check how many maximum number of odd alice can get if that is even then definetly alice will win. otherwise you can check that how many time even numbers are if that is odd time then alice choose number such that he got last even number so bob must be select one odd number so now we apply same above approch but number off odd is decreased by 1. and above all condition not sutisfy then bob will win.

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

how can i spend nearly two hours and finally realized just some bruteforce is enough for C

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

Can Anyone Explain me i am got runtime_error on my 1st quetion solution in c++20 language but when i have submit same code in c++17 then i got accepted but for changing language i take 1 hour. so can anyone explain me why this happen in c++20. my c++20 code: 174108183 my c++17 code: 174139409

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

F is really a great problem and it took me very long time.

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

Here is some feedback on the problems:

  • A: Nice easy problem. Seemed a bit hard for its position.
  • B: Nice easy problem.
  • C: I don't see the point of this problem. Giving numbers instead of zeroes and ones does not make any sense. The problem is very standard. I did not even try to understand what are the "winning pairs", just wrote a dynamic programming solution since the constraint on $$$n$$$ is really small (I suppose that $$$n$$$ is left small on purpose, and I assume that the problem can be solved in $$$O(1)$$$ for any $$$n$$$ up to reading the input). Felt very easy.
  • D: Nice problem. I misread it and solved a different one. Both the alternative one and this one are cute and clean.
  • E: Boring. Immediately after reading the statement I knew how to solve it, there is not even a tiny bit of idea here, it's just about not doing a mess with indices. Did not like solving this one. It seemed very easy for its position.
  • F: Ok problem, easy for its position. It's not particularly interesting but it is clean and easy to implement.
  • G: Wonderful problem. Solving this one (which required me half of the contest) was very satisfying. From the very beginning, I thought that the number $$$(n-k+1)^2$$$ had to be special in some way. And in fact it is:if one is allowed to delete $$$(n-k+1)^2-1$$$ cells then the answer is always impossible! After that, I still needed to think a lot in order to conclude. Making sure that the $$$k-1$$$ antichains are "disjoint" was the hardest part for me.
  • H: Not read.

I loved problem G, while I did not enjoy solving the previous problems as it was just speed-solving without thinking. The contest was well prepared and the statements were clear. Thanks to the authors!

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

    How did you end up making sure the antichains are disjoint in G? I read the editorial but it seems to go in a different direction...

    Edit: I read your code, looks like the key is doing this to the input:

    for (int i = 0; i < k-1; i++) for (int j = 0; i + j < k-1; j++) {
            a[i][n-1-j] = 0;
            a[n-1-i][j] = 0;
        }
    

    It's easy to see that this transformation is valid (because no k-increasing sequence would ever use those elements anyway), but it's very interesting that after doing this the rest just "works".

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

      I want to confirm that your interpretation of my solution is correct. I am proud of it, it felt magical when I noticed it.

      Let me remark that those cells (the ones set to 0 in that for cycle) cannot be deleted, otherwise there will surely be a $$$k$$$ chain. So any solution will not delete them and therefore it makes even more sense to make them undeletable.

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

I suggest problem A in contests (other than div1 contest) should be at very easy and friendly to all the newbies and incomers, this contest problem A is too hard for its position.

Because if a contestant do not make any submission, he will not included in official table. If problem A is too hard, many newbies will quit and not included in the ranking table, and this contest will become another "div1" contest, only strong contestants participate.

However, it is more difficult for a contestant to gain rating in a contest surrounded by strong contestants, as I discovered in one of my blogs, it is not good for a weaker contestant who want to challenge him(her)self.

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

As an ABCDEFG solver, almost all problem was typical and needed at most one idea, but sometimes participating in such a contest is not always bad. (Though it's right that this contest isn't likely a Global Round)

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

Logic I have used : if Alice Can take even number of odd elements he wins! What's wrong in My logic? 174123447

int n; cin>>n; int o = 0; for(int i = 0; i < n; i++) { int x; cin>>x; if(x % 2)o++; } int k = o — (o / 2); string ans = "Alice"; if(k % 2)ans = "Bob";

cout<<ans<<endl;

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

    you are directly considering that alice can take all the numbers he wants at a time but that is not the case they have to play alternatively selecting only one number at a time.

    consider case

    1

    1 2 3

    o(odd numbers)=2;e=1;

    as per your solution alice selects one odd number now o=1;e=1 . now if Bob selects the remaining odd number alice will lose but as per your logic alice wins.

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

Hardest Div.2A I've ever seen... 174095886

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

Very strong indeed.. A was hard, tough contest.

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

In problem E, I thought for a lot of time that there may be negative numbers. Is it solvable in this interpretation?

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

    It seems at least as hard as counting common subsequences in two arrays. Is even that solvable in subquadratic time?

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

Many failed system test in B

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

FST... So many FSTs in B...
(@Successful Hackers: what's the key of distinguishing correct solutions and wrong solutions in B?)

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

    (-1)/2 == 0 in C++, but many contestants do not understand this...

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

      IMO, rounding towards zero in C++ is well-intended (It has multiple reasons including consistency and performance), but evil at the same time (most of all, it is counter-intuitive!)

      upd: This behaviour is also the reason why negative modulo happens on C/C++. It has persisted since C99, and while I think it should change, I guess it won't for a few years at least.

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

        C++ has zero-overhead philosophy. And this is how division works in cpu. So it will never change in c++

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

        What happens in python can you please explain

        They did not have to care about thia why?

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

          Python uses floor division for integer division, and the modulo is always positive. That's one thing I like about Python

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

      It's more about forgetting about negatives than not understanding this

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

    Probably not handling $$$k = 1$$$, also something like this works incorrectly with negative numbers:

    int threshold = a[n - k + 1] / (n - k + 1);
    if (a[n - k + 1] % (n - k + 1)) {
      ++threshold;
    }
    if (a[n - k + 1] < threshold) {
      cout << "No\n";
    }
    
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The limit for the original array element at the (n-k+1)th index. Many messed up trying to find this

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

    that's why one writes a * b <= c instead of a <= (c + b-1) / b D:

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

ABC are straight forward annoying casework shit. I would call these problems more or les heavy implementation.

D is greedy.Imagine the blocks <= k or > k can be like 000011100011 and figure out the last one from there.

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

Epic pretests for problem B, thank you!

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

F (and maybe G) is(are) awesome. But C, E (and maybe H) are shitty casework / Chinese-styled problems.

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

Problem E is very boring and complicated to implement.

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

    I don't see any submission from you in this contest, Have you participated with alt account?!

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

unaddictive contest

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

I'll try to start a new trend of "as a tester" comments. I would like to share my feedback that I have sent to the coordinator after testing. I don't know if it was passed to the authors, but I can see that the changes I proposed were not made.

A, B: I guess they are fine, I don't really like either, also I think that both of them are too hard for div2A, and A is a bit harder than B in my opinion
C: I just don't understand why this problem exists. I assume there is $$$O(1)$$$ solution (once you know number of even and odd numbers), but why would I think if there is an obvious $$$O(n^2)$$$ dp? why are there negative numbers in input? just to trip people who will check parity as x % 2 == 1 ? that's just bullshit
D: the hardest part is just reading the statement, even though I think that my solution is overcomplicated, because standings say that it is much easier than E and F, while I think it is harder (?). also it is kinda weird that finding k and finding the permutation is totally independent (in my solution at least). the problem is ok though.
E: super obvious combinatorics, the problem is kinda ok for div1A maybe, I don't get why testers are struggling
F: nice problem, although it is weird how simple the solution in the end is
G: I like this one, I know that it is from Anton :) I don’t think it’s anywhere close to div1D by difficulty, but fine
H: "write eertree on queue", wow, such problem. I think that there is eertree on dequeue, so it's not like it's something groundbreaking. and TL is just insane. my $$$O(q \log q)$$$ is right on border, either allow it freely or disallow it, but I think it is a bad idea to cut off $$$O(q \log q)$$$

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

    What's the O(1) solution for C?

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

      Who wins only depends on (number of evens) mod 4 and (number of odds) mod 4.

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

        Only the parity of the number of evens matters.

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

    I did the O(1) solution for C but I am gonna fail system tests because of negative numbers its so frustrating

    UPD: I don't know how but it passed system testing

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

      if(arr[i]%2!=0)

      you seem to have won the coinflip^^

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

    Well, if C needed O(1) you could still do n^2, print table and pattern is very clearly visible, so i think not asking for it is a good decision

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

    Completely agree. I also don't like A, B, and C which are the three that I solved. B had extremely weak pretests too, which made me FST.

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

    I also felt D is really hard. Not sure why so many people solved it

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

    G didn't exist when I tested, and it is nice, so it must be from Anton :)

    Also E was H when I tested (there were 9 problems), authors' and/or coordinators' sense of difficulty must be quite off.

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

    You are the only tester who passed all problems, and had a chance to win this round if you were not a tester. Of course you deserved to write down any comments you'd like.

    Get used to your impoliteness and arrogance as always.

    Anyway, the following is just to say something you might have ignored.

    C: Yes, it is obvious that I've already known there are two approaches. But you never tried to have think why I determined to make two possible approaches both pass. To you, either approach is obvious and may be boring. I want to ask: is there really a huge difference for you high-rated guys if only $$$O(1)$$$ solution is allowed?

    It seems you are complaining not large enough constraints, and you think it is good to make higher constraints.

    If this is Div1 only, of course I will do so. But you never know (at least forget or pretend to forget) what beginners really need. Do they just need to train case works? You can check many comments on how they loved and what they learned from this DP to pass, see 1, 2, 3, 4, 5.

    For checking the parity, that is also what beginners need to learn, and they did appreciate it.

    To you, these features are nothing. But please put away your arrogance in your own world, and see my comments on H below.

    H: Wow, this time you turned your attitude 180 degrees? Let me repeat your arguments to fit in H.

    I just don't understand why your $$$O(n \log n)$$$ solution exists to pass. I assume there is $$$O(n)$$$ solution (once you see the constraints are so large and TL is so tight), but why would you think your $$$O(n \log n)$$$ can pass naturally? Just to trip people who only know fast $$$O(n \log n)$$$ solutions, that's bullshit.

    The better way is to only allow $$$O(n)$$$ solution pass and let $$$O(n \log n)$$$ fail. But this time, it seems you are complaining not small enough constraints, and you think it is bad to make higher constraints.

    So where is your arrogance? You are expected to solve it $$$O(n)$$$, not sub-optimal things. Why did you stop your step?

    The only reason is that

    1. You know better solution to problem C.

    2. But you don't know better solution to problem H.

    That's it. So you wish to make problem C harder so that you can pass without pain but wish to make problem H easier so that you can pass without pain.

    Don't forget that:

    1. Problem C aims to let beginners learn more.

    2. Problem H aims to let high-rated coders like you learn more.

    If you did not pass problem H in testing round, I definitely you would shut up your mouth saying that problem H it's not groundbreaking and TL is just insane.

    At the very last, I am not an impolite person as you may see. When beginners are rude to me, I know they do not fully undertand the meaning of some problems that trouble them. But for you,

    1. You deserve to be treated rudely by others, as you always do so.

    2. Really shame on you, on your behavior, and on your ignoreance!

    The last of the last, thank you very much to test our round and give useful feedback. It would be better if you could raise your comments more smoothly. Looking forward to seeing you in the testing round, and leaderboards, in the future, my dear!

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

      Stop crying, just take your L. I have some tissues here in India if you want.

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

      Wow. What the fuck is wrong with you? I don't think that any of my comments were anything close to rude. Saying that your work is bad is not rude.

      Once again. Those were the comments I wrote BEFORE the round so that you could change something. I don't see where you found any arrogance or 180 turns. I didn't say that you should make problem C harder, I said that in the current constraints it is a bad problem. I didn't say that you should make problem H easier, I said that in the current constraints it is a bad problem. The reasons for that are different, yes. For problem H I literally say "either allow it freely or disallow it", because having reasonable solutions that seem to be fast enough and that are right on the border of TL is really bad. Yes, my opinion is that you should have let $$$O(n \log n)$$$ pass freely, but that is one of the options. I think that in the current state the problem is worse than either with higher or lower constraints.

      If you want to nitpick comments... I think that there is eertree on dequeue, so it's not like it's something groundbreaking.

      So, yeah, problem H is just shit, and your contest was bad, deal with it.

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

        Everyone knows your polite words, fuck, shit, bullshit. That's amazing. This is your upbringing yourself. Leave it alone anyway.

        To be honest, I was not aware of your feedback even before the round ended and I had nothing to do with it. Sorry if this makes you misunderstand.

        Another topic is about constraints. Could you explain why such constraints were bad more detailed? For me, I don't think so. Rather, it was set deliberately by me.

        1. I don't know why (and I don't think) the constraints of problem C is bad, as I had already mentioned in my last comment.

        2. For problem H, I ever proposed this constraints and explained why to do so to everyone concerning this issue. This is because, as always, we allow sub-optimal solutions to pass just for kindness. As you can see, the TL of every problem is very far away from its intended solution. When you select an algorithm that can probably get TLE, you should take your own risk.

        Now consider your arguments to support your opinion that H is shit.

        1. I think that there is eertree on dequeue Why do you ignore the sentence "However I have never seen an implementation of it"?

        2. so it's not like it's something groundbreaking Why do you try to refuse groundbreaking by an $$$O(n \log n)$$$ solution?

        So is there anything other than arrogance in your conclusion?

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

          Yes, there's some truth to it. I won't argue that there isn't some arrogance mixed in, but setting constraints such that you allow suboptimal solutions to either AC or TLE by a slim margin isn't kindness, it's basically setting a trap for the contestants. It's also not unreasonable to expect O(NlogN) solutions to pass in 2s for N = 1e6, far from it, such solutions usually are fast enough.

          From your messages, you seem to be blinded by um_nik being um_nik and thus refusing to accept his (valid) criticism.

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

      thank you liouzhou_101 , i have figured out solving game problems using dp with the help of problem c. although it has taken more time i am very happy that i have came up with a new approach to solve game problems.

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

    Something about E, F and G.

    Indeed, among testers, the grades of E, F and G have very high variance, concerning their easy implementation. Every of them happens to be super-hard or super-easy to different testers.

    As you may see on the standings, our round is balanced concerning the number of people who passed every problem. So it's our honor to see that we ranked these problems in a right order.

    That means, you did not grade E, F, and G so accurate, but it's not surprising.

    Let the statistics speak for themselves.

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

      I mean, I just want to mention the slight possibility that the round appears to be balanced according to the number of solves, solely based on the fact that they were ordered this way to begin with? As such, many would've disconsidered to solve some problem during contest solely due to the pressure of not having solved anythinf earlier (and by extention, you'd think that the problems, the later they appear, the harder they get, so your bet is safer with the easier problems. Although this is a bad mentality)

      To futher argument this, today I was at school and the teacher assigned us to upsolve this round. For D and E, very few people caught on the solution. But at problem F, almost half found the solution in less than 20 minutes (in this time, some even implemented it)

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

extremely weak and poor test cases in B , is this a joke?

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

can anyone tell me what is room, is it just random members assign to every room? and changes in every contest or there is anything else

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

    " is it just random members assign to every room? "

    Yes and you can only make hacks on people in your room.

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

    Yes, contestants are randomly assigned to rooms. It's only relevant for hacking. If you lock a problem (only possible after passing pretests), you can view the submissions of others in your room for the same problem and try to hack them (construct a test case where you think their submission will fail).

    The rooms make the hacks more fair, since each person is visible from a relatively small pool. Otherwise, if anyone can hack anyone, then except for those near the top, the probability that somebody's submission would be examined by a hacker, out of thousands of people, becomes extremely small, and getting hacked becomes a case of extreme bad luck.

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

Nice B, awesome tests

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

I'm really disappointed with this contest. One would think that, being a global, problems would be great and well prepared. Well... A huge load of FSTs in B and in problem C I still can't figure out why would you include negatives, it doesn't affect the problem and can make people have WA if they do x % 2 == 1 to check if number is odd. Ideas were cool, but bad round in general.

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

    Yes

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

    If you experienced global round many times, you will never think like that. A global round always taught in a painful way.

    And I don't know why many FSTs of B matter. Making strong pretests is obviously good to participants, but it is not mandatory. Sometimes FSTs are needed for participants to implement more error-freely and accurately. This time I failed D in system testing, but I don't blame setters.

    FST means that a participant wrote wrong code, so that participant should be held accountable for the wrong code. But I often feels this fault is completely overshadowed and only setters are blamed. Isn't it?

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

Testcases for problem B sucks, or maybe the problem itself!!

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

    same like Educational Codeforces Round 136 problem b also. really very bad contests

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

What a tough contest!

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

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

Weak pretest for problems B and D, also description for D, E, and F can be better.

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

Can someone explain to me how the non-DP solution works for C?

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

    It's some caseworks. Let number of odd and even numbers a and b. Answer only depends on a mod 4 and b mod 2. If b is odd, Alice loses when (a mod 4==2) and wins else. If b is even, Alice wins when (a mod 4 == 0 or 3) and loses else. Proof is not so hard, so I recommend you to think about it:)

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

Why was there no pretest for max value = 2e9 in B((((

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

what the heck is there in testcase 36 in question B can anyone tell the corner case?

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

    Oh my gosh you didn't type return after the if statement that checks if the dp value is already calculated. So the pre-calculated values always gonna be recalculated. What a sad mistake

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

      Lol...Thankx

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

        I strongly recommend using -Wall -Wpedantic flags when compiling your code.

        In this particular case you'd get


        > g++ -Wall -Wpedantic a.cpp a.cpp: In function ‘int DP(int, int, int, int)’: a.cpp:37:60: warning: statement has no effect [-Wunused-value] 37 | if(dp[even][odd][turn][sum]!=-1)dp[even][odd][turn][sum]; | ~~~~~~~~~~~~~~~~~~~~~~~^
»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Thanks for the k=0 in problem D that takes away my LGM.

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

How To Solve C in O(1) ??

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

My solution for E:

Firstly,consider a special case:there's no zero in array $$$a$$$.

We notice if we put a "partition" between $$$a[i],a[i+1]$$$,we must put a "partition" between $$$a[j],a[j+1]$$$ as well,where $$$(a[1]+...+a[i])=(a[j+1]+...+a[n])$$$ (except the "partition" in the middle).

In other words,the "partitions" are in pairs.So the answer is $$$2^{k},k$$$ is the number of pairs.

Now let's consider an array $$$a$$$ including zeros.

Remove all zeros from $$$a$$$,we get a new array $$$b$$$.

The same as the special case above,if we put a "partition" between $$$b[i],b[i+1]$$$,we must put a "partition" between $$$b[j],b[j+1]$$$ as well,where $$$(b[1]+...+b[i])=(b[j+1]+...+b[n])$$$.

Because there're zeros,the situaion is a bit more complex:

Assume there're $$$x$$$ zeros between $$$b[i],b[i+1]$$$ and $$$y$$$ zeros between $$$b[j],b[j+1]$$$,the number of plans to place "partitions" is:$$$ \Sigma^{min(x+1,y+1)}_{i=0}C^{x+1}_{i}C^{y+1}_{i}$$$.

Take care of boundary conditions:

-all numbers are zeros

-the array has zeros at both the beginning and the end

-the "partition" in the middle

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

wtf is B maintest 36?

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

    do you know what is even worse? failing on main test 48.....worst contest for me till now.

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

      that would be yesterday and today both for me, sigh wud have been 1350 by now if yesterday and today both didn't fst, and now I'll be 1100

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

Why just why :(

It was last minute I couldn't fix it.

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

    Naturally, as there's not much points expected in hacks nowadays, people start reading when they think they don't have the time to solve the next problem.

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

      Oh that makes sense now, because most of the time you have 10-20 extra minutes after solving last problem so you spend it on hacking :D

      Thanks for explaining.

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

Div 1.000002

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

how to solve C through Dp?

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

    For every move player will either choose a even or odd number (offcourse only if they are present)
    At the end if alice has even sum then he wins otherwise Bob

    There are basically 3 dp states
    1. Number of even numbers
    2. Number of odd numbers
    3. Parity of alex's sum

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

    Check CSES removal game, DP solution is based on that only imo

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

C was not a good problem. It was more like writing all test cases and coming up with a solution.

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

    I did something quite similar to that

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

    Except it was not the intended solution...

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

    Back in my days (~5 years ago), green and blue people wouldn't call out the problems as good or bad, unless there was some unavoidable issue like wrong test cases or ambiguous interpretation.

    Things seemed to have changed over the years... ( some other comments are there on this line as well )

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

Second problem pretests have extremely disappointing quality ^(

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

B's pretests are weaker than my sperm quality.

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

    Instead say "B's pretests are weaker than my jokes quality"

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

      My sperm would still be weaker.

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

Inviting low-rating testers is also a very difficult problem for me, because among my good friends, there are very few low-rating testers, but I still think that every contest should try to invite some low-rating testers. For a contest In other words, this can avoid a lot of problems.

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

    There are probably plenty of greys, greens, and cyans that are devoted to programming and would love to test a round(myself included). However, most of them cannot test because they generally are not very close friends with any problemsetter. Problemsetters are generally high rated, and correspondingly most of their friends are probably rated fairly well.

    That is why I propose making the tester role more open. Obviously, I get that it may be weird to have some stranger critiquing your problems, but you get a completely new viewpoint which could improve round quality in return. For the record, I'm not suggesting giving anyone who wants to test the round a tester role, as it's a big responsibility, but I think problemsetters should consider, "Hey maybe I don't know this person, but they seem like they can provide valuable, constructive criticism for their level."

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

      If anyone wants to test our round, there are two steps: 1. Add my discord, it's easier because I don't reject anyone. 2.Become good friends with me,It may be difficult, because I need to know you very well. I will not invite anyone to take the test, and most of the testers in our round are invited by aquamoon.

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

I am glad I did well in this contest. This was a harder contest as usual and even as a pupil I was able to answer the first three questions. I am also really glad I was able to find the dp solution for the game-theory question (not sure if it was second or third question. I think it was third), although implementing the solution took me more time than it should have as I ran into a lot of problems. If I implemented the solution more efficiently, who knows, I may have even solved a fourth question, given I had 45mins after I finished the third question.

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

omg what's wrong with 300iq How did he drop to master

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

    300iq, I also wonder.

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

    I haven’t done any competitive programming since 2020 :) I’m a bit rusty now, as I’ve spent this time learning math and working in cryptocurrency/finance sphere instead.

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

why are you asghar?!

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

I cannot understand why this blog gets many downvotes.

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

Guys, what's happening? Why is this blog so heavily downvoted?

Subjectively, there were some problems with this contest. Personally I didn't like problem D much, because after deepening down I felt like some trash scene is taking place in my brain. Many people constructively criticized it, I mostly agree. But it has a strange property because of which many people had suffered from the problem: you can either find the key to solving it, and then this is a straightforward implementation, or you can wander in vain and get frustrated. I am not sure whether this property makes the problem bad or not.

Also, as -is-this-fft- said in a comment, the distribution of problems' complexity turned out to be a bit flat. I kinda agree, but, firstly, I don't agree that B is somewhat similar to CDEF in terms of hardness (it's way easier), secondly, the solution of C only relies on careful cases considering, so it is also noticeably easier than DEF. As of DEF, they are of nearly equal hardness, and maybe for me D was even the hardest among them.

Some comments denounce problem H because it is way easier to solve if you have solved some other problems in the past. Sorry, I did not even read problem H (and didn't read the problems that are similar to problem H due to the commentators), so I cannot really say anything constructive here. But basically it is OK that experience matters, and acquaintance with some techniques which are not too common helps much with participating in the contest. For example, often in math problems (and in those programming problems which are essentially mathematical) I make some conclusions in mere seconds where some other participants might spend minutes, and this is not because I am very smart, but rather because I've seen similar concepts several times in other problems. And this alone doesn't make the problem bad, and in such situations I don't run into the comments saying than problemsetters do their job poorly.

Some comments state that the contest was too Chinese, but this is also a bit subjective. I didn't feel that it was outstandingly Chinese. Yes, one had to write some code to get AC, but in my eyes this doesn't destroy the fact that most of the problems contained some beautiful ideas or were themselves questions of interest.

A comment said that the statements were too hard to comprehend, but I didn't notice it. Oppositely, I'd say everything was crystal clear to me.

Some comments said that the pretests are weak, and this is not really nice, but it's participants' task to check their solutions during the contests. Any assumptions that you make on the quality and content of pretests, you make at your own risk!

Some comments say that the contest was too hard, but come on guys. This is not even an excuse for people who participated poorly in it (because even if it was hard, it was hard for everyone), not to say this is not a flaw of the contest or mistake of the problemsetters.

My point is that all aforementioned issues are totally minor, they don't crucially spoil the contest! There weren't any failures during the contest, problemsetters definitely did their job very well. Not to say that no problems were stolen and the contest wasn't made unrated.

Damn, why do they have -156 on the announcement? They definitely didn't deserve it.

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

    I guess too hard A and weak pretests on B led to many newbies' and pupils' performances to catastrophe and their frustrations are expressed through downvoting (a participant who attempted only 1 or 2 problems out of 8 also have 1 vote).
    But I agree that this contest is without wrong statements/solutions, long queues, plagiarism, or any other heavy troubles and concluded with success.
    I'm sad with the round is overblaming because this situation may cause demotivating future problemsetters...

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

      Never mind. It doesn't demotivate me at all.

      As a problem setter, it's more glad to see you guys evaluate the round by comments so that I will know how to make a round better, rather than a useless contribution. Also glad to see you think this round was a success.

      By the way, CF is used for learning and discussing. I believe those beginners who downvoted this round will eventually realize how they've learned if they are progressive, and that's enough. Who cares those know nothing but blame.

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

        Never mind. It doesn't demotivate me at all.

        Well, it doesn't demotivate you, but it definitely demotivates others. As time goes on, I feel less and less motivated to set problems for Div. 2 after seeing how every minor issue is treated by that part of the community.

        I've never set problems on CF, but it feels less and less likely that I will unless they let me set a Div. 1 only round.

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

    I might be partly responsible for that, and I'm sorry. I just don't consider contribution on CF an important number.

    But yeah, downvoting the announcement is not cool. They provided a contest, it wasn't very bad. It wasn't good either, but that's ok, not everything is good.

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

      I got some fun reading the comment by kristin_karoline saying that you attacked the blog with a bot farm. You definitely have nothing else to do Friday evening.

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

        Well, he obviously didn't bot, but it seems completely plausible that a lot of greens and greys saw his comment as validation and downvoted the blog.

        Still I wouldn't blame him, it's not his responsibility if others behave irrationally after reading his comment.

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

          While I also wouldn't blame him for just saying out his opinion on the contest (however, I really didn't like Um_nik criticizing the round before its ending), I guess influencers (like top-10 on Codeforces by rating or by contribution and other people who have a large audience) do have some responsibility for what they say and what they do. Each their action may result in some social response, and they should at least recognize their possible impact, what Um_nik did.

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

    As a tester, I tried my best to make this round better, although in the end I failed, unfortunately. But liouzhou101 and his friends are great writers, I hope you can give them more support, they will do better next time, instead of meaningless downvotes, next time maybe I will help earlier, this time is a bit late . As a tester, I like the personality of um_nik who dares to tell the truth, but I will not express my true opinion on the problem in the comment area of cf.

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

    It always seems to happen. Whenever there are some legitimate complaints about the round, it feels like an army of people see it as validation for "the round is bad". But the round wasn't bad. It was mediocre, perhaps, but not bad and doesn't deserve negative votes.

    In particular this round had weak pretests. I don't see anything wrong with that, pretests are a part of the contest format. In recent years, pretests have gradually become stronger and stronger. This has led to many people expecting pretests to always be strong and see weaker pretests as "the problem was poorly prepared, the contest is trash, the setter is probably an idiot". If I recall correctly, originally pretests were only meant to be a slightly less feel-bad variation of the TopCoder system, where the only pretests are the samples and you can even submit without passing them.

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

    While I can agree with the sentiment, I think some of the issues are more serious than you're describing.

    I have heard of several people that understood D incorrectly and wasted several minutes by solving the wrong problem, so calling the statements crystal clear is just patently false. Obviously this hurts the competition and to me might be the biggest issue with the round.

    The problem with the pretests is not only having extremely bad pretests -- it's why include the corner case in the first place? Why give negative numbers in B and C? It doesn't make the problem more interesting in any way, it's just a "gotcha" to fail people that forget an obscure detail of how their language works.

    But bad pretests do make a contest significantly worse by allowing hacks, which are an extremely unfair mechanic. Participants are divided in rooms randomly, and you can only get hacking points based on how many people in your room made a mistake and if you are the first person in the room to start hacking. Also, if you get hacked, you get extra information that people who were not hacked do not have. Furthermore, if your point is "you shouldn't assume anything about pretests", then what is the point of having them in the first place? How much testing should you do, when you have absolutely no information on the pretest contents?

    The flat difficulty gradient is a trend with recent rounds and there have been several blog posts complaining about it (having fewer problems is fine!), but this contest is definitely not the only one to suffer from that particular problem.

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

What's the formula of calculating which people get T-shirts?

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

I have been accused of cheating for problem B submission. I am sharing the pair of submissions which, according to the system message I received, "significantly coincide": 174109848 and 174107830.

Clearly the 'solve' function which implements the logic for the problem is completely different. Both codes have different space efficiency and even the method for implementing the logic is completely different. However, the basic template that has been used by me and the other guy is same. I don't think it is fair to accuse someone of cheating and penalizing them because the template matches which is clearly written before the contest starts.

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

1st question of this contest wasn't that much easy as compared to other codeforces contests 1st question

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

When will the list of t-shirt winners released? KAN, antontrygubO_o, liouzhou_101

»
2 years ago, # |
  Vote: I like it +71 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 1738 1 cnnfls_csy
2 1738 2 ksun48
3 1738 3 maroonrk
4 1738 4 orzdevinwang
5 1738 5 ko_osaga
6 1738 6 tourist
7 1738 7 jiangly
8 1738 8 noimi
9 1738 9 peti1234
10 1738 10 Maksim1744
11 1738 11 WYZFL
12 1738 12 QAQAutoMaton
13 1738 13 skip2004
14 1738 14 Golovanov399
15 1738 15 Ormlis
16 1738 16 dreamoon_love_AA
17 1738 17 hos.lyric
18 1738 18 asdsasd
19 1738 19 A_G
20 1738 20 tute7627
21 1738 21 pigstd
22 1738 22 Nachia
23 1738 23 tabr
24 1738 24 physics0523
25 1738 25 Pyqe
26 1738 26 feecIe6418
27 1738 27 NeoOrgano
28 1738 28 SirShokoladina
29 1738 29 dario2994
30 1738 30 milisav
43 1738 43 hank55663
75 1738 75 qwerasdfzxcl
106 1738 106 Kevin114514
135 1738 135 antekb
239 1738 239 QwertyPi
284 1738 284 CartesianTree
296 1738 296 Juanzhang
299 1738 299 cxm1024
307 1738 307 mazihang2022
313 1738 313 Soetdit
330 1738 330 zmj2008AKIOI
333 1738 332 stefanbalaz2
344 1738 344 Cocoly1990
384 1738 384 al3xstr33t
404 1738 404 ssamt
456 1738 456 Kano
467 1738 467 ivan2023
485 1738 485 tfg
489 1738 489 alexchist
490 1738 490 The_Hallak