hugopm's blog

Codeforces Round #668
By hugopm, history, 4 years ago, In English

Hello Codeforces!

We are glad to invite you to Codeforces Round 668 (Div. 1) and Codeforces Round 668 (Div. 2), which will take place on Sep/06/2020 17:35 (Moscow time).

The problems were created by Ari, Kuroni, JettyOller, Monogon, antontrygubO_o and hugopm.

We would like to thank:

There will be 5 problems in each division and will be given 2 hours to solve them (or post memes in the comments if you can't solve any).

We tried to make interesting problems, short statements, useful samples and strong pretests, and we hope you will like it.

Scoring will be announced shortly before the round and editorial will be posted shortly after the round (it is already written).

Good luck!

UPD: The number of problems is now 5 in each division.

UPD2: Score distribution:

  • Div.1: 500 — 1000 — 1500 — 2250 — 3000
  • Div.2 : 500 — 1000 — 1750 — 2250 — 3000

UPD3: Editorial is out

UPD4: We are sorry for problem div1E being well-known. No setter or tester have seen this problem. We apologize and hope you still enjoyed the contest.

UPD5: Congratulations to the winners:

Div.1

  1. maroonrk
  2. ainta
  3. ko_osaga
  4. Itst
  5. hos.lyric

Div.2

  1. minhchauxinhdep1234
  2. potato167
  3. guangmutianwang
  4. w_o_kje
  5. veckoper
  • Vote: I like it
  • +1132
  • Vote: I do not like it

Comments Comments (289)
| Write comment?
»
4 years ago, # |
  Vote: I like it +694 Vote: I do not like it

hi

→ Reply
»
4 years ago, # |
  Vote: I like it +248 Vote: I do not like it

This is how the problems were created:

→ Reply
»
4 years ago, # |
  Vote: I like it +803 Vote: I do not like it

As an author of two div1s in a row, give me contribution

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Excited for this contest!!

→ Reply
»
4 years ago, # |
  Vote: I like it +78 Vote: I do not like it

AC round 4

→ Reply
»
4 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Hope for strong pretests.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +137 Vote: I do not like it

As a tester, I'd say the problems are really good. I wish everyone the best of luck and get a good rating after the contest!!

→ Reply
»
4 years ago, # |
  Vote: I like it +168 Vote: I do not like it

editorial will be posted shortly after the round (it is already written)

Codeforces should make it a rule for authors.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -173 Vote: I do not like it
    My thoughts about tutorials
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +66 Vote: I do not like it

      I think this totally depends upon the person itself, if they don't wanna see the editorial, no one is forcing them. But think about the the person who tried everything during the contest and wanna see the solution badly.

      In my opinion, it is good to have editorial as soon as possible after the contest is over.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -160 Vote: I do not like it

        ..

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -157 Vote: I do not like it

        ..

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

          No. We're downvoting because you are suggesting taking away our freedom of choice under the ridiculous pretense that you know better

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it -84 Vote: I do not like it

            I'm only putting my side

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

              nobody is stopping you from voicing your opinion, but if people think it's stupid, they'll downvote you lol

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

                they are downvoting me that's okay
                but few of them are being very personal with me that's where real problem begins

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

                  are people sending you personal attacks in DM or something? I don't think anyone would do that over something as insignificant as this

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

      Do not decide for me

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -58 Vote: I do not like it

        He can't decide for anyone , Open his profile and check the college he is from , LMFAO you'll laugh your azz out if you know the scenario of his college

        IIT Mandi , don't make me laugh , even the facchas from my IIT can do better coding than his CSE fourth years

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

          i can also say bad words about other people through memes and personal attacks
          but i am maintaining my well behavior in comment section till now i was just defending myself
          i don't understand why people are so much offended by opinion of just one person and can't let it go

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

      i think editorials should be posted next to next day after the contest

      Hmmmm..... Interesting

      You say that but ironically you commented on the editorial of Codeforces Round #665 within 30 hours of the contest itself ...

      Practice what you preach is all I would say

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

        Atleast read that comment carefully I had found mistake in my code on my own and then I asked for help in not repeating such mistakes
        And if you are that much offended by my opinion dm me I can explain what I am trying to convey here

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

          Well I wasn't hoping for you to understand my comment in the first go , I guess username checks out...

          It isn't about the comment , It was about the fact that you read the editorial within at least two days contradicting what you originally said ...

          Because if you commented on it , you must have clicked on it after reading EDITORIAL in the blog title , so much for the hyprocrisy of not going to the editorial within at least 2 days

          If you still didn't understand anything above (chances of which are very high ) , you can DM me I can explain what I am trying to convey here

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

            i had upsolved upto question D in that contest before commenting
            as a beginner i am not supposed to solve after that level as it will not be beneficial for me ( so tutorials turned useless for me as i was not going to solve after problem D)
            that's why i directly headed to solve my doubts in comment section

            and about the thing of atleast 2 days, here i wanted to say is if editorials are not posted for 2 days then people will be forced to solve problems on their own and this will train their mind to solve problems beyond their knowledge

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

              I like how you went from having an opinion of yours to making excuses for why you are a hypocrite in the same thread lol

              cyans be trippin nowadays

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 3   Vote: I like it -8 Vote: I do not like it

                atleast i am commenting through my original account and taking downvotes
                not like you
                fear of downvotes hh..
                and if someone is calling me hypocrite then i have to and i need to prove my point

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

                I like how you suddenly made it a rating dependent thing.

                Btw if you didn't know, CF rating ONLY determines the performance of people in CP contest at CF. nothing more than that.

                Also yea this guy first forces his opinion, then says it's just my opinion and also behaves hypocritically. It's hilarious

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

    That would be nice too. But actually I don't mind delay as long as they're well-written

    So I would prefer optimizing the quality of the editorials over the publishing time

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

      Well, I think the quality would usually be better if the editorial is written before the contest, without time pressure.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

As a tester, good luck!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +51 Vote: I do not like it

Ponies? Not again !

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I wish I'd become green after this contest

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

hugopm: "post memes in the comments if you can't solve any"

me: well, now I know that studying Paint is a good option :)

