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

Автор hugopm, история, 4 года назад, По-английски

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

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

hi

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

This is how the problems were created:

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

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

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

Excited for this contest!!

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

AC round 4

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

Hope for strong pretests.

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

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!!

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

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

Codeforces should make it a rule for authors.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -173 Проголосовать: не нравится
    My thoughts about tutorials
    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +66 Проголосовать: не нравится

      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.

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

      Do not decide for me

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

        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

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

          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

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

      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

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

        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

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

          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

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

            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

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

              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

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

                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

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

                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

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

    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

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

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

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

As a tester, good luck!

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

Ponies? Not again !

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

I wish I'd become green after this contest

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

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

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

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

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

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

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

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

Sorry, I sent it in the wrong place.

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

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

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

"gAmeGaME fOr 4lWayS B1enG NicE AnD SupPorTiVE."

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

    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.

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

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

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

So many reds ,red means danger xD

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

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

I am wondering who is the coordinator...

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

Why ponies? I am very scared of them.

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

No round coordination?

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

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

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

I wish everyone a happy contest !

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

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

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

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!

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

Oh Yeah!

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

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

It's so cute <3 <3

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

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

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

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

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

As a tester I want my contribution :)

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

    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.

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

USA Users, have a good contest on Labor Day.

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

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

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

hugopm How many common problems are there?

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

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

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

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

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  • Some good meme ;) *
»
4 года назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится

Please give me downvotes, Codeforces!

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

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

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

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

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

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

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

Congrats maroonrk for his very first win xD

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

speedforces

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

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

C > D

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

Thank you for a very nice C.

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

I guess div1b is Monogon problem

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

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...

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

    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.

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

      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...

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

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

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

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

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

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

    Same here

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

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

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

      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?

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

        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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • Try to satisfy $$$s_i = s_{i+k} = s_{i+2k} = s_{i + 3k} = ...... $$$
    • Try to make $$$s_{1...k}$$$ balanced
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

Am I the only one refreshing page for editorial :D

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

when will tutorial release?

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

Such a nice contest..

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

Any hacks on D ?

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

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

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

    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.

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

      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?

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

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

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

    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

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

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

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

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

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

How to solve 2E/1C ?

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

    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.

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

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.

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

    The case where 2Da >= diameter of the tree

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

      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?

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

        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.

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

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

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

            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.

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

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

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

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

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

    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.

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

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.

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

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

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

    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.

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

    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]

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

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

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

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

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

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

    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.

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

D1D easier than D1BC for me lol

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

Thanks for the amazing round, I enjoyed it

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

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!!!!!!!

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

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 ;(

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

Is div1E a duplicate of topcoder SRM577?

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

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

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

    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.

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

STRONG PRETESTS..

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

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

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

aah the good old system testing errors

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

    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.

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

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.

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

    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.

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

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?

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

    Nvm I was stupid :(

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

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

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

    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 :)

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

Nice contest!!

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

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

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

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

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

    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!

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

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

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

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

Finally Green!

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

My bad luck.

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

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

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

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

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

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

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

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

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

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

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

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

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

Am I the only one or ratings change reverted?

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

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

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

Hello! When will the rating for div2 be restored?

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

Now is a good time to ask

Is it rated ?

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

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

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

Is it Unrated?

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

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

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

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.

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

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

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

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!

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

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

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

MikeMirzayanov send help pls

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

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

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

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

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

So it is rated now?

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

why not ratings ?

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

Is the rating change of the contest permanently rolled back?

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

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)

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

Is #668 Div2 unrated? Who can tell me

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

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

MikeMirzayanov antontrygubO_o hugopm

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

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.

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

As we know,div2 + 5problems = codingspeedtest

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

Where is my +120?

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

The rating has been reset!

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

Thank you! :)

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

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

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

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