waaitg's blog

By waaitg, history, 2 years ago, In English

Hello, Codeforces!

Imakf and I are glad to invite you to Codeforces Round #808 (Div. 1) and Codeforces Round #808 (Div. 2), which will take place on Jul/16/2022 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours to solve them all.

We would like to thank:

Score distribution will be announced before the round.

Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)

UPD1: Score distribution is

Div 2: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$

Div 1: $$$500 - 750 - 1250 - 1750 - 2500 - 3250$$$

UPD2: Editorial

UPD3: Congratulations to the winners!

Div 1

  1. Isonan
  2. djq_cpp
  3. tourist
  4. jiangly
  5. Um_nik

Div. 2

  1. _WidowMaker_
  2. N193r
  3. Ayaka_s_Dog
  4. PaiGuChicken
  5. NothingOccurred
  • Vote: I like it
  • +280
  • Vote: I do not like it

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

1-gon 可爱 1-gon cute.

Hope everyone enjoy the round.

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

    Imakf is very cute.(:

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

    Imakf is very cute :)

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

    Imakf is very cute.(:

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

    I hope that today's tasks will be interesting and good. Let's try to solve more problems. Good luck!

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

    I really like the Codeforces competition. Hope you like it too. After all, this is a great opportunity to test your knowledge and experience. This will help increase our Knowledge. I hope this competition will be great for everyone!

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

    Problem C was amazing, just look at the number of ACs, 2k managed to solve out of 13k, good contest!!!

    We should have more of these.

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

Expert, I'm coming. EDIT : it came true

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

Can't wait to see PinkieRabbit's performance!

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

Thank you for the great round!I can't wait to try my best to solve the problems!

And hope seniors can enjoy their university lives in the future!

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

As a tester and a fan of cute Imakf, love the round so much!
Hope everyone enjoy it!

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

    As a tester, I disagree with this part of the announcement:

    Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)

    Historically, that almost certainly means us testers made a mistake or there's a CF meltdown and the round becomes unrated.

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

    As a contestant, I don't believe testers anymore.

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

In the last round, I passed three questions and I hope I can reach 1200 points in this round.

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

Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)

hope so (XD)

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

Hopefully I don't lose expert.

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

    Same! I also just recently got it, we are living on the edge here. Good luck!

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

      yeah you too man.

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

        Well, that definitely didn't go very well... I'm lucky I won't drop to Pupil after this round.

        Guess these will be my last words as an expert in the foreseeable future :/

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

          Same man, I think I've got a valid sol for C (after the contest!) I got seriously unlucky lol.

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

            I feel you. It's funny we fell down to very close ratings too. Better luck to us on #809 I guess. The journey back to expert begins!

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

              yes imao. Time to start upsolving!

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

    Hopefully I don't lose CM

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

Respect smg23333!!!!

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

Wish you all wouldn't gain negative ratings in this round!

So this is unrated?

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

One of my curious questions: How to become a Codeforces Round tester? Sounds interesting

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

    You have to get invited by the writers

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

I can't wait to see jiangly's performance!

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

Today is my birthday. Hope this contest is as special as my birthday

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

respect++ for smg23333

You can take away my house, all my tricks and toys. One thing you can't take away, is my csgo time. ~ Iron Man
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It says it is theoretically possible that no one gets negative rating.

Someone knows how?

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

    The scoreboard has participants with non-increasing order of rating.

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

photo-2022-07-16-16-43-46

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

wana to be a Specialist ... ovo ...

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

Deleted

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

Deleted

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

Is there a way to find out if a specific user is registered for a contest (before the contest begins)?

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

    Add the user to your friends' list, and see all your registered friends. I don't know a better solution lol

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

      Yes, thanks, I didn't know about the registrants page!

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

let's see how bad I'm going to do after solving only 100 problems this year and the last submission was more than 2 months ago and the only algorithm i still remember is implentation

Edit: Well I started with C and it was a bad plan

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

Is this div.0?

I've checked the title of this contest for 3 times, I think this is div.1 but the problems are more like div.0.

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

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

"Wish you all wouldn't gain negative ratings in this round!" Wow!! I think all will gain negative ratings in this round XDXD

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

It just feels bad when i am a second year CS university student and can't solve A.

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

    oh, I thought I'm the only one who can't solve A problem, it's hard as """"

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

God, I felt so useless when I took that much time to solve A with solid proof, until I saw comments. Feeling so idle in this contest :)

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

