arsijo's blog

By arsijo, 5 years ago, translation, In English

Hi everyone!

The rated Codeforces Round #571 (Div. 2) will take place on Jun/28/2019 11:20 (Moscow time). This round is based on the Kremenchuk Summer Programming Cup 2019.

The contest is prepared by Dalgerok, Karasick, stanislav.bezkorovainyi, antontrygubO_o, danya.smelskiy, and me.

You will have 2 hours and 15 minutes to solve 6 problems.

Good luck!

We apologize for the issue that happened with the problem B. The round is unrated. If you want to read my emotional reply about it, please read this.

  • Vote: I like it
  • -802
  • Vote: I do not like it

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

shortest blog for CodeForces round XD

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

    I mean, you know the saying: Quality over quantity. xD

    Anyways, good luck to all participants!

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

there is one more thing you wanna say

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

I hope the statement as short as the blog :)

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

    Why hope? You won't even participate as far as I know.

    UPD: He is my friend, and I asked him about that, he said he won't participate in the whole contest.

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

      I'm sorry but his name is Black_Ghost, not "my friend".

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

      I guess he knew about problem B all along. He's happy now.

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

I got it all wrong, it was not you

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

It was wonderful to set the contest for 2 hours and 15 minutes instead of 2 hours.

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

    It will not affect much!

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

      It will not affect you and the people like me Who just solve 1 or 2 questions . :D

      And then they are done because they don't try to solve further .

      For others it matters a lot .

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

You forgot to thank MikeMirzayanov for codeforces and polygon platform.

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

What do they mean when it is said that the round is based on a certain competition? In this case the "Kremenchuk Summer Programming Cup 2019".

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

    it means there was hosted (or there will be hosted) a local competition and they decided to use its problems at cf round

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

      But wouldn't that mean that some coders might have already solved these problems?

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

        They are asked not to participate

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

        This round is during the official competition. Participants have no way to take part in this CF round.

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