→ Reply
»
4 years ago, # |
  Vote: I like it -93 Vote: I do not like it

antOn in the list of authors? I suggest everyone to skip the contest

→ Reply
»
4 years ago, # |
  Vote: I like it +170 Vote: I do not like it

(Screen-Shot-2020-09-04-at-10.24.10-AM.png)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

Sorry, I sent it in the wrong place.

→ Reply
»
4 years ago, # |
  Vote: I like it +87 Vote: I do not like it

It's a risk I'm willing to take. ;-)

→ Reply
»
4 years ago, # |
  Vote: I like it -30 Vote: I do not like it

"gAmeGaME fOr 4lWayS B1enG NicE AnD SupPorTiVE."

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

    Obviously that was sarcasm. Gamegame is the most friendly and agreeable person I know, so to call him toxic is an instance of absurdist humor.

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

My school starts two days after the contest... phew

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

So many reds ,red means danger xD

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I am wondering who is the coordinator...

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Why ponies? I am very scared of them.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No round coordination?

→ Reply
»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Always Hope for the best. and May this round increase everyone's rating.

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

    increase everyone's rating

    This statement breaks rating calculation rules of codeforces.

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

      You mean, it's as unrealistic as "May Peace Prevail on Earth"?

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


        cout<<"Hello World"

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

        Technically it might be possible actually. If new accounts all do just slightly worse than expected, they will lose real elo, but still appear to go up because of the new system. That would allow the good people to be allowed to very slightly gain elo as well. So everyone would have a net positive delta.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      vivek1401 What if everyone comes 1'st?

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -24 Vote: I do not like it

I wish everyone a happy contest !

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

    Why do you have so many downvotes?

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

      Because he has changed the comment after he saw downvotes, you can read his previous comment.

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

i hope with this contest my rating will start to increase.previous 4 contests the rating is decreasing continuously

→ Reply
»
4 years ago, # |
  Vote: I like it +228 Vote: I do not like it

I'd like to take a moment to congratulate a special boy. Our genius leader who put us back on track whenever the future of this round looked bleak. Happy birthday hugopm!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh Yeah!

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

We tried to make interesting problems, short statements, useful samples and strong pretests.