Can't solve 2C. Lower rating :(

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

I don't know why my codes for A,B are WA

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

One of my worst contests ever! I will never join Chinese contests again.

The contest is not balanced. The last Div2 round was very balanced but this contest is just a fast coding contest with some sh!t.

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

    It doesn't mean all Chinese contests are like this one.

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

      I hope so.

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

        What are you saying. If you solve the problems normally, the round will be cool. The problem is not in the round, but in you. It's not speedforce. I agree, maybe we need to swap A and B, but no more!!!

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

    Why do you think so? I also think this round is not good enough(Exactly last round too),but it is absolutely not a fast coding contest.

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

From Newbie to Pupil to Specialist to Pupil to Newbie. What a Journey :)

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

There is a big gap between B and C

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

I am that point when there is nothing left to think about A, B, C

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

Every time a problem with '0' and '1' appears in a contest,

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

    I can say same thing for me, but with $$$l$$$ and $$$r$$$, even though I solved B today.

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

    Also when there is bitwise XOR or something like that

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

I can feel what Doremy is going through :(

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

Can someone give me a hint for Div2D?

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

    Note that there are always a lot of duplicates in the array

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

    The process converges very quickly to all zeros because the number of distinct differences is $$$O(\sqrt{M})$$$ where $$$M$$$ is the largest element in the current iteration.

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

A) Prove by AC, somehow works. Spent 20 mins on it, thought about rage-quitting without making submissions because it seemed like I won't be able to solve even A or B :lol:

B) Until the very end of the round I was convinved all elements also have to be distinct, so had no idea how to approach it and solved it only at the very end

C) Prove by AC, no idea why it work and whether it really works or problem just has bad pretests

D) A bit of reasoning lead to solution convincing enough. Quite a cute problem. Logic seemes easier than A/B/C

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

    Can you please explain your reasoning for D. Thanks

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

      It is pretty much above

      Note there cannot be many unique values in the array

      Think how to avoid useless computations, repeating values don't add much new. They add zeroes and further zeroes again produce zeroes

      So you just keep track of the number zeroes and observe how the process quickly converges on all the other values

      Well, that's the idea.

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

    Same lol for B

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

D1B editorial. Also it's my only authored problem lol.

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

"Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)", That's when we should have known that the contest would have been a disaster.

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

For Div1C, is this wrong or does my implementation just suck?

Let T be the MST of the graph. Since edge weights are not repeated T is the only MST.

Then a root R is good if and only if for all edges (u, v), at least one of the following hold:

  • (u, v) is in T

  • When T is rooted at R, u is an ancestor of v or v is an ancestor of u.

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

Pretty brutal contest. Very humbling, can't wait for the editorial.

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

Whats wrong with my code? am using PB_dS with reverse traversing and putting max value + 1 every time i check more than q

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

Div 2 A is trash

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