This day is my birthday, I hope I will become yellow

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

    I think you will become Red instead of Yellow because it is your birthday #GPL

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

    Happy birthday in advance!

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it -41 Vote: I do not like it
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it -11 Vote: I do not like it

      It doesn't matter.

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

        "It doesn't any matter,OK?" is grammatically incorrect. This is an example of a fact that actually does not matter, because there are few native English speakers on Codforces and almost none English is perfect here (including mine).

        On the contrary, if a person has two fakes from which he writes contests, he indeed shows disrespect for the competitive programming community. You may say, that i am writing from a fake account and show disrespect for the community too. This is a valid point, but i do not plan to write contests from this account and, therefore, won`t affect the rating distribution and anything related with contests themselves. Secondly, i just wanted to write this using that exact handle.

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

      Im curious over how you deducted that this person has multiple accounts.

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

    By the way, how do we know you are not a contribution s**t? Anyone can write this and gets tons of upvotes, and, therefore, contribution. This comment does not provide no useful information, no joke or funny meme, it is not a question. It does not provide anything! Although i realized that i can not understand cf community properly, i still have no idea why this got so many upvotes. So, lets conduct an experiment. I will write a similar comment and will see, whether it will get upvoted or not (i bet it won`t).

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

      Shitposting is a perfectly valid mode of expression online

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

    ohho, many many happy returns of the day, Happy Birthday in advance. :)

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

    I hope to become yellow as well because it's nomapunk's birthday

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

    Good luck.Happy birthday!

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

    Happy Birthday!!! I wish you that each problem you solve would be as interesting as this round`s B!

    All the best!

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

The time is unusual.And it is friendly to Chinese!

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

    so strange I feel. Although I think in here, the words Rabbit said seems emotional and rude. But, both sides’ words are really harmful to this fair community and very disrespectful. I don’t know how everybody who looked at these comments, also upvote or downvote to both them thinks. At least I regards these behaviors are unreasonable.

    Ok, I’m just using my right to express how my feel, and also, take my downvote. Mmaybe a downvote can’t represent or change anything, there may be a lot of people on the other side. So what, that’s my right¯_(ツ)_/¯

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Do i need to register or can i directly participate..I don't see register button..

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

    contest has ended. before contest you will see a register button

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

May I become an orange color after this round?

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

New to codeforces and been reading this a lot "based on......". What does thos actually mean?
Are the questions same, similar or based on something taught there??

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

Hi i'm very new to CP. I'm not sure if this is the right place to ask my question but sorry :-) I've joined CF recently. In my profile it is showing unrated. What should do to get rated.

Please help me I want to improve. Thanks to all in advance

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

Can someone give more information about the "Kremenchuk Summer Programming Cup 2019"?

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

It's a nice time for Chinese CFer

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Kek, authors have 3 IMO medals. Why not 3 golds, antontrygubO_o? :trollface:

»
5 years ago, # |
  Vote: I like it -35 Vote: I do not like it

This day is my birthday, I hope I will become cyan.

»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

good luck !

hope good color for all ♥

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

As a Chinese I think the time will be good for us.
However, I'm in Russia now and thus the time is not that friendly for me to participate lol.

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

I was introduce with programming just 1.5 year ago. I have created my codeforces acount then. But still i don't know about the rating system. Anyone please help me to know about the rating system.

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

It feels to be good on Codeforces!

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

Contest time is suitable for Chinese.Good luck for everybody.

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

Hi everyone I want to solve questions on graphs and trees but i don't know basics about tree and graph.Please anyone help me from where i can learn basics and after that i can solve questions on graph and tree. Thanks in advance.

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

Why contest delayed by 15 minutes? It's definitely a bad culture of Codeforces!

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

    I think the purpose is to gain more participants, but since the start time is different from the usual contest, the fact that there are fewer participants is not strange. Anyway, it's time to read comments. :)

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

Delayed by 15 minutes

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

Sorry about the delay. We have some internet issues onsite.

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

Will there be a 12 hour period of hacks for this round after the contest?

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

    Nope.

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

    No. 12 hours hacking phase exist in Educational CF Round and Div.3 Round (and few more contests).

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

 that internet issue again

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

Seems that, codeforces is trying to maintain it's dignity(as well as uniqueness) by delaying contests nowadays.

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

![ ]( ) we are still waiting

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

looks like that code forces is testing it's users's patience !!

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

yes 15m delay ...…. Thx from Bangladesh !!! its Friday …. ( salat time if the contest start before time)

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

So real!!!

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

Score distribution?

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I had registered for the contest . but during contest it showed i didn't register for the contest and thus couldn't submit solution . Please , Codeforces solve these type of problems soon.

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

I think the sole purpose of this contest is drop my rating, getting easiest A and level goes high up from B.

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

    it's true about me too ; i'm exactly like you now !

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

    ur lucky,round became unrated

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

    Same here :)
    Had some network issues and couldn't submit 1st problem with good speed.
    But it's unrated now :D
    We are lucky.

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

the contest is unrated now :(

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

The problem setter of B should stop creating problems.

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

    how to solve c , can u tell me

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

      let sum(l, r) be the number of "1" appears in range[l, r] in the string a.

      and the answer is the number of range [l, r] that (sum(l, r) % 2) == (the number of "1" in string b % 2). and of course (r — l + 1) = |b|.

      you can see the code of my another account Dilute_ :P

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

        (sum(l, r) % 2) == (the number of "1" in string b)

        Can you clarify the above line please? Because LHS would always be 0 or 1

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

          I believe Dilute meant sum(l, r)%2 == (no of "1" in string b)%2

          because say there are x no of "1" in substring of a and y no of "1" in b and z be the no of "1" that are in same position in that substring and b

          then required number of different will be x+y-2z

          so if x + y is even, that substring is counted in final answer

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

            Thank you and How you come up with this?! Do you have some similar problems on cf?

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

            how please explain or if u have link of similar problem share it

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

              Proof for problem C. BanazadehAria

              Let there be $$$x$$$ number of 1s in substring $$$c$$$ of given $$$a$$$ and $$$y$$$ number of 1s in substring $$$b$$$.

              Let $$$t$$$ be the number of 1s that match[overlap] in both the strings. So exactly $$$x-t$$$ number of 1s do not match in $$$c$$$ and exactly $$$y-t$$$ number of 1s do not match in $$$b$$$.

              Total mismatches = $$$x+y-2t$$$, we need to find whether this is even. $$$2t$$$ is even, so it's sufficient to check whether $$$x+y$$$ is even.

              56238050

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

            Well.. It was my fault and I have fixed it now :D

            I just wrote the comment without checking carefully, but I just meant it modulo 2 QwQ

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

        You do know that you are not supposed to have two accounts, right?

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

    LOL! But why? Is it because it was very difficult in comparison to the points assigned to it or because the judge's solution was wrong.

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

    Exactly. I didn't like that problem either.

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

    I'm really interested in why so much people solved B...

    and their solution are all the same as the writer's wrong one...

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

      Because a lot of people follow their intuitions blindly :-)

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

anyway, will there be a tutorial for the B ?

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

    I think the answer is (n+1)*(m+1)/6, but I didn't prove it yet.

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

      its wrong

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

        Can you show me the case my answer gives the wrong answer?

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

          Try 6 6 The answer is 7

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

            NO. The answer is 8. And like this:

            1 . 2 . 3 3
            1 . 2 . . .
            . . . . 4 4
            5 5 . . . .
            . . . 6 . 7
            8 8 . 6 . 7
            
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh, you are right.

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

      Also thought of this during contest, but was given WA on 3, also can't find any counterexample.

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

      I think the answer is (n+1)*(m+1)/6, but I didn't prove it yet.

      Apart from proving, could you please explain your intuition?

      What is a resoning behing this formula?

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

        It is now understood. An explanation by Noam527 was helpful.

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

          I thought it by finding that when input is 13 17, the answer is 42. :)

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

            Are you kidding me? How could you find the right answer for this input during the contest? (13x17 seems to be too large for brute force.)

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

              It is like this.

              A . B . C . D . E . F . G
              A . B . C . D . E . F . G
              . . . . . . . . . . . . .
              H . I . J . K . L . M . N
              H . I . J . K . L . M . N
              . . . . . . . . . . . . .
              O . P . Q . R . S . T . U
              O . P . Q . R . S . T . U
              . . . . . . . . . . . . .
              a . b . c . d . e . f . g
              a . b . c . d . e . f . g
              . . . . . . . . . . . . .
              h . i . j . k . l . m . n
              h . i . j . k . l . m . n
              . . . . . . . . . . . . .
              o . p . q . r . s . t . u
              o . p . q . r . s . t . u
              

              Actually not so hard..

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

                But how did you know that this tiling is an optimal?

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

                  In fact it is another intuition. So I checked another case:

                  A A . B B . C C . D D . E
                  . . . . . . . . . . . . E
                  F F . G G . H H . I I . .
                  . . . . . . . . . . . . J
                  K K . L L . M M . N N . J
                  . . . . . . . . . . . . .
                  O O . P P . Q Q . R R . S
                  . . . . . . . . . . . . S
                  T T . U U . a a . b b . .
                  . . . . . . . . . . . . c
                  d d . e e . f f . g g . c
                  . . . . . . . . . . . . .
                  h h . i i . j j . k k . l
                  . . . . . . . . . . . . l
                  m m . n n . o o . p p . .
                  . . . . . . . . . . . . q
                  r r . s s . t t . u u . q
                  

                  But this case gave me same answer.

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

When you solve D problem the first time and contest becomes unrated :/

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

The contest became unrated. :(

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

The luckiest and unluckiest day of my life

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

What's the answer of this input for problem B?

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

It's 4:50 a.m. in my timezone.

And the round is unrated.

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

How to solve B?

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

arsijo please stop creating problems (с) (2).

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

Let's solve problems for fun!

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

Scored well for the first time. Round unrated. Can't laugh anymore at my fate. LOL crying inside

»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Round became unrated => Let's start down-voting the blog post :D

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

    There was some problem in B, it affected a lot of people and hence unrated, doesn't mean we down vote him, it takes a lot of efforts to come up with problem ideas and write problem statements.

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

      I know man I appreciate all the effort, I up-voted him too, but it's some kind of Codeforces tradition.

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

      But it is also true for the problem setters to take responsibility for their mistakes.

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

calm down...

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

I wrote down last Div2 contest that from now on I will skip B's and work on C and D, and I managed to solve D while I didn't have even the slightest idea how to solve B (or C). Seriously guys, fix your B's and C's, C's are usually better and easier than B's because you put some stupid string/geometry tasks in B that are unnecessarily hard.

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

When the contest time is so convenient for you, but the round became unrated. SAD LIFE

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

Is this round unrated now?

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

    sad to say yes :(

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

    Can anyone give solution to problem C?

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

      In Problem C, Look for every substring of length |b| in string a , Now, for every substring count the number of set bits and if the sum of set bits in a and string b are even then just add 1 to your answer.

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

      If there's an equal amount of 1's and 0's in string b and string(a.substr(i,b)) then their difference must be even.

      1010 and 1100 is a good example, no matter how you arrange those 1's and 0's, their difference will still be even.

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

I thought that author of problem B was just unlucky. Even many (it could be over 80%, maybe?) oranges or reds are solving with incorrect solutions. So it is not to surprise that all writers and testers solved in incorrect but same way.

So, I can't gaze at the current situation which problem setter said to stop creating problems.

And I don't think that it should be heavily downvoted, as same reason as Codeforces Round #373.

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

    For such problems, I in general expect rigorous mathematical proofs of the claims made. So, I'd like to know if the proof went wrong somewhere, or did everyone else use some greedy-like technique?

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

      Both are possible. It is possible that proof of problem B went wrong somewhere, judging by many orange of red coders tend to at least find a way to prove the optimality before coding.

      But it is also possible that authors "verified" their solution by brute-force check for small H and W, then got that it is same as kind of greedy-algorithm result.

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

    I guess, just stresstesting author's solution with O($$$2^n * m$$$) will do the trick. But they are to lazy to write dp for 10 minutes or to prove something. So I think it should be heavily downvoted.

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

      How to calculate the optimal value with DP by $$$O(2n * m)$$$? I thought about it for five minutes and couldn't come up with it. I only came up with something like $$$O(2^{2n+α}×m)$$$ solution because we also need to think about "non-touching combination" and it will be like similar to $$$4×3$$$ tiles.

      Also, implementation is difficult. It is inevitable that tester thought that brute-force is enough for testing (if did), contrasting to heavy-implementation DP. Since the complexity of brute-force is about $$$O(2^{nm}×nm)$$$, it is no wonder they missed the minimal hacking case of $$$n=6,m=6$$$.

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

        Ok, all right, O($$$2^{2n} * m$$$). Ok, even brute-force is enough to find 6x6 test, isn't it?

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

          I manage to find optimal answer of $$$n=6,m=6$$$, but it took more than $$$45$$$ seconds with pruning brute-force algorithm written in C++.

          Here is the results of all possible testcase for $$$n \leq 6, m \leq 6$$$. The results are represented as the format H, W, the optimal answer, and the number of states in pruned DFS, in one line. My program took $$$67.535$$$ seconds to compute all of them.

          Solutions

          My pruning algorithm is that "decide if there's a tile, from increasing order of pair (x,y), and prune if $$$size \geq 3$$$ 8-connected components appeared.

          I think my pruning algorithm is not perfect. But I at least can say that the situation difference between $$$(H,W)=(6,5)$$$ and $$$(6,6)$$$ is huge.

          UPD: Seems like $$$H=6, W=6$$$ was not even a minimal hacking case. I made a mistake in my calculation, and the intended answer was correct. Seems like E869120 made a more efficient brute-force (refer to this comment). But even he could not find the hacking case. It means that efficient brute-force cannot even find challenge case.

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

          Sorry, I made a mistake in my calculation. $$$6×6$$$ is even correct. I thought that $$$7×7÷6=7.x$$$. What is the minimal hacking case, though?

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

            $$$7∗7/6=8.16666666666667$$$

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

              Finally we managed to prove that the optimal answer will be exactly $$$⌊\frac{(H+1)(W+1)}{6}⌋$$$. The proof was rather difficult, but I liked it. It was a good example of IMO-like problem.

              I even think that the problem can re-appear, because now there exists a correct solution.

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

                That's not how IMO problems look like... Though I haven't proved it yet, this problem absolutely requires lots of casework and details, and that's not the spirit of IMO.

                Also, this is a nice problem, but in my opinion, it is not suitable for CP contest since most people will just guess the answer without really proved it and the difficulty of the problem is mainly its proof.

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

        how to solve B using dp?

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

      You are right that this problem is not well-prepared. We could fix it. However, I absolutely do not agree that we were lazy. We spent a lot of time preparing this round. We fucked up, that is true. The main reason of this is me, because as a CF employee, I had to check everything. When we started to prepare the main contest, we did not want to hold a mirror. But in a week before the round, KAN told me that there is a need of a CF round at the end of this month. I recalled that we were organizing a contest at that period of time. Therefore, I decided to let people solve those problems too. Why do you think we do it? Why did we prepare round? Money? Shit no, if I wanted to earn money, I would prepare problem for Codechef, as many of my friends do. If we wanted to earn money from this round, we would give these problems to Codechef and earn much more. Instead of this, we decided to satisfy the need of CF users of a round. If you want to blame us because of it, go ahead, downvote the post (I am sure you did it), say that arsijo fucked up.

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

        But this round didn't even have testers

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

          We had cross-testing. Authors of some problems tested other problems.

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

            Well, then at least 1 tester of 5 should have written stress.

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

            So you didn't prepare very well.

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

        everyone makes mistakes, it is fine, ignore the haters

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

          Lol, that is, if you are criticized, then they are wrong?

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

        Nobody said you're doing it for money so I don't see a point in bringing it up. Especially in a comment that you linked in the announcement blog.

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

          So that more greedy coders start writing codechef problems instead of cf rounds :)

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

        I would start with the basic issue: that problem was completely inappropriate as div2 B. Perhaps if it was valued correctly, it would have been tested and proofed better...

        IMHO this type of problems should be forbidden in contests at all...

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

        Meanwhile codechef: Why the fuck are you dragging us into this

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

        I just want to say you are really a great man, and selfless. Good luck and look forward to your next contest!

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

        You are absolutely right! But why don't you just stop creating problems? :)

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

        So, will you publish editorial of this round ?

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

        So basically you are saying that it is OK to make problems with incorrect authors solution as long as it is some local contest or Codechef round?

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

        When we start system testing ?

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

        arsijo rest are fine but u shouldn't dragged money and codechef in between. No sense of making these points here.

        you should really improve your problem quality, first your problem c of your previous round and now this.

        && last thing codechef doesn't pay money to anyone who just come up with a random bad problem and puts it in contest without testing or juding its difficulty. .

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

          codechef problem authors get money bro...

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

          what was wrong with the C problem in last arsijo`s contest?

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

        Can you just run the system test? I want to try other problems in the problemset.

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

        Efforts can't win respect without taking responsibility.

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

        Who doesn't shoot — will never miss.)

        P.S. Ok, maybe, someone didn't understand me. I don't think anything bad about authors of the round. It was a proverb and means "Everyone who does something sometimes makes mistakes" and it NOT BAD. It is a part of process.

        Peace.

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

        How to prove that the solution of problem B is (n+1)*(m+1)/6?

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

        Thank you very much! The problems are really interesting

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

        What is a lot of time by the way? 10 hours?

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

        arsijo fucked up.

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

    So it is not to surprise that all writers and testers solved in incorrect but same way.

    I completely disagree with this statement. A setter shouldn't try to solve a problem in 5 minutes and then call it a day. It isn't the only job of testers to get AC either.

    That being said, I don't like all the "stop creating problems" comments. To all setters: just make sure you write brute force solutions, you write down proofs, and that somebody will carefully read those proofs.

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

      I wholeheartedly agree. I think that with just a little bit of extra testing, the quality of CF rounds in general will increase.

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