It's so cute <3 <3

→ Reply
»
4 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Go check out my graph, who thinks this round is gonna take me to Expert?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems with short statements are relief for an idle like me...

→ Reply
»
4 years ago, # |
  Vote: I like it +79 Vote: I do not like it

As a tester I want my contribution :)

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

    Why do you feel the need to say something that contributes no tangible value to the community?

    Edit: I meant as a joke based on my hypocrisy of having made similar comments. I realize now this didn't come across. No hard feelings.

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

      My message was supposed to be a joke about all the testers like you who always ask for contribution :kappa:

      → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

USA Users, have a good contest on Labor Day.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

hugopm How many common problems are there?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Author: "or post memes in the comments if you can't solve any."

Me: "How to make good programming memes google?"

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  • Some good meme ;) *
→ Reply
»
4 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Please give me downvotes, Codeforces!

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

    Oh no, I expected everyone to do the opposite :'( Anyway, thanks for the negative :)

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -35 Vote: I do not like it

Div.1: 500 — 1000 — 1500 — 2250 — 3000 Div.2 : 500 — 1000 — 1750 — 2250 — 3000

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

    I'm not sure you know how score distribution works

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

      can you tell? :)

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

        Sure! The first thing is that you can't compare score distributions of div1 and div2. Also it just shows how much score you will get after solving the task

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

    Can you kindly elaborate on how you came to this conclusion great sir?????

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

    score != difficulty

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

    Score distribution of div1 500 is like div2 1500 or more. So, you can't compare these two.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so many reds. This contest is sure to have very good quality questions.

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Sliding through hilarious memes down here and forgot to register......

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Congrats maroonrk for his very first win xD

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

    Will only know for sure after system tests

    → Reply
»
4 years ago, # |
  Vote: I like it -33 Vote: I do not like it

speedforces

→ Reply
»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

C > D

→ Reply
»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Thank you for a very nice C.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess div1b is Monogon problem

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You really "tried to make short statement" in Div1D???

The interactive part is totally unnecessary: Let judge always give the array and let contestants just ignore it for the First case. You have written so in the Hack Format, why didn't you use it as the input for the contestant...

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

    We discussed making the format to 1D non-interactive in a few different ways. Ultimately we felt interactive was cleaner, though of course, you may disagree.

    For that format in particular someone raised the point that you could try to find a valid play as Second, and then if you fail, submit the same input as First. Of course, that's not particularly helpful given that the actual solution, but it felt somewhat weird.

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

      Thanks for the explanation!

      I agree with you on that "Which is cleaner" might be personal preference.

      I can't really agree on the second point because even in the interactive format the contestant could make some random partition to try and switch to First. Anyway I understand that it is somewhat weird, so, no clear conclusion...

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give some hints for D and E(Div1)?

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to hack B? I kept getting

