hugopm's blog

By hugopm, history, 3 weeks 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, Maripium, 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

»
3 weeks ago, # |
  Vote: I like it +694 Vote: I do not like it

hi

»
3 weeks ago, # |
  Vote: I like it +248 Vote: I do not like it

This is how the problems were created:

»
3 weeks ago, # |
  Vote: I like it +803 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Excited for this contest!!

»
3 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

AC round 4

»
3 weeks ago, # |
  Vote: I like it -39 Vote: I do not like it

Hope for strong pretests.

»
3 weeks 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!!

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -173 Vote: I do not like it
    My thoughts about tutorials
    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it -160 Vote: I do not like it

        ..

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it -157 Vote: I do not like it

        ..

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            Rev. 2   Vote: I like it -84 Vote: I do not like it

            I'm only putting my side

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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

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

      Do not decide for me

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

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

As a tester, good luck!

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

Ponies? Not again !

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

I wish I'd become green after this contest

»
3 weeks 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 :)

»
3 weeks 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

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

    There were not Anton problems in Div1 heh

»
3 weeks ago, # |
  Vote: I like it +170 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

6 sep, 8 sep, 12 sep, 14 sep <<div 2 days <3 >>

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

Sorry, I sent it in the wrong place.

»
3 weeks ago, # |
  Vote: I like it +87 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

"gAmeGaME fOr 4lWayS B1enG NicE AnD SupPorTiVE."

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

So many reds ,red means danger xD

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

A small price to pay for salvation.

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

I am wondering who is the coordinator...

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Why ponies? I am very scared of them.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No round coordination?

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    increase everyone's rating

    This statement breaks rating calculation rules of codeforces.

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

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

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


        cout<<"Hello World"

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      vivek21 What if everyone comes 1'st?

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

I wish everyone a happy contest !

»
3 weeks 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

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

    don't let cheat Prashant, and your ratings will increase brr brr

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

This is one of the most interesting announcements. <3

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

(or post memes in the comments if you can't solve any)

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh Yeah!

»
3 weeks 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

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

deleted

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

nibbi got no chill btw this is my first comment.

»
3 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

As a tester I want my contribution :)

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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:

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

USA Users, have a good contest on Labor Day.

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

hugopm How many common problems are there?

»
3 weeks 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?"

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

can i spam meme if i can not done the problem :Đ

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why was one of the problems in div 2 removed? It appears that the problem A or problem B has been removed because they are the only two that are not common with div1!
Is there an explanation?

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
  • Some good meme ;) *
»
3 weeks ago, # |
  Vote: I like it -50 Vote: I do not like it

Please give me downvotes, Codeforces!

  • »
    »
    3 weeks 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 :)

»
3 weeks 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

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

    I'm not sure you know how score distribution works

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell? :)

      • »
        »
        »
        »
        3 weeks 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

  • »
    »
    3 weeks 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?????

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

    score != difficulty

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

    congrats mate. (Your comment made me laugh for a whole minute lol)

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Can you please make registration button available for this round..there is still time

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Congrats maroonrk for his very first win xD

»
3 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

speedforces

»
3 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

C > D

»
3 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

Thank you for a very nice C.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess div1b is Monogon problem

»
3 weeks 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...

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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
»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

    Same here

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how do we incorporate that into '?'

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So basically what you have to do is first replace all question marks that you can, by applying this condition. Then remaining question marks will satisfy the condition that if s[i] is a question mark, then s[i+k] is a question mark. Now just check the first substring 0 to k-1.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here... is it greedy?

  • »
    »
    3 weeks 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.
    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate point 3?

  • »
    »
    3 weeks 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
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      But why it works?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        consider consecutive k length substrings lets say 0 to k-1, and 1 to k. Now suppose 0 to k-1 satisifies constraints, and s[0] = 0, then you can see that s[k] should also equal 0.

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

Am I the only one refreshing page for editorial :D

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Video editorial for D. Tree Tag

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will tutorial release?

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

Such a nice contest..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hacks on D ?

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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?

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

how to solve div 2 -C

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 2E/1C ?

  • »
    »
    3 weeks 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.

»
3 weeks 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.

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

    The case where 2Da >= diameter of the tree

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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?

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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 ;( :(

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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 ?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh nice !!

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

        I did it using substraction rather than using the remainder, still passed with same complexity and obviously the same idea.

  • »
    »
    3 weeks 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]

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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

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

      Oh! Thanks for that. I will edit the comment. $$$O(n*lg n)$$$ should still work in time limits I guess. EDIT: Failed on system tests.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D1D easier than D1BC for me lol

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the amazing round, I enjoyed it

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

Can Anyone tell me Why Did Codeforces compiler gave Run Time Error in my Solution to Problem B Div 2. My Submission: 92070449 while other compilers like https://www.onlinegdb.com/ gave correct answers?

I wasted the whole 1 and a half hours to debug this still can't. Can anyone tell me why did it happen?

I just Used Lower Bound to find the position of the lowest index greater than my present positive index and after operation erases it.

Please Help !!!

»
3 weeks 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!!!!!!!

»
3 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

So this is what failure feels like...

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

    posted twice, my bad! didn't realize new comments were at the bottom of the feed

»
3 weeks 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 ;(

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

Is div1E a duplicate of topcoder SRM577?

  • »
    »
    3 weeks 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://codeforces.com/blog/entry/82288?#comment-691914

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

STRONG PRETESTS..

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

aah the good old system testing errors

  • »
    »
    3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

interesting

»
3 weeks 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?

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

    Nvm I was stupid :(

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

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

  • »
    »
    3 weeks 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 :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest!!

»
3 weeks 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).

»
3 weeks 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!

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

    Mike is the best !

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Seems like there were a considerable number of cheaters around this time. And it's good that Codeforces is taking that into consideration. To be honest Even I have cheated a very few amount of times(2 times to be exact and caught once.. Good luck finding the other one). I just want to say that cheating doesn't quite brings the satisfaction that AC brings... And yeah don't downvote me coz of ratism only, feel free to ignore me otherwise

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

      And I vow to not to cheat ever again if not anything, then atleast out of my allegiance to Naruto

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it
  • »
    »
    3 weeks 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!

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Finally Green!

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

My bad luck.

Spoiler
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

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

Am I the only one or ratings change reverted?

  • »
    »
    3 weeks 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.

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

    Me too.It seemed to be unrated?

»
3 weeks 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.

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

Hello! When will the rating for div2 be restored?

»
3 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

Now is a good time to ask

Is it rated ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is DIV2 unrated now?

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Is it Unrated?