In problem B, the result for "6 6" should be "7" and for "8 8" it should be "13". I guess it's the problem for the solution and the point for my "Wrong answer on pretest 3" * 4 and "unsuccessful hacking attempt" * 2.

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

    For 6x6, the answer would be 8

    1 . 2 . 3 3
    1 . 2 . . .
    . . . . 4 4
    5 5 . . . .
    . . . 6 . 7
    8 8 . 6 . 7
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, my fault...So can this problem be solved in O(1) time?

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

        It might be

        ( n + 1 ) * ( m + 1 ) / 6

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

            Looks right, but I could not prove the very first claim myself and then gave up. How to prove that if there is a correct placement of the 1x2 and 2x1 pieces, then the extended 2x3 and 3x2 pieces do not overlap?

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

              Consider most high right point these usual pieces touch. If it belongs to both pieces, they overlap. Now it belongs to one "hightest" piece. They overlap iff extended highest overlaps other one's highest rightmost point. It cannot overlap other one's extended side (the one we added, imaginary)

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

                Thanks! Still can't say I completely understood it but I got the idea.

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

                  if extended higher upper piece touches other usual piece, then both extended pieces collide.

                  If it does not touch other usual piece, it does not touch its extension: (Same as if extended touch, usual pieces touch) If extension covers usual piece, then both usual pieces touch trivial. If both extended areas touch, then: a) Going higher on piece 2 collision (that is lower or right-er) from that point, we get to usual piece from piece 2, that piece also collides with extended 1, trivial case above. It cant go higher because piece 2 is lower. Also, all higher pieces collide and if there are no usual pieces 2 on that path, we can still use that fact. Let's take highest such point b) We get some other extended collision piece. By same argument, we can go left and find usual piece from 2 that collides with extended 1. This time, we know that going left once will get us to usual piece 2 (there is only 1 point with the property for both types of extended pieces). This time, this piece may not even touch extended 1, but be in lower left corner of it. So it touches usual 1 by our rules anyways (this one is extra case, others are trivial).

                  Extended = piece with border. Extension = border (down and right) usual piece = original one, without extension

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

            Thank you for the detailed explanation

            This is the 7x7 case: (in case anyone was wondering)

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

              What does that state mean? I can't find the purpose of that state because the answer of input 7 7 is 10; like this:

              A . B . C . D
              A . B . C . D
              . . . . . . .
              E . F . G . H
              E . F . G . H
              . . . . . . .
              I I . J J . .
              

              and other solution also exists.

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

                In fact we say "7 7" means H+1=7 and W+1=7. So you should use "6 6" as input.

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

                It was in response to Noam527's comment. I think saying n=7 m=7 would be better. It's for a 6x6 grid

                From that convert 2x3 blocks into 1x2 blocks and 3x2 to 2x1

                1 * 2 * 3 3
                1 * 2 * * *
                * * * * 4 4
                8 8 * * * *
                * * * 6 * 5
                7 7 * 6 * 5 
                
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This has to be solved in O(1) time.

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

    me the same. my solution is (m+1)(n+1)/6 but "Wrong answer on pretest 3". I dont know why :((

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

      Because the data of the problem was wrong

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

Delayed 15 min and turned out to be unrated. What a good round!!!

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

    Something was fishy about this round from the start.

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

      From the announcement. You could see arsijo as author

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

        It's ok to complain about the contest, and downvote the blog, because he made a big mistake.

        But I don't see any reason to make personal attacks. If you can't find a way to give constructive feedback, just shut up.

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

A problem in EGMO contest 2019 is just a special case of Problem B today (they just ask to find the maximum with table of size 2n x 2n):

https://artofproblemsolving.com/community/c6t520112f6h1818715_yet_another_domino_problem

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

    Nope. Those dominoes have to be 2 blocks away not 1. This problem is more similar to Croatian nationals 2019 where I would have won gold if I didn't misread a problem. (The problem is #3 on page 3, use google translate)

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

What a shitty contest.Problem A kindergarten problem.Problem B is shit. Problem D is easier than B. Don't know who is testing these rounds.

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

    Agree problem B was shit. And A was very tough :(

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

    I agree with you, but please respect the authors. Preparing a round is difficult.

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

    I also agree that B in this game is very bad.

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

What the f**k?

I had a great score in this round and I can be a candidate master then it is unrated?

I thank the authers very mucn and I know preparing a round is difficult. But I still think this is a little sad.

Hope everyone can have a great score next time ans hope myself can be a candidate master. :(

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

    Today, somehow I managed to do the problem D and the contest got unrated. karma is a bitch!!

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

    Come on. Keep training. Hope you can get a gratifying score in the next round. (And hope there isn't any grammar mistake in those sentences)

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

A perfect contest becomes bad because of problem. I feel upset.

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

    How was the contest perfect in the first place?

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

I am very very disappointed in codeforces. I woke up at 3:30 AM just to do this contest. I was actually pretty happy when I saw the problems because I knew how to solve them and I was predicted to get quite a bit of positive delta. But all of a sudden announcing that the round is unrated because the problem writers for some reason can't make good problems is quite discouraging. Imagine how many times I would have wanted round to be unrated in order to not lose rating. Maybe this should be a wake up call for all those creating contest: From weak pretests, to weak solutions, to weak language. All this can be avoided by testing thoroughly and thoughtfully.

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

    boo hoo cry kiddo hahahahah

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

      Hey I am not a kid! I am almost 4 years old!

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

Weird difficulty distribution.
For me it is just like A < C < D < F < both B and E
What thE HeLL???

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

    Dude, I had to use SCAN to pass F, wtff ????

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

      My dumbest greedy algo' passed the pretests while I can prove it is neither right nor wrong lmaooooo

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

finally passed pretest of F have almost +200 on predictor, excited to become candidate master. And the next second it became unrated.....so upset.

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

real shit contest ! hard B(even writer and many unofficial participant don't have solution). fucking implementation D and E with Case handling !

please when you are writing problems be in participants shoes and don't write shitty problems !!!

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

How does it feel when 6 authors + testers + coordinators can't properly solve 7th grade math?

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

    Moreover, there are 2 gold IOI medalists and 3 IMO medalists among them

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

      Why is it so hard to make good problems? I am genuinely curious.

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

By the way, it was because of the problem B that I moved to D and could solve it. So, thanks anyway.

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

UNRATED

That's the result when you forgot to thank MikeMirzayanov for codeforces and polygon platform. :)

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

    it is the K A R M A T R I G G E R E D
    (nope

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

The problem setter of B should stop making questions. At last it became unrated. This was my debut round for becoming specialist XD. Someone wants to see me in green.

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

OK,I can solve these problems for fun.But in fact it waste my time.But I won't decrease my rating.

It's a lucky and unlucky day.

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

Can someone give me counterexample to (a+1)*(b+1)/6 in B?

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

    As someone already pointed out, 6x6 can have upto 8 dominoes placed.

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

      7*7/6=8

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

        Ah, my bad. Consider 5x5 then — we expect 5*5/6 = 25/6 = 4 as the answer, but you can get 5.

        Edit: Oops, I'll just let someone else answer this before I make more blunders now :(

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

          In 5x5 you can even have 6, and 6*6/6=6 .

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

    6x5? I think answer is 6.

    (n+1)*(m+1)/2 gives 7.

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

      **.*.*

      ...*.*

      **....

      ...*.*

      **.*.*

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

      5x6 is 7.

      11.2.3  
      ...2.3  
      44....  
      ...5.6  
      77.5.6  
      

      this is one possible way to reach that

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

    I think the input 4 10 does not work. The answer is supposed to be 8 but the formula gives (5 * 11) / 6 = 55 / 6 = 9. Here are some possible arrangements of 8 tiles in a 4 * 10 matrix:

    1 1 . 2 2 . 3 3 . .
    . . . . . . . . . .
    4 . 5 . 6 . 7 . 8 .
    4 . 5 . 6 . 7 . 8 .
    

    1 1 . 4 . 5 5 . 8 . . . . 4 . . . . 8 . 2 . . . . 6 . . . . 2 . 3 3 . 6 . 7 7 .

    I cannot find any arrangement for 9 tiles.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it
      1 . 2 . 3 . 4 . 8 8
      1 . 2 . 3 . 4 . . .
      . . . . . . . . . 9
      5 5 . 6 6 . 7 7 . 9
      
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The problem statement of B was very unclear. Did C and D and later found that the round was unrated. Many contestants like me are very excited whenever we see a new contest on the contest page and are equally disappointed when the round becomes unrated due to such reasons.

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

waste time for this contest, 1 min to solve A and 1 hour can't solve shit problem B. And when it remove, i spend 5 min to solve D -_-

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

    That's why I always read B, C, D after solving A. You never know, maybe D is easier than B XD

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

Why "this round be the UNRATED"? Other problems are perfect. :(

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

    Because many people waste too much time in B,I think

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

      Maybe you are right. Ah.Today is really unlucky.

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

    I stuck with B because my solution is right

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

      On B,My Solution is wrong.

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

      i submitted (n+1)*(m+1)/6 but "Wrong answer on pretest 3". Are you the same ?

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

        I submitted ((n+2)*(m+2)-12)/8+1. I think my solution is wrong.

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

    Last time, one similar contest also became unrated just because the problem A had a small mistake on a special situation. And the mistake was discovered and fixed in less than 15 minutes. But the round still became unrated.

    So any mistake which may influence the contestants' score and rating changes is not allowed to be found in a rated Codeforces round. That's the rigorousness of Codeforces.

    By the way, if you exactly participate a round like this and you lose the high rating delta, looking forward to next round and try to keep a good mood.

    Hope everybody get a good score in the next round.(And hope there isn't any grammar mistake in those sentences)

»
5 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Blacklist all problem setters.. :'/

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

My mood right now after knows the contest is unrated

mood

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

Who is here after the round being unrated and before the end of the contest?

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

The problem maker is cxk

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

I like contests. We should not forbid the problem setters from setting problems. Without their effort, there will be no contests. Just prepare problems with caution and be aware that thousands of people will suffer because of careless.

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

I was so happy for a while...

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

How beautiful the Problem B is!

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

Even though the round is unrated, I liked C and D. nice problems!

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

Since the round is unrated, can anyone give some hints on F?

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

    for each edge if removing this edge does not decrease degree of connected vertices below their allowed minima then remove it. Passed the pretests hope it will pass systests.

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

    I think pretests of F may be weak — I randomized the order in which I check edges, and then greedily take them until I get a workable configuration — others have pointed out just simple greedy also gives pretest passed.

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

How to solve D?

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

    You can floor all numbers, then add +1 for each one (except integers) while sum of array is less than 0. Too easy for problem D I think.

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

      I think it's easier than B(which needs lots of thinking).

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

It proves that the task may need more people to check, and tell the reasons. :(

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

    this will be a greater lesson to the problem setters of codeforces :P

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

Who will win : Div2B or 2 gold IOI medalists and 3 IMO medalists

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

am I the only one who didn't even understand B ?.. I don't get it how they do touch and don't

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

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

What was wrong with F?

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

    Plz. say that F is also wrong...!!!
    That will make the setters learn something unique today... lol

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

      No, there is a correct approach, but I'm afraid about the strength of the testcases. Most solutions should fail if they are strong enough, for example, the solution of the current winner (pekempey) fails on this test:

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

        My greedy 56221717 passed that test, but i think that maybe my solution should be wrong.

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

    I dont know, but I had to use SCAN to read input and printf to output. Otherwise I would recieve TLE in test case 10. Probably my solution is wrong.

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

      not always, since reading $$$2*10^6$$$ integers does take tons of time
      however my greedy failed on this test XD

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

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

This is now a curse to those who don't thanks to MikeMirzayanov and to Polygon. If you don't, your contest will be unrated!

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

How to solve problem c?

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

    solve it using windows sliding technique in O(N)

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

    Set ans = 0. First, count the sum of 1s in string b and the first |b| letters of string a. If the difference of them is even, add 1 to ans. Then consider shifting string b to the right and change the second sum, add 1 to ans when the difference is even.

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

      That seems like a great solution, I would have never thought about that because in my head, summing up when I need to compare leads to WA, but I guess not in this task.

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

        It's right in this one because a different digit makes a contribution of 1 or -1 to the difference of two sums.

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

I wonder how my brute force solution for F passes the pretests?

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

In what case is the answer in B not $$$\left\lfloor(w+1) (h+1) / 6\right\rfloor$$$?

This is at least an upper bound, since the problem is equivalent to tiling a $$$(w+1) \times (h+1)$$$ array with $$$2 \times 3$$$ pieces. To do this, place a $$$2 \times 1$$$ domino to the upper-left corner of every $$$3 \times 2$$$ domino, and a $$$1 \times 2$$$ domino to the upper left corner of every $$$2 \times 3$$$ domino.

Edit: I managed to prove that this can always be achieved

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

    There is no such cases.

    For $$$n>1$$$ you can tile $$$6\times n$$$ rectangle by $$$3\times 2$$$ pieces. So it's sufficient that formula holds for rectangles when $$$w,h \leq 6$$$.

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

can any one explain C ?

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

    First observe that if two binary strings are same at an index, then the sum of the bits is even and if different, sum is odd. So, the total of such sums of bits will be $$$Sum= (No. \, of \, vertices \, at \, which \, bits \, are \, equal)*(Even)+(No. \, of \, vertices \, with \, different \, bits)*(1)$$$ So the criteria for even number of different bits reduces to the sum being even.This can be done in $$$ O(n) $$$ by storing the sum of |b| bits of a and iterating through the remaining bits of a.

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

Is F really easy or does the greedy not work?

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

What is system testing after the contest?

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

Credits to Rudy1444 for outstanding memes

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

Here, I don't know why people are angry because this round goes unrated. I am very thankful to the problem setter that I am able to read all the question this time. Otherwise, I got stuck in the 2nd problem.

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

in F: greedy will always work or we should use DFS + eulerian tour ?

»
5 years ago, # |
Rev. 6   Vote: I like it -32 Vote: I do not like it

[ [ DELETED ] ]

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

    Chill, if you're red it doesn't mean you have to win every time, so stop complaining to grab contribution. We know B is bad, but if a green complained about it he would've gotten -40 or smth.

    Also, you could've focused on harder tasks, since they're obvious close to your level.

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

    Since there is only a month before IOI, you should weight more in practice with more difficult problems. Not like some shitty Div2 rounds. Or are you actually a blue coder??

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

      [ [ DELETED ] ]

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

        Then you solved Div.2 F this time and learned a lot. What's the problem?

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

          [ [ DELETED ] ]

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

            ...why didn't you open E and F first then? Performance and rank are absolutely irrelevant when you're participating in Div2 rounds.

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

              EnumerativeCombinatorics LOloLolOlOollloL. why are you giving others suggestions. I think you yourself didn't get any precious thing from your IOI

              "...why didn't you open E and F first then" HAHHAHAH.. why don't you do the same in atcoder grand contest problems. Like ksun, tourist and petr does.

              "As a tutor, I am really disappointed with your stance towards OI." LoLOLOl you r a tutor. actually you yourself need a tutor. you can't touch 2600 in these 10yrs of your codeforces and behaving like tourist. LOLolOLol.

              And finally, KSUN48

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

                Who hurt you?

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

                You keep messaging me just saying ksun48. Do you love me or ksun48?

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

                These LTDT clones are nowhere near as good as the original

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

            Complete waste of time is reading your crying.

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

    Why are you and square1001 always like this?

    No one judges how Div1 people do in Div2 rounds. This is nothing like IOI, and no one doubts you're good

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

      [ [ DELETED ] ]

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

        Okay, I can see why you personally care about Div2 rounds, but maybe read back the post before you send it.

        What to you reads as an honest message about 'failure' reads just like matthew99 or geniucos' whining posts after their 'failure's in the IOI — really annoying to most people on CF (in particular, all the Div2 people in this round) who would be lucky to have as good a contest in a year of programming.

        Note: I say 'failure' because I do not judge either of the cases mentioned as failure

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

      I'm not an IOI participant this year so I can't say anything, but caring much about "not failing in contest" is a very good concept, because we can't miss gold or some medal. Gold medal probability 80% is better than that of 70%.

      So, if we fail even in Div.2 contest, we tend to search why did it fail and we believe that excavation of them may yield mountain of treasures for improvement. Suppose that I solved Div.2 F in 30 minutes but some reds are solving in 25 minutes — we think about what was different between the fastest players, and what was wrong in my thinking, implementation, debugging, or something else, and then think about improvement to decrease the probability to fail in the same way in future.

      However, for this time, he claims that the writer was the cause to fail. I wonder what improvement we can find.

      UPD: He mentioned in his comment that we should not forget that Div.2 has also many interesting problems, and it is also same as my thought.

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

        Isn't it why you failed to get in the Japanese national team that you always care about "why can't I solve this (Div 2) problem in 30 minutes" rather than "why can't I solve this (OI problem some golds can solve) problem in 2.5 hours"?

        You two gotta understand the priority. Why are you always practicing short-term contests and failing (or at least struggling) at training camps for years? As a tutor, I am really disappointed with your stance towards OI.

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

        I would be very surprised if someone has never gone far lower than their expectations. Ideally, when you fail you need to look for reasons behind the failure, so you could focus on improving said points. On the other hand, taking part in a contest means you need to accept the possibility of failure. I'm not saying you shouldn't care about failing, but rather if you accept it, you can forget about that fear, possibly even perform better, and not take it hard when it happens.

        To me it seems that E869120 is devastated about the wrong things. "I spent 91 out of 135 minutes for problem B, and because of this issue, my round result became historic and rare failure. [begin complaint paragraph]" — Okay, you can point out the bad time management, but how about you focus on "next time I can prepare myself for such events and manage time better", instead of ranting about this specific performence? You're worrying too much about things that, frankly, are not under your control;

        • A certain problem will take you longer than for others.
        • You cannot find the bug quickly.
        • Today was just a "bad day" for you, while maybe a "good day" for others.

        Maybe having a good day to you is affected by how well you slept the night before, but it's useless to consider it during or after a contest, so what good is it to focus on such things? You need to be aware that it can always happen and move on.

        In my opinion you should resolve this mentality before the IOI. If you're driven insane by accidents on CF div2 rounds, I can't imagine how you could feel if you don't meet your exact expectations on IOI.

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

Could you please loose the time limit of Problem D to 2 seconds? I am python user. Usually the system suggests us to submit through PyPy for faster judgement. But this time PyPy is slower than Python 3.

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

Mike Meanwhile mike

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

SyTest please :)

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

Now ,why don't admin ban account of this blog's author as they did mine(for 48hours) just ,for asking my doubt. People usually dislike new members due to there low rating. So my negative contribution doesn't mean i am posting bad stuff ... I received a message from SYSTEM named id 3-4 days ago and my id was banned****..

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

    If you posted public blog during contest, then it's rules violation and it's correct if you has been banned after that.

    If you have some doubts about correct testing then you should ask your question to jury.

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

    the blog goes negative because of the toxic community the author of this blog did nothing wrong

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

      I see the one who posts the blog as the someone who is responsible for any issues related to the problems. If you are not welling to be responsible in case anything went wrong with one of the problems, simply don't be the one who posts the blog.

      Ofc, he shouldn't get downvotes because of problems like server-issues, power outage, or any problems that happens in the round but not related to the setters.

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

Can somebody share the results of an on-site competition?

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

What kinds of wrong solutions did people submit to $$$B$$$?

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

    Something like initially fill row with all horizontal tiles then with vertical tiles doing this alternately.Do this for both cases n*m and m*n and output the maximum

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

If this was the scenario for CF round what happened at the Kremenchuk Summer Programming Cup 2019.

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

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Almost missed submission of my second problem by 5 second ,i was feeling very depressed and angry on myself.. But thank got round become unrated ...

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

    change your profile pic please, this makes me vomit

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

      You child hater , I don't think it's that bad . It's just a cute kid .... It is still better than nothing ,like your profile pic. I will post my real pic after reaching purple on cf.

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

By the way when the system testing starts?

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

can anyone tell me how to solve D.i tried to sum the decimal part of numbers with sign and distribute it among the numbers depending whether the sum is positive or negative?wt is wrong with it?please help.here's the link-https://ide.geeksforgeeks.org/vUNw9LErK6

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

    Well u can just kepp the i terger value and take out the sum of all integer values. If sum is zero then thats the simple answer like testcase 1 and 2 else if its greater then zero than simpy decrease every negative number till sum is not zero and viceversa for if sum is less than zero. This is what is used to solve.

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

      i did the same thing its saying wrong on testcase 7.i took the sum of decimal one.it should be same naa?if decimal sum is positive then integer sum will be negative as the sum should be 0 and vice versa

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

        see my code

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

          be careful about already integer number like 1.0000. I created an ignore list and didn't touch them.

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

            can u give an example where my code is failing .itried on several testcases but it was correct.i tried complete integer an everything

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

              Check this one:

              6
              2.456778
              -1.00000
              -0.456778
              0.456778
              1.456778
              -1.456778
              
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                bro the test case is wrong sum is not 0 for this

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

                  not important in this case, you can make the sum 0 by changing numbers in upper lower bounds. Edit: looks like it makes difference in your solution, I changed it and it gave correct answer: ~~~~~ 6 2.00001 -1.00000 -0.956778 0.456778 1.456776 -1.956786 ~~~~~

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

                  bro read the question it is given sum is 0

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

    Can someone tell me if this is a valid solution for D? 1. Ceil() all the integers up and add them together. 2. Decrement the first "sum" integers by 1.

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

      You can't do it in the case when the fractional part of a number is 0 like 2.00000

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

        Good point. In that case, then keep track of all "fractional zero" valued indexes and skip those?

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

    A hint; start by rounding down all the numbers and working out the sum.

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

      Cant we do either round up or round down? It should be the same idea either way right?

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

Will there be any system testing for this round??

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

This is very annoying, I don't mind that round is not rated,but I hate "artificial" problems,that don't have proof.I was trying to solve B for 90 minutes,before clarification, I couldn't focus on D or C,because I hadn't solved B... I really got annoyed and wanted to stop studying CP...

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

First time ever I was able to solve 5/6 problems in Div 2 and my rating was going to increase about+174 and they declared it unrated so unfair.

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

Why is the contest still "Pending System Testing"? I want to be submit — If the contest is unrated what's the point of not allowing submissions during system tests?

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

In my opinion, tasks in this round was really good, although they didn't swap C and D and difficulty of B is 9999+. Also they could swap F and E but I don't see any problem here. But contest is not only about tasks solving, so the contest.

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why is the system test still pending? Are you guys intentionally trying to make it the worst contest ever now?

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

When will the system test start?

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

    Looking at the screen for system testing besides knowing it is unrated.

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

Before the contest started this blog had over 200 upvotes and now it has 300 downvotes. That means more than 500 people downvoted. People are more interested in downvoting when a contest is declared unrated than upvoting when they see a new contest

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

Since my randomized (in time) F finally passed with a good running time (888 ms), I wonder if F tests are just weak or if anyone can prove the correctness of randomized solution with a high probability?

Link to solution — https://codeforces.net/contest/1186/submission/56215781

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

I solved F using a randomized algorithm. 56216823

While I didn't find an answer, I shuffle the edge array and try to greedily remove edges if possible using the random order. It manage to get an AC. I am still confused why would that work. Does anyone got some idea for a proof?

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

I am waiting for the editorial for problem C.

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

wtf testers, check your mum, why I get AC in F with shuffling edges?

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

Great job with preparation...

Testset in F sucks, many solutions (including mine, but due to a bug, not to being a heuristic) should fail... And most of these which failed, failed on my test from hack... Unfortunately, I didn't have enough people in my room to make tests stronger...

Heuristic in B? Seriously? Prove solutions or stresstest them next time. I'm not telling that everything should be always prepared by 15 people with rating 3500+, but remember, that you show your own quality by preparing a round, so you should do your best, no matter what this "best" means... Here, authors definitely didn't :/

UPD: I totally forgot about it. After making an attempt to hack for the first time, I've received "Unexpected verdict" verdict. Can you explain, please? Was the main solution wrong in some way? If yes, what was the reason? Bug, or similar situation to B?

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

Can anyone explain wat was the problem with Problem B. My code was able to pass all pretest and I didn't also find any problem in problem statement. Can someone please elaborate!

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

    Can you show here your code? I'm also curious about what was intended.

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

      How will I get that code as they deleted Question B so my submission also went off with it. But here I will explain my logic m n are inputs Ans1 = ((m+1)/3)*((n+1)/2) If m%3==1 Ans1+=((n+1)/3) Ans2 = ((n+1)/3)*((m+1)/2) If n%3==1 Ans2+=((m+1)/3) Print max(ans1,ans2)

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

        I thought that you still have it on your computer, sorry then.

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

          Can you please explain what was wrong with the question!!!

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

            I don't know what was wrong with the problem, but I know that your solution is wrong (still something).

            For n=m=4 your solution outputs 3, doesn't it? It's possible to achieve 4.

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

          Code that passed pretests for me (actual method only)

          void solve(std::istream& in, std::ostream& out) {
          		in >> n >> m;
          		int ans1=((n+1)/3)*((m+1)/2);
          		if(n%3==1)
          			ans1+=(m+1)/3;
          		swap(n,m);
          		int ans2=((n+1)/3)*((m+1)/2);
          		if(n%3==1)
          			ans2+=(m+1)/3;
          		out << max(ans1,ans2) << "\n";
          	}
          

          Basically greedily place vertical dominoes with a column gap in between them and repeat with a line gap and if possible place a horizontal row of dominos on the last row with a 1 space gap in between.

          Thinking about it after its pretty obvious to create anti-cases but this is what they expected I guess. Really should have been tested better, since even inputs as small as 4 4 can fail it.

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

            For the case $$$n=4, m=4$$$ the answer is 4.

            Many codes, including this one, prints 3.

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

              I know its wrong, he asked for the code that passed pretests so I posted it, I even mentioned in my post that inputs as small as 4 4 fail

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

                When I started to write the comment, your edit wasn't there.

                I wrote but didn't send. After some time, I did, then saw you edit:)

                Sorry.

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

                  No problem, should have realized something like that was the case, my bad.

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

I forecast that this contest will be unrated

so what can I say?

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

Hey, I have one strange question for problem D. Is it not ok that my solution doesn't submit because it prints -0 instead of 0, or i should remember this feature of C++ for the next time? Here is the code: https://codeforces.net/contest/1186/submission/56215735 (Please rejudge it if it was unexpected mistake)

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

    I don't think that it's fair to say 0 and -0 are different. Even mine also, whole solution to D problem got failed on test case 16 just due to that 0 and -0 thing! Just corrected that and it got accepted. :-(

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

      Same case happened with me too

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

What is the intended solution for F? I gave the contest from my smurf and applied greedy from the start and from the end on the edges given. The solution passed, however I don't think it should have. Please rejudge if the solution is incorrect. Submission: https://codeforces.net/contest/1186/submission/56222396

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

    can you please explain why did you go through all edges two times, first from 1 to m then in reverse order. Is'nt going through only one time enough?

    Actually, I wrote code using same greedy approach but with only one loop and it failed on test case 31

    my code

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

      I initially submitted the solution by iterating only from forward and the solution passed the pretests. However, I realised that it is was such a naive approach yet a lot of submissions failed the pretests. That's when I realised that the solution undoubtedly depends on the order of the edges. So, I did this in an attempt to make a randomised approach so that odds of the solution passing would be higher. I did not expect it to work though.

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

How to solve problem B with (1<=n,m<=10^9)?

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

Why is Problem C tagged fft? Does anyone have an fft solution for C?

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

    Just think about $$$F_i=\sum{(A_{i+j}-B_j)^2}$$$,then if $$$F_i=0(mod\ 2)$$$,the answer adds 1

    So you can reverse B and calculate F using fft

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

Apart from some questions being too easy and some being too weird, I am interested in question E.

The thing which I found during the contest was, ith block (0 indexed and in the same line ) will be same as first block if number of bits in its index is even. else it will be inverted. Then I will calculate all the complete blocks. (Also the Special case when they are odd). Now comes the question of handling incomplete corner row and column. How to do that ?

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

How to solve F?

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

Is problem F really easier than E?

I tried to solve F after 45 minutes(before the surprising announcement). However, I didn't find a solution that I can prove in an hour! Then I gave up on it and turn to E, although only one-third people solved it compared with F... Do you know what happened then? I found a $$$q \cdot logn \cdot log{10^9}$$$ algorithm in just 5 minutes, but there wasn't enough time for me to implement it...

What's worse, after finishing the code five minutes after the end, system testing didn't start. As you know, I waited for a long time.

Then comes the questions:
- How to solve problem F? (All of my friends' solutions get FST qwq)
- Is there a faster algorithm for E?

(In fact, preferring 'first' rather than 'easiest' also happened on me in Codeforces Global Round 3)

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

    About problem E, there is a solution with complexity $$$O(Q*log 10^9)$$$

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

Such an easy F problem, but i can't prove that greedy algorithm is working. Can anybody help? All i do is run through all edges and delete an edge if possible while the number of edges exceeds (n + m + 1) // 2. Very similar to Ford-Bellman algorithm.

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

Nowadays in every div2 contest- I see the B problem is greedy. What is the reason?

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

Sorry for the issues with the round 300 more times.

Intended solution for F was:

Create an imaginary node and connect it to all nodes which had an odd degree in the original graph with imaginary edges. Now, all degrees are even. Now find the Eulerian path. Added (imaginary) edges cut it into not more than $$$\frac{n}{2}$$$ chains. Now from each chain of length $$$k$$$ we will choose $$$\frac{k+1}{2}$$$ edges skipping each second if $$$k$$$ is odd and $$$\frac{k+2}{2}$$$ — first edge and then skip every second — if $$$k$$$ is even. It's easy to see that this way we will take not more than $$$\frac{m+n}{2}$$$ edges in total. Also, it's easy to see that the degree of each node will decrease not more than in $$$2$$$ times as in each chain we take at least $$$1$$$ edge from each node in that chain.

The more detailed solution will be posted in editorial soon (I hope).

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

Guys, why are you so angry at the authors of this round? I understand that you and I expected them to have a well-prepared set of problems so that we can enjoy solving them. They definitely failed in one problem and admitted it. However, why must the authors meet our expectations? We have not hired and paid them. Actually, the authors and CF team owns us nothing. I think we should always take this fact into account while complaining about anything here.

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

    I'm sorry 。I accidentally ordered the bad review.

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

    To be fair, authors are indeed paid for preparing rounds.

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

      I think I have not paid them anything even though I donated money to Codeforces. But I agree that CF team who actually pays authors have rights to require the quality according to their agreement but not participants.

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

    Thousands of participants also paid time to take part in the round, we spend more time on it than the problem setters (the sum of all participants). So, we should thank the problem setters if we enjoyed the round and got help from the problems. If we wasted our time (I admit that some of the problems are good, however, I think there are people struggled with problem B, doubt him/herself, and got accepted with the wrong solution, and thought it was right), if the round didn't "satisfy the need of CF users", we have no reason to thank them.

    What's more, this is a CF round. In my eyes, Codeforcces rounds are a symbol of high-quality contests. If it is a round on CF, the problem setters should not only make efforts but also have to work carefully, take responsibility for the participants.

    However, as arsijo said, "in a week before the round, KAN told me that there is a need of a CF round at the end of this month", the faults are not only on the problem setters. I also want to ask, why a CF round is needed at the end of this month when there are rounds 2 days before and 2 days after if the round is not well-prepared?

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

1186F - Vus the Cossack and a Graph accepted with a randomized solution (56231972). Any counter test or proof?

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

I have slept the round.

Please somebody send problem B preposition because i am curious and it is removed. Tnx

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

    You are given a $$$n \times m$$$ size of rectangle and infinity number of $$$1 \times 2$$$ tiles. You have to fill the rectangle with as many tiles as possible, so that

    • each vertex of each rectangle is lattice point (i.e. both coordinates $$$x$$$ and $$$y$$$ are integer) if you defined an $$$xOy$$$ coordinate whose origin is one of the vertices of the original rectangle, and both axis are along the edges.
    • no pair of two tiles shares any points in common (i.e. they don't overlap each other and don't share edges or corners).

    You can rotate tiles. What is the maximum number of tiles you can place?

    Constrains: $$$1 \leq n,m \leq 10^9$$$ (I guess; maybe smaller? I have a bad memory)

    Example 1: $$$(n, m) = (3, 3)$$$, answer is $$$2$$$, in which case you can place the tiles as follows (different numbers indicates different tiles:)

    1 1 .
    . . .
    2 2 .
    

    I forgot the other example. Hope that helps

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

      The other example was n=4 m=6 and answer 5. The constraints are right btw

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

Can anyone explain the solution for problem C. Please!!

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

    same in two strings: even "1"s

    different in two strings: odd "1"s

    So you just need to maintain the xor value (number of "1"s modolo 2) of each character of $$$b$$$ and $$$a[i..i+|b|-1]$$$, and calculate the number of "1"s in the two strings modulo 2.

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

Can anyone tells me what is wrong with this solution ? 56211719

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

    Some problem in your string/double processing. This is your (modified) code: #.

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

      I don't get it, why using strings is wrong ? or where is the bug in my code

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

Can the authors correct their decision on problem B and add it to the archive? I would like to solve it in good condition.

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

In problem D I first converted all the elements to their floor values. I initialised a variable "dif" that will store the sum of (a[i] — floor(a[i])) for every i. Now dif needs to be added to the elements. So I iterated again and if the element was earlier a float value and dif is greater than 0 I added 1 to this element and decreased dif by one. I am using a boolean array "can" to check if the element was earlier a float value or not. Why is this approach wrong 56231283

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

    I believe that it is floating point roundoff error.

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

      How do I handle that? I got WA in python too

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

        Your method is correct except for the floating point error. To fix that, instead of dif > 0, you should use dif > (some epsilon value that works). You could try dif > 0.5 since dif should be equal to an integer when there is no roundoff error after the first for loop.

        Double is stored in binary format, hence adding exact decimals may not be 100% reliable. For example, in double, 0.2+0.1 != 0.3 (which is counterintuitive). In this case, your final result after addition could have been 1.001, in which a[i]++ would have been done for 2 different i when the intended number of times is 1.

        Alternatively, in Python, you can simply use the Decimal module. The result is exact since everything is worked out in decimal.

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

Is there someone explain to me how to solve E?

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

Anyone help me why my code fails on 7 pretest for problem D.

Thankyou.

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

arsijo In problem C, if it's required to print $$$f(b,c)$$$ [the number of mismatches] for each substring $$$c$$$ of $$$a$$$, is there an efficient way ?

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

Why vote down? This can happen to anyone. Better vote up for the effort made by each setter

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

How to do C? What is the intuition?

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

can any one explain what fft means . problem c has ftt tag .

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

How to solve E?

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

Problem B Page: It is deleted already.  Oh, the picture is rather blurred...

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

    how to solve problem B,if the domino can touch each other?can you give me a practice link?thanks~

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

      In that case the answer is [n×m/2].

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

        sorry, that problem seems to stupid.... what if the area is NxM,and the domino is nxm,how to solve this problem?is there any practice link about this? 3q

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

          Domino is a rectangle formed by two unit squares sharing a side. So it's dimension is always 2*1 or 1*2.

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

how to solve problem B,if the domino can touch each other?anyone who can give me a practice link ?thanks~

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

    if dominos can touch each other, it's much easier, since you can basically fill the board completely, except for 0 or 1 square

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

      thanks what if the domino is 2x3,or 3x4,and so on,arbitrary nxm,then how to solve it?

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

Ok, we apologised your mistakes about problem B, But 3 days had gone but there are no editorial about other problems. This is so sad....

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

UNRATED

That's the result when you forgot to thank MikeMirzayanov for codeforces and polygon platform.

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