POV: no one can feel my pain The pain: 8 wrong submissions in B

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

    maybe u were thinking like me to put diff values in diff places :( 1 wrong submisson

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

    In Global Round 21 I did 12 WA on test 2 submissions.

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

Problem C is just like my friend. His name is Long. \

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

How can I pass problem 3?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How wrong is my solution for C ?
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Dear authors, shouldn't it be said in B that numbers can be equal? I love you very much, kissing you for the great time!

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

    or at least give a sample case where numbers are equal

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

    Well, it is our fault in a sense that we don't read statements properly. But yeah, they could make it clearer.

    Solved B only at the very end because of it

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

    I got 2 WAs in problem B because of this :')

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

    I did not solve the problem because I thought the numbers should be distinct. But that is my fault since it was not stated that they should be distinct. Even the examples did not have any equal numbers to make it clear.

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

No more algorithm-reading problems plz No more algorithm-reading problems plz No more algorithm-reading problems plz

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

Ouch, the power outage plus the problems were the final nail in the coffin for me.

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

Sorry to say but A, B and D are one of the worst problems I ever solved. C was pretty good though.

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

    It could have been much better if the authors asked just to output the number of solved contests, because then a DP approach with segment tree/SQRT-decomposition on top of it could work without greedy approach.

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

      Can you elaborate on the DP approach?

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

        Yes, of course. Let dp[i][q] be the maximum number of tested contests if we consider only first $$$i$$$ contests and after testing or skipping $$$i$$$th we have IQ exactly $$$q$$$.

        At first, let's solve in $$$O(n^2)$$$.

        for each i:

        1. $$$a_i \le q$$$. for each q, dp[i + 1][q] = dp[i][q] + 1.

        2. $$$a_i > q$$$. for each q, dp[i + 1][q] = dp[i][q], dp[i + 1][q - 1] max= dp[i][q] + 1.

        Let's note that in the second case dp[i][q] + 1 is always no less than dp[i + 1][q - 1], so we can replace max= with =.

        Okay. Now let's maintain the difference array of dp[i]: diff[j] = dp[i][j] - dp[i][j - 1].

        When we increase i, we simply need to

        1) add 1 to diff[a[i]], substract 1 from the last element of diff (this is the case $$$a_i \le q$$$

        2) set the prefix ending with a[i] to 1 (case $$$a_i > q$$$)

        This could be done using a segment tree or SQRT-decomposition.

        Because q cannot decrease more than $$$N$$$ times, we can keep just $$$N$$$ values of diff.

        But I don't see a way how to recover the answer...

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

      You can record the pos of the dp-ans,and then output answers according to this.

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

        Could you please elaborate on that?

        I've explained my solution here.

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

          Will,my dp solution is diff from yours XD

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

            Could you please explain yours?

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

              OK I just realized my solution may be not dp(although it is from dp sol), sorry :(

              I just do it from n to i.

              make c[i]=(a[i]>q)

              Notice that if c[i]=1 and i is picked,then all of c[i]=1 in i+1 to n must be picked. (When I didnt notice this I use simply dp to do it)

              set dp[i] as the best answer when you deal with i to n,and c[i]=1,and dp[i] can be claced by dp[nxt[i]] (nxt means the next 1's pos)

              Here we can use BIT or priority_queue to solve. Actually it is not dp eventually (I came up with it according to O(nq) dp sol).

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

div2c was binary search ?

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

what's wrong with this approach of Div2 C. Any counter testcase? It gives WA on TC 3

code

upd: got it

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

Did you guys use prime factors to solve problem B? Bruteforce just got a TLE

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

    Used simple math for O(1)

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

    You don't need any prime factors or anything like that. My idea was: the last element should be divisible by $$$n$$$, the second last should be divisible by $$$n-1$$$ and so on because $$$gcd(i, a[i])$$$ is always $$$i$$$ in that case. All $$$i$$$ are different so it is the correct solution.

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

      Yep. i got the same idea. But i was traversing [l, r] round and round to get the proper a_i which fulfills gcd(i, a_i) = i. And got a TLE

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

Problems are not bad, but the problemset is too hard :(

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

Congratulations, you're now officially interlude 2.0

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

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

Very INTEREST Round! I have never got the place on div2 before

pC is very nice

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

what a shame how could I miss such a cute contest! :,c

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

A was torture for me.

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

weak pretests and lack of explanation for problem B

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

About how my Div1D gets FST: somehow creating a vector and resizing a vector $$$O(n^2)$$$ times magically make my code 5x slower.

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

I was thinking C for more than 40 mins like what exactly I could do...just read the tutorial and found that it was an easy problem :). just didn't get the right approach:(

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

Ratings updated preliminary. As I said here: https://codeforces.me/blog/entry/104766?#comment-932270 cheaters will be removed later.

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

My submission for B no problem I can not find any test case that can fail.Can anyone help me with a failing case??

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

    numbers don't have to be distinct.

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

      ""such that gcd(i,ai) are all distinct"" Distinct was mentioned

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

        Dude gcd must be distinct but the ai can be the same.. suppose an array of 2 numbers 1000,1000 have gcd's with the index's as 1,2 respectively, gcd's are different here but numbers are the same:)...what I get is that u have encountered that ai must be different.. if that's not the case still finding the mistake:)

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

Thanks to this contest, I had become LGM!!!

appreciate very very much for writer and tester!

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

my friend:“Hello!” me:“How do u know I become a Expert?”

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

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

Fortunately I miss this round(I have registered but forget ha) Only 2k solved pC Are you sure this is div2???

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

Anybody knows the solution for B if all ai were to be distinct between one another?

(meaning that for any l <= i, j <= r and i != j: ai != aj)

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

candidate master, I'm coming :>

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

Please don't use questions from other websites . Question d of div 2 or question b of div 1 was previously asked in codechef starters 33. https://www.codechef.com/START33B/problems/ARRAY_OPS . This gives unfair advantage to those who have seen the question previously.

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

why my rating is rolled back which I gained after giving this contest any help