Validator 'validator.exe' returns exit code 3 [FAIL Unexpected character #13, but ' ' expected (test case 1, stdin, line 3)]

My generator
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    You put n=100000 but didn't output 100000 numbers.

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

      oh no! don't know why i thought 5 + 5 * 10 ^ 4 = 10 ^ 5 :/

      → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

how to solve C? I spend 1.8 hour on this task(

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

    Same here

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

    You have to make the observation that for "YES" answer, s[i] should be equal to s[i+k] for all i.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    1. first k characters decide the whole string.
    2. all characters at i, i+k, i+2*k ... should be same. So if any one of them is set then set all others and if there are 0 and 1 both then answer is NO.
    3. There will be case where all i, i+k, i+2*k ... will be ?. In that case greedily try to assign it to 0 or 1 based on how many 0 and 1 are in 0 to k-1.
    4. If at the end number of zeros and number of ones in 0 to k-1 are not equal answer is NO else YES.
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hi, could you provide a proof as to why no Balanced String can exist with the ith character not equal to the i+Kth character? Thanks. Also could you tell me a little about the intuition behind your solution?

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

        from sliding window

        when you move from [0, k-1] to [1,k] then the a[k] should be equal to a[0] for the new subarray to maintain balance. similarly you can keep sliding all the way up to n-1.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • Try to satisfy $$$s_i = s_{i+k} = s_{i+2k} = s_{i + 3k} = ...... $$$
    • Try to make $$$s_{1...k}$$$ balanced
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same lol, finally went to D and was able to do it in 20 mins

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I missed some observation in 2C, 2D was simpler for me.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only one refreshing page for editorial :D

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will tutorial release?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Such a nice contest..

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hacks on D ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess I've forgotten a case in Div2D. Anyone has an idea of the solution? What I did: if distance between a & b is <= da, then Alice wins, if 2*da >= db then Alice wins, and then if the diameter of the tree is >= 2*da + 1 then Bob wins, else Alice wins

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

    Bob needs to reach a diameter endpoint without colliding with brurrito. I am not able to think of a case but that could be one of the things.

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

      Same bro, I made all other observations. But How I can be sure that Bob will reach on the diameter or end of it without colliding with Alice. How to prove this?

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

    If diameter > 2*da && db > 2*da && dist[a][b] > da Bob wins. Else Alice wins.

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

    and then if the diameter of the tree is >= 2*da + 1

    But what if db < diameter of a tree? It should be min(diameter_of_a_tree, db) >= 2*da

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

      Alice wins iff d[A][B] <= da OR 2*da >= min(diameter, db) But how to prove this?

      → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

When you submit the (what you think is) correct code ten seconds before the end but there's a last-minute compilation typo

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

imagine searching template (2SAT) on Anton's contest lol

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 2E/1C ?

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

    From left to right for each index i calculate maximum index L[i] such that you can remove a[i] if you only consider segment [L[i], i]. Segment is good if there is >= i — a[i] (you need to remove i — a[i] numbers from left to make a[i] = i) numbers that can be removed. Now answer on segment [l, r] is number of L[i] >= l from l to r.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure which case I missed in D. If the initial distance is <= da, then Alice wins. Then limit da and db to be at most diameter. If db > 2 * da, then Bob wins, otherwise Alice wins. Can anyone tell me what case I missed here? Getting WA on pretest 2.

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

    The case where 2Da >= diameter of the tree

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

      Why would Bob win that case? If db < 2 * da, then Bob will never be able to cross Alice when Bob is at the endpoint of a diameter?

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

        That’s what I meant to say, diameter can be a small number compared to Db. It can happen that Db is greater than 2Da but 2Da is greater than diameter so Alice will win but your code would output Bob.

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

          I did da = min(da, diameter) and db = min(db, diameter). Then the actual logic holds right?

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

            I think I found the mistake in your code. 

            da = min(da, diam);
db = min(db, diam);
if (2 * da >= diam) {
  win("Alice");
}
else {
  if (db > 2 * da) {
    win("Bob");
  }
  else {
    win("Alice");
  }              
}

            When you take the minimum of db and diameter, you are also incorrectly comparing db > 2 * da, Probably db was greater than the diameter and after taking the minimum, your db > 2 * da will yield a false value, incorrectly printing Alice, when it should have printed Bob.

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

              That's not the issue. The logic is correct. I haven't marked the root node in my BFS as visited. Unforgivable error ;( :(

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

                Yes, my bad. Looks like your logic was correct. Tough luck

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

    Find the diameter of the tree. If da >= ceil(diameter/2), then Alice wins since she can just go to one of the center vertex(es) and get Bob on the next turn since she can effectively go anywhere in the tree in that move.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E?

I know we can answer (if only one query) in O(n) by ans+=(ans>=a[i]) but idk how to answer q queries in time.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the proof that every s[i%k] should have same value in problem C ?

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

    Consider this: Every time you move to the next subarray, you are removing the first element and appending a new element to the end.

    If the current subarray is valid, the next will be valid only if the removed element is equal to the appended element, else the balance will be disturbed.

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

    Lets consider a subarray of length K, s[i], s[i+1], ... s[i+k-1]

    and another subarray of length K as s[i+1], s[i+2], ... s[i+k-1], s[i+k]

    the sum of both of these should be equal and equal to k/2.

    Hence,

    s[i] + s[i+1] + ... + s[i+k-1] = s[i+1] + s[i+2] + ... + s[i+k-1] + s[i+k]

    which gives, s[i] = s[i+k]

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

      Thanks , i missed this observation, feels bad now as I already applied this thing in some older problem.

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

Hi, I made a testcase on which my pretests passed code runs in 1.3s on my system. My code runs in $$$O(n*lg(n))$$$

Kindly check if it the same happpens for you.

TLE testcase for problem B

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it 
    for (int i=0; i<(int)p.size(); i++) {
		auto it = lower_bound(all(q), p[i]);
		while (it != q.end() && a[q[(it &mdash; q.begin())]] == 0 ) ++it;
		if (it == q.end()) break;
		int val = min(a[p[i]], abs(a[q[(it &mdash; q.begin())]]));
		a[p[i]] -= val;
		a[q[(it-q.begin())]] += val;
		if (a[p[i]] != 0) i--;
		// rep(j,0,n) cout << a[j] << ' ';
	// cout << '\n';
	}

    This makes your code O(n*logn)

    Update: Sorry my bad, it's O(n^2). For ex, consider the array 1 2 3 .... N 0 0 ..... 0 -1

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

    No, while loop in the for loop makes $$$O(n^2).$$$

     for (int i=0; i<(int)p.size(); i++) {
  auto it = lower_bound(all(q), p[i]);
  while (it != q.end() && a[q[(it - q.begin())]] == 0 ) ++it;

    I made worse case

    1
100000
50000000 1 1 ... 1 -1 ... -1 -1 -50000000

    When i=0 many elements in q become 0. For each i>0, it goes through.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D1D easier than D1BC for me lol

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the amazing round, I enjoyed it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +246 Vote: I do not like it

Tfw you read div 1 E in last 5 mins and realized it's the same problem you authored (which also turned out to be a duplicate of some old Topcoder problem) and you submit your old code to get AC in last minute :facepalm:

Moral of the story: READ ALL PROBLEMS!!!!!!!

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It was a horrible contest for me. Whatever confidence as a colorless I gained in past 3-4 contest just vanished today, though the problems were good but I just lost myself, completely shattered ;(

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +47 Vote: I do not like it

Is div1E a duplicate of topcoder SRM577?

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

    Yes, and zscoder just found out about it in the last minute https://mirror.codeforces.com/blog/entry/82288?#comment-691914

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

    My original plan for today was to skip CF and only participate in JOI Open Contest (5hr contest). I started it 3.5hr before the CF because collision didn't matter.

    And I solved everything in 2hr, so I could participate in CF. But I didn't care and just chilled.

    10 minutes after the contest started, I casually checked the hardest problem. It was a problem I solved some months ago, which means it's just free rating.

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

      I also had the exact same plan but I also joined cf later because I finished joi open in 3 hours.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

STRONG PRETESTS..

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

aah the good old system testing errors

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

    The vast majority of them are people writing n^2 with breaks on div2B, which we definitely didn't expect at all, and also when you can only have 3 pretests, one has to be a sample, one has to be a good correctness test with the max amount of test cases leaving only 1 possible n=100000 test. It's almost impossible to stop all possible n^2 with breaks with just 1 test case.

    → Reply
»
4 years ago, # |
  Vote: I like it +81 Vote: I do not like it

I think pretest 3 in question D is not valid. I got a runtime error when I tried to parse the input without trim, and I was able to pass the pretest when I did trim.(below is diff of code.) diff I've send question about this and haven't gotten an answer back. I really want to rejudge to fix this issue because I lost 14 minutes and got 2 penalties due to this issue.

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

    I read your question and you are right, I am extremely sorry both about the issue and about failing to reply to that question, you are correct that there's an issue in the format :(

    I have fixed the issue now, and we're looking into the possibility of rejudging. Once again I am deeply sorry.

    → Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How does the checker work in problem D when $$$n$$$ is even and the contestant prints a pairing different from the official one? Is it $$$O(N^2/64)$$$ using bitsets?

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

    Nvm I was stupid :(

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

    We used bitset if n<=25000 and heuristics otherwise.

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

    It is indeed $$$O(n^2)$$$ with bitsets for reasonable values of $$$n$$$. For very very large values of $$$n$$$, even that is too slow, so it works through some heuristics. Of course, this means you could get AC by printing something incorrect, but we didn't see it as a huge issue since the even $$$n$$$ case is easier anyways, and it's unlikely that someone will have a solution that is only incorrect for huge n.

    As a challenge, you could try hacking the checker to get AC on a wrong output, might be fun :)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +174 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    Mike is the best !

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

    Hi, my rating change was rolled back, but isn't updated yet. Can you please look into this?

    UPD: Just read comments below, and looks like it is the case for many people too. I guess you're looking into it then, still wanted to point it out.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -17 Vote: I do not like it

    Good for you

    → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

can someone explain this submission

https://mirror.codeforces.com/contest/1405/submission/92045757

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

    This is well known as code Obfuscation! TO avoid third party read code until you write an script to remove #define with original statements. This is a trick to avoid plagiarism issues. But since this solution is reported and this is out of contest rules thus this submission will be skipped and the rankings will be fixed!

    → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

1536-->1419 cool. Before contst-i have a chance to become xpert tonight.

After contest-god! please save me from becoming pupil!

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Finally Green!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

My bad luck.

Spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same mistake ,you can read my code.

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Interesting Problems + short statements + strong pretests + quick editorial, one of the best CF rounds ever, thanks all

→ Reply
»
4 years ago, # |
  Vote: I like it +98 Vote: I do not like it

The best part of this contest is clearly 92063082 getting WA on pixel art.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh no! I want to be 1800 in this contest. :(

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why codeforces Round #668 become unrated. Can anyone tell me?

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

So is it rated at last? If it is rated, I can be a CM. Can anyone tell me?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this contest was unrated?can any one tell me please?

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

    You won't get an answer until every participant asks this same question.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only one or ratings change reverted?

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

    Me too. Maybe it's Mike catching the cheaters? Don't know yet if there's a reason to cause this round unrated.

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

    Me too.It seemed to be unrated?

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

why this contest is unrated?Due to Div 1 E. problem ?Someone help me out with it.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello! When will the rating for div2 be restored?

→ Reply
»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Now is a good time to ask

Is it rated ?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

if the problem was a div 1 E , why div 2 ratings were changed while div1 ratings stayed the same?

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is it Unrated?

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

Why this contest got unrated? My ratings changed back to same as it was before the contest(div 2).

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

All of those who are thinking that the contest is made unrated, just wait for some more time? If it were really made unrated, you would get an update in the announcement about that. Ratings are just reverted temporarily for removing cheaters from the standings (as Mike's comment says) most probably.

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

I still have hope that it is going to be rated.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

Yesterday I learned from the banner notice at the top that the rating for this contest rolled back, but before I knew it, the banner disappeared and the rating is still not reflected. Is this recalculating the rate? Or did you become Unrated? (I'm Div.2) (P.S.) The rate has been successfully updated to the pre-rollback rate. Thank you very much for your great work!

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Why are the rating changes rolled back and not yet returned? Could someone please let me know?

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

MikeMirzayanov send help pls

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I did not get any update on my rating for this, can you guys check it please

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Something is definitely not right, otherwise Mike would have reverted the ratings by now

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

So it is rated now?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why not ratings ?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is the rating change of the contest permanently rolled back?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Since there was no interruption due to server lag or problem statement, It's gonna be RATED. Can be the case DIV1E is a open ques OR some cheaters are getting punished OR some problem in rating update formulae, Let's wait for Mike. (My opinion)

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

    But Round div.1 has been rated

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

      Then It can be the case that some people might be using 2 ID's to get there D/E Correct to avoid penalties in Div2.

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

        In this case, that codes will skip in the system test.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is #668 Div2 unrated? Who can tell me

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

why isn't Mike or any co-ordinator giving some clarification as to what is going on ?

MikeMirzayanov antontrygubO_o hugopm

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Please stop spamming the comment section to whether the contest is rated, it won't instantly solve things.

Just be patient and wait, probably the ratings are rolled back from removing cheaters from the contest.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

As we know,div2 + 5problems = codingspeedtest

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is my +120?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The rating has been reset!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you! :)

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I solved B and C in this contest then why is it showing that I solved 0 problems??

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).

→ Reply