AndreyPavlov's blog

By AndreyPavlov, history, 2 weeks ago, translation, In English

Hello, Codeforces!

T4M0FEY, qualdoom and I are glad to invite everyone to participate in Codeforces Round #846 (Div. 2), which will take place in Jan/25/2023 17:35 (Moscow time).

This round will be rated for the participants with rating lower than 0x834 (i.e. 2100). Participants with a higher rating can take part in the round unofficially.

You will have 7 tasks and 2 hours to solve them.

One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

I want to sincerely thank everyone who provided invaluable help in preparing the round and made it many times better:

This is our first official round on Codeforces. We sincerely hope to your participation. We hope that you will like the proposed tasks!

The score will be announced closer to the start of the round.

We wish you good luck and have a good time! See you in the round!

UPD: Scoring distribution: $$$500-1000-1250-1500-1750-2000-2500$$$

UPD: Round is unrated. We're sorry — it's our fault.

UPD: Tutorial and comment about task C Once again, we apologize for the inconvenience caused.

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

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

It clashes with codechef starters 75 https://www.codechef.com/START75?itm_medium=hpbanner_1&itm_campaign=START75. Is it possible to change the time ? Thanks

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

    You should be knowing that Codeforces >>>>>> Codechef.

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

      Codechef tasks can be pretty good too, at least the ones at the end. Well, clashes are inevitable so just upsolve the contest you decide to skip.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        In the past, sometimes Codechef contests and other times, Codeforces contests (like this and this) have been rescheduled to avoid the clashes. So, it's not a given that clashes are inevitable and can't be resolved. Especially, when this Codeforces contest isn't a mirror of some olympiad.

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 3   Vote: I like it +10 Vote: I do not like it

        their plagiarism checker is extremely bad... their community support is really bad...

        I was plagiarised for one contest, in which I solved zero problem, and tried to solve one problem 16 times,,, and still I was plagiarised...

        How can you plagiarise someone, who solved zero problems and tried to solve the problem 16 times !!!!!!...

        if you copy code from someone, why wouldn't u get it right ???

        https://discuss.codechef.com/t/successful-plagiarism/104943/2

        UPDATE : I received response from codechef moderator regarding the plagiarism. According to them, I had solved 2 problems in contest and got plagiarised on 3rd problem.

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

      Yup, it always have been Sir. Looking forward to it. will upsolve last 3 questions of codechef (they are worth it though).

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh no that is an outdated statement. These days codechef problems are really really good.

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

    Well, Codechef postponed it, but now they shouldn't have.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mean Bits-chef??

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

As a tester, the tasks are quite interesting and the statements are clear.

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

    What a joke is this round ? Unrated....

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why C cant be solved in given constraints? What's the problem??

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        greedy approach doesn't always work in this problem

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

        Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe you can test this
        1 25 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 9 4 4 4 the right answer should be 25 cause you can make 1 to c2 c3 c4 and 2 to c1.

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

    Sorry about my shit testing(((

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Git gud LOL, no harm intended!

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

      It feels weird how this issue wasn't caught by so many people during the setting and testing phase.

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

    i am happy because if this round was rated i would get minus :D

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same, i barely made it to 1300 last round

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how many questions you solved on this round for now

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          one completely, but i got stuck on some edge case on second one, not even trying now.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Me too, I took a really long time to solve A and B, and I have no hope of solving the other ones.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if this contest rated,@huanghaoxiang will get 1400+ rating!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a clown**

»
2 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

Tester is me

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

As a tester I can say that I am a tester

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

clashing with codechef, it would be great if timing is changed

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

I Think it's Bitmask Round , I hope it is a misconception

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope it is not (I like those type of problems)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

almost OrangeForces lol

»
12 days ago, # |
  Vote: I like it +23 Vote: I do not like it

Codeforces round is not clashing with codechef round. Codechef is clashing with codeforces.

»
12 days ago, # |
  Vote: I like it +47 Vote: I do not like it
Meanwhile Codeforces Lovers
»
12 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I take my words back ;(
DISAPPOINTED

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

omg orange round

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to solve till D in this round.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wish every contester good luck and happy rating++ !

»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

"One of the problems will be interactive."I think it will be "D".

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish to all positive delta!!!

»
12 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Masters' Round!

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

Will the rating update of this round before educational #142?

Update: Now the rating has been updated.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What should I do To become Specialist

»
11 days ago, # |
  Vote: I like it +17 Vote: I do not like it

hope i can solve problem C,so that i can change a color 。 i dont like green

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

    this didn't age well

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

    Fortunately, I solved C in the last thirty minutes, but there was some wrong with C。IS i solve C?(cry)

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

IS THAT A JOJO REFERENCE??????!!!!!!!!!!11!1!1!1!1!1!1!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Unrated?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why will this round be unrated?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solution of the Problem C which was solved by the author is wrong.

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

I was off to a great start, and then they make the round unrated :)))))

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so C is unsolvable or what?

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

      Idk man, I just used a simple greedy which did pass the protests, but greedy algorithms are hard to prove

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

        Greedy is wrong.

        Consider following example: 102 people like dish 1, 104 people like dish 2.

        Tables are: 51, 51, 26, 26, 26, 26

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Pretests must be weak as shit lmao

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

            I think even setters must have thought greedy was right

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

            It's not that the pretests are weak (the round wouldn't have been made unrated if that was the reason), but the problem setters probably didn't realize that the greedy solution is actually incorrect.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          is the answer not 179?

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

          The answer should be 206, right? I think that's what my solution would give?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If your strategy is to assign biggest group of people to biggest table then this approach fails on this test:

        1 9 3 1 1 1 1 1 2 2 2 2 4 3 2

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

          answer is 8? edit. got it, 9

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It is 9.

            Assign 1's to the tables of size 3 and 2, 2's to table of size 4.

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

          What answer should it be for this case? Edit: sorry, should have refreshed the page.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          is there a way to find out why the greedy approach would fail without using a specific test case. also can it be solved using dp. dp[i][j] ->maximum satisfied customers considering till ith type and j tables.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My strategy was assigning the smallest that fits the table. That would still work?

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            1

            11 3

            1 1 1 1 1 1 2 2 2 2 2

            5 3 3

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              11

              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Explain your algorithm more deeply since I have misunderstood smth.

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

                  Maintain a (multi)set with the group sizes. For each table (sorted in descending order), find the smallest group that has at least that size, and put on the table, and adjust the group size in the set. If none exist, put the largest among the set.

                  EDIT: I didn't prove correctness, but I tried to anticipate the problem with the direct greedy approach

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

                  your solution fails on this test case: 1 10 4 1 1 1 1 1 1 2 2 2 2 3 3 2 2

                  answer should be 10

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  1

                  11 4

                  1 1 1 1 1 1 2 2 2 2 2

                  5 3 2 1

                  Ans: 11

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, you're right; I get 9

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  but i am getting 11 as answer !!

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

                  My code worked too. It gave me result 11

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hello sir, can u tell me ur greedy algorithm?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dont get it then why is it suddenly unrated?

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

Unrated??.. First time solved 3 questions in 40mins

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

"Unranted"

what an absolute bruh moment

»
11 days ago, # |
  Vote: I like it +23 Vote: I do not like it

Solved A+B+C in 26mins , thought I would finally become a specialist :")

But turns out the round is unrated. Sad :(

Anyways, Nice problems , thanks to the authors <3 !

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello sir can u tell me ur solution for C? I am curious and ur help will be greatly appreciated. Thank you.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's greedy approach. But will fail on certain testcases. so yeah..... No solution exits in given constraints.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Sad that round will be unrated. Anyway, I enjoyed solving problems, especially D

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

I was getting some positive delta (110+) after a long time. and now it's unrated. was it really necessary to make it unrated?

Edit:- ohh c is not solvable that's why it became unrated!

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

    Yes, since problem C is unsolvable. The problem setters thought that a greedy approach would solve C but it turns out that greedy doesn't always work. During the contest they realized that C is actually unsolvable within the constraints.

    And no, it wouldn't be enough to just not count C towards the ratings, because different people spent different amounts of time on C and it just wouldn't be fair.

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

What is "can't be solved under given constraints"?? Last I saw, 2752+ correct submissions are there on C

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same question?!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I'm kinda confused since I thought C was kind of easy. Maybe the test cases are weak?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello sir, can u pls tell me your solution for C? It will be greatly appreciated. Thank you.

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

        Though the round is unrated it would be great if this is discussed after contest, ig?

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

      did you use greedy approach ??

      can you solve for this,,, lets say..

      25 people wants to eat dish 1. 15 people wants to eat dish 2.

      tables are 15 , 13 , 12 .

      greedy wont work here... I was stuck here... also, I got stuck in B somehow... got 3 wrong subs..

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        is the answer not 38? table 15 dish 1 -> 15 satisfied table 13 dish 2 -> 13 satisfied table 12 dish 1 -> 10 satisfied

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Answer is 40.

          Everyone who wants to eat dish 2 sits at table 1.

          The rest of the people (people who like dish 1) split themselves between table 2 and table 3. Therefore, there are no dissatisfied customers.

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

        why the greedy wont work here? isn't the answer 15 + 13 + 10 = 38?

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

          Answer is 40 ...

          we will make 25 dish-1 people sit on 12 + 13 table...

          and 15 people from dish-2 on table 15 ...

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    idk man, maybe pretests are well below the constraints.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Perhaps with some input data greedy doesn't work

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe they mean that the mistake cannot be solved within the time constraints of this competition, as the mistake would need be corrected in just a few minutes.

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

    I suppose they mean the actual testcases, not the pretests (which are not comprehensive).

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

    The judge's code is probably wrong as well. The authors thought greedy was correct but it wasn't. Sad way for a good round to go, although I didn't participate

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

I skipped C, solved D, and after 5 minutes round became unrated. Not cool.

»
11 days ago, # |
  Vote: I like it +12 Vote: I do not like it

The way it was going was almost sure of becoming CM today and it became unrated

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

almost 3k people solved a unsolvable problem :/ how? misread? :/

»
11 days ago, # |
  Vote: I like it +70 Vote: I do not like it

the round is unranted, not unrated guys.

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

nothing here

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

    The problem maker have their faults, but you're not expected to be so rude.

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

how is problem C not solvable

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Truly an "Unranted" contest:(

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because it cant be solved using a greedy algorithm. If you have used greedy algo, try this : 7 people want dish "1", and 5 people want dish "2" and we are given 3 tables with accommodation 5, 4 and 3

    SPOILER : the solution is 12 guests can be made happy and not 10

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Garam krke thanda kr diya -_- .

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Baler contest setter.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Here We Go, After Solving ABC Under 30 mins, the round is unrated. WoW.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I feel you, this was my best performance in a long time and the round becomes unrated

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i feel you bro, me too. was hopeful of a good positive delta but then the announcement ._.

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

    The only reason u solved c is because the problem is wrong

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u tell me solution for C? It will be greatly appreciated. Thank you.

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      Testcase
      Greedy Answer(Probably Yours Too)
      Something Better
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I wanted to know what the greedy solution actually was, cos the greedy solution that I came up with was something I already knew didn't work. So i was wondering what greedy solution others came up with and thought worked but actually didn't

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          maintain a priority queue and sort b in reverse, and then greedily pop the maximum element from the pq and and assign them to the maximum table currently available, if not all of them fit in that table then add num_of_people — size_of_table to the priority queue and repeat the process. But this fails on so many test cases so yeah

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh right. That was actually the first greedy solution that I thought of as well. Kinda weird that so many ppl just assumed that it would work when it doesn't.

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

How is problem C unsolvable ?

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

    Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! I understand now. My code (greedy) is giving output for this as 12.

      But, ideally, it should be 13.

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Can anyone explain why Problem C can not be solved?

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

    I think the intended solution was a greedy algo, but it appears, that there are some tests, where it doesn't work

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

    Maybe the intended solution of C is not fully correct and maybe exist some counter case of this solution which makes problem more complicated than supposed to.

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Unrated. Thank you so much.

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

    Why even this single comment can receive downvote I can't understand

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why unrated? Sad. I think constraints are ok

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C please add some tighter testcases/pretests !! But please dont make the round unrated !

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

Codechef round was postponed for an unrated round.

Who would have thought the sequel would be as good as the original https://codeforces.com/blog/entry/103170 https://codeforces.com/blog/entry/103108

»
11 days ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

18 coders could not find this before and what were the testers doing. what a waste of time:(

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was off to a great start, and then they make the round unrated. :/

»
11 days ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it
  1. Is this Rated !!!!! ::: >>>
BIG SPOILER !!!!!!
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was on the verge of becoming a specialist after so long and now the round in unrated..sigh :-)

»
11 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it ranted?

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

This is absolutely ridiculous. It is not expected from codeforces. Nice problems btw..

»
11 days ago, # |
  Vote: I like it +70 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What does "unranted" mean?Unrated?

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

How did so many people get AC in C?

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

    Only pretests are run during the contest and the solutions probably would've failed when run against the proper testcases.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The judge's code probably used the same greedy algorithm everyone else used. They didn't realize that it is actually incorrect before the contest.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The test data is too weak and the testers used the wrong method to produce the test data.

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

can we make it the first contest then where editorial is updated before the contest ends.

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

+165 Delta and it's all gone. Thanks for the great round !

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

It say's unranted, what does that mean?!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No rate updates for the official participants. You can find your rate history in the graph in your profile.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain what they mean by that problem C is unsolvable in given constraints?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my rank would've increased this round :(

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a bad luck for contestant as the contest has been unrated.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

First time in a while I was able to pass pretests on C and now the round is unrated :(

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

This is just sad.

»
11 days ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

My best performance so far.

Bye Bye +125. Top 500 performance.

»
11 days ago, # |
  Vote: I like it +17 Vote: I do not like it

muda muda muda muda muda muda muda muda

»
11 days ago, # |
  Vote: I like it -16 Vote: I do not like it

bye bye +100 (real)

»
11 days ago, # |
  Vote: I like it +15 Vote: I do not like it

I was wondering that how come C be 1250 worth of points but seem impossible to me. I am dumb but not that that dumb(hopefully).

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

    It had an easy-to-think-of greed solution, but now it seems to be a wrong one. The correct solution may be the Knapsack problem, but it cannot achieve the required time complexity.

»
11 days ago, # |
  Vote: I like it +79 Vote: I do not like it

How did so many people falsely solve C? I stared at it for like 20mins and had no idea, but seeing that many people solving it so fast, I started to doubt myself. I tried some stupid greedy ideas but all failed on paper.

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

    Easy hacking greedy passed the pretests.

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

    Given it was only 1250 points, proof by AC is easier to try than a real proof or looking for a counter example :P

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain what is the issue with the constraints?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      exactly what I thought lol

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Speedcoding just does that to you

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

    I guess this really says something about how many people "solve" problems by simply guessing a reasonable-looking greedy.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      B was guessable too

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am still not sure, how to solve problem B optimally...

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's ideal to split the array into 2 subarrays.

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

        I mean maybe, but the point is that C is literally unsolvable — so anyone who actually proves their solutions wouldn't have solved it.

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

          I think the problem is that everybody writing was trying to get AC — and the greedy prrof is somewhat easy to think up really fast. None of the testers really struggled on the task, except me.

          The issue should have been caught by me — when we were "testing", I did not manage to solve C (it was B then) in contest, and I submitted like 7 wrong (all greedy) solutions to it. Then, when I was asking the author about the solution, I was told that it is "a simple greedy". Then, I decided to believe him and did not upsolve that task. I should have caught it.

          So I think that the CF system of less points with more time will always incentivize this sort of "half-done" proofs.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I proved B before solving it. But when I came to C I just guessed some unproved greedy approach and got WA for silly mistake then I started doubting this approach and couldn't come with another one.

        My problem solving skill is slowly goes from random guesses to prove-first approach or even partially-proved approach after watching many streams from tourist, um_nik, and many other legends.

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

      simply guessing a reasonable-looking greedy.

      Is this a common thing among highly experienced users when it comes to simpler problems (say div 1 A-C)?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you go to the "status" page and look at all C AC's, the fact that most of them are 15ms should point at a sub-quadratic solution

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

I see many people solved C !!
why c is unsolvable!?
why the round unrated?◑﹏◐

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

    Seems that greedy solution of C is not correct

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

+114 ...and then its unrated

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

Testcase for problem c that dosen't work whit the greedy metohd 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5

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

don't do it unrated pls

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Not Happy with the contest making today :(

»
11 days ago, # |
  Vote: I like it +15 Vote: I do not like it

This contest is a disgrace to the Joestar Bloodline!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the problem with C?

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

    did you use greedy approach ??

    can you solve for this,,, lets say..

    25 people wants to eat dish 1. 15 people wants to eat dish 2.

    tables are 15 , 13 , 12 .

    greedy approch will fail,, for 25 dish guests we can pick 12 + 13 = 25 , and 15 for rest.

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

      I see. How did I not see that lol? Speedcoding I guess. What would be a good dp formulation for this assuming bounds are low enough?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        after solving A , I tried solving C... couldn't solve that...

        it is basically knapsack problem with 'K' sacks given to us...

        where 'K' is number of distinct elements given in array.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is the answer 12 ? I mean its working fine on my local environment. can someone hack my solution please I am feeling to much smart for getting my solution accepted.

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        u put the 9 ones at the three 3 ppl tables and the 4 guys at the table of 5 and the answer is 13

»
11 days ago, # |
  Vote: I like it +29 Vote: I do not like it

What the fuck?

The solution is $$$8$$$, not $$$9$$$?

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

    It is 9, author's solution is wrong.

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

    Maybe the standard code also used the wrong greedy method and fails on this.

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

C looked so hard to me with given constraints. Looked like a multiple knapsack problem. The knapsacks are your guests that like dish $$$i$$$ and the items are the tables. In this version you can keep feeding a full knapsack but gain no score. I tried greedy strategy on papers, they all had edge cases. Couldn't find a dp. Best algo I found was like $$$O(m^{\sqrt{n}})$$$. I really wonder what happened there :)

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

    the dp i came up with was something like dp[i][j]->max satisfied customers considering till ith type and till j seats. so dp[i+1][j]=max(dp[i+1][j],dp[i][k=0 to j] + min(count[i+1],summation till k)) ps:i did sort the tables though

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm not sure what you mean with "count[i+1]" and "summation till k". Have you tried your solution with the counterexemples to many greedy approaches that were given in the comment ?

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

        count simply stores the number of customers who like ith type of dish and summation till k means we add all empty places from c0 to ck. i tried it for 7 3 1 1 1 1 2 2 2 2 2 3 this one

        the correct answer is 7 and it worked for this one and the pretest.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what is unranted?. In the announcement it says the round is unranted not unrated.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same thing unranted means not having received a rating or assessment.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Only if the contest makers had a stand for stopping time like ZA WARUDO

»
11 days ago, # |
Rev. 4   Vote: I like it +20 Vote: I do not like it

Unfortunately,the round will be unranted.We apologize,we made a mistake in problem C and it cannot be solved with in the given constraints.

Notice that it is unranted instead of unrated. Does it mean that this round still needs to be rated?

UPD:Now this round has become unrated. It is really a frustrating round.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

In an interactive problem, TLE means i am taking more operation than the available operations ?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the interaction instructions carefully: "If your program performs more than 30 operations for one test case, subtracts a number x greater than n, or makes an incorrect request, then response to the request will be -1, after receiving such response, your program must exit immediately to receive the Wrong Answer verdict. Otherwise, you can get any other verdict."

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why this round is unrated??

»
11 days ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

sorry to hear that it's unrated..

and a wrong example for many solution including mine:

1
7 3
1 1 1 1 2 2 2
3 2 2

the answer is 7 instead of 6.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is that extension bro?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      CARROT

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you mean why the answer should be 7?

      let the room be $$$c_1, c_2, c_3$$$ , then we can match $$$c_1 \rightarrow 2*3$$$, $$$c_2 \rightarrow 1*2$$$ and $$$c_3$$$ the same.

      If you use a greedy like me, the match would be $$$c_1 \rightarrow 1*3$$$, which is obviously wrong ;_;

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Carrot

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, i misunderstood...

      it's Carrot, also CF predictor is another good choice.

»
11 days ago, # |
  Vote: I like it +150 Vote: I do not like it

I'm curious how these testers test this round?

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Bye bye my hopes and chances to become pupil...

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Feel u brother! My rating position is almost the same as yours!

»
11 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Funny that a large portion of the top 100 participants didn't even attempt C because they knew it to be impossible

»
11 days ago, # |
  Vote: I like it -36 Vote: I do not like it

Trash Russian Round.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What about those who had solved C in O(N)/O(NLogN) :(

»
11 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

There has been 2 times in the past year when CF rounds and CC starters rounds are planned to clash with each other. One of it was postponed both times, and in both occasions, the round that is not postponed became unrated [Lol]

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Why the announcement says

Unfortunately, the round will be unranted. We apologize, we made a mistake in problem C and it cannot be solved within the given constraints.

instead of "unrated"?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this round is still rated for the time being, but it may become a unrated round. Because there are mistakes in this round of questions.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unranted is not unrated, so it's still rated.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      UPD: Round is unrated. We're sorry — it's our fault.

      Now this round has become unrated. It was a frustrating round.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, Unra'n'ted.

So, does the std solve this problem with greedy algorithm? lmao.

1
7 3
1 1 1 1 2 2 2
3 2 2

answer: 7

»
11 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Could have attended the Codechef contest instead. Whatever ...

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to prove B?

  • »
    »
    11 days ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    If g divides a and b, it divides a + b. That implies [there was typo mistake] gcd(a + b, c) >= gcd(a, b, c), which means that if you have some partition you wouldn't get worse solution if you delete some intervals.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's say your optimal answer has k partitions, whose gcd is 'x'. We can merge the first k-1 partitions and the gcd will either increase or stay the same.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose that k >= 3 in optimal answer. Let d be the answer for testcase. Then you can combine some two neighboring segments in one segment and get a solution no worse than the previous one. It's because if d | a and d | b then d | (a+b) and you got answer for k — 1. So in optimal answer k = 2 and you get your solution

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you only need to split array into 2, If you get some gcd 'x' by splitting more than once, then you can club all untill there are 2 subarrays because each subarray is multiple of 'x' and sum of them will also be multiple of 'x'.

»
11 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Why not just remove problem C and extend the round by 15-30 mins rather than declare it unrated?

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

    because some people have spent time on this problem, and some people haven't

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

Guys go easy on the Downvote Button
Mistakes were made

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

To all the people that solved C, How did you fakesolved it? I'm interested in the "expected solution".

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

    Greedy. Didn't even realize it was wrong lol