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

Автор AndreyPavlov, история, 22 месяца назад, По-русски

Привет, Codeforces!

IzhtskiyTimofey, qualdoom и я рады пригласить вас на наш Codeforces Round 846 (Div. 2), который пройдёт в 25.01.2023 17:35 (Московское время).

Раунд будет рейтинговым для всех участников, чей рейтинг будет ниже 0x834 (то есть 2100). Участники с более высоким рейтингом могут принять участие в раунде неофициально.

Вам будет дано целых 7 задач и 2 часа, чтобы их решить.

Одна из задач будет интерактивной. Обязательно прочитайте этот блог и ознакомьтесь с этими типами задач перед раундом!

Хочу искренне поблагодарить всех, кто оказал бесценную помощь в подготовке раунда и сделал его в разы лучше:

Это наш первый официальный раунд на Codeforces. Мы искренне надеемся на ваше участие. Также мы надеемся, что предложенные задачи вам понравятся!

Разбалловка будет объявлена ближе к началу раунда.

Желаем удачи и приятного времяпровождения! Увидимся на раунде!

UPD: Разбалловка: $$$500-1000-1250-1500-1750-2000-2500$$$

UPD: Нам очень жаль, но раунд признан нерейтинговым. Приносим свои извинения — это наша ошибка.

UPD: Разбор и комментарий по поводу задачи С. Ещё раз приносим извинения за предоставленные неудобства.

  • Проголосовать: нравится
  • -628
  • Проголосовать: не нравится

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

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

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

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

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

      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.

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

        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.

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

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

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

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

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

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

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

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

»
22 месяца назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

Tester is me

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

As a tester I can say that I am a tester

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

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

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

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

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

almost OrangeForces lol

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

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

»
22 месяца назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится
Meanwhile Codeforces Lovers
»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I take my words back ;(
DISAPPOINTED

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

omg orange round

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

Hoping to solve till D in this round.

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

wish every contester good luck and happy rating++ !

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

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

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

Masters' Round!

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

The One piece is real!!!It said Lion C. BlackBeard.

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

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

Update: Now the rating has been updated.

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

What should I do To become Specialist

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

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

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

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

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

Unrated?

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

Why will this round be unrated?

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

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

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

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

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

"Unranted"

what an absolute bruh moment

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

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 !

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

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

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

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

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

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

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

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!

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

    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.

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

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

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

    same question?!

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

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

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

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

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

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

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

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

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

          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.

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

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

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

          Answer is 40 ...

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

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

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

    idk man, maybe pretests are well below the constraints.

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

    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.

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

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

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

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

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

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

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

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

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

the round is unranted, not unrated guys.

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

nothing here

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

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

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

how is problem C not solvable

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

    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

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

Garam krke thanda kr diya -_- .

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

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

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

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

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

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

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

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

    • »
      »
      »
      22 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Testcase
      Greedy Answer(Probably Yours Too)
      Something Better
      • »
        »
        »
        »
        22 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

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

          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

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

            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.

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

How is problem C unsolvable ?

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

    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

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

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

      But, ideally, it should be 13.

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

Can anyone explain why Problem C can not be solved?

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

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

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

    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.

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

Unrated. Thank you so much.

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

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

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

Why unrated? Sad. I think constraints are ok

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

Where are the testers when a problem is unsolvable? What did they test?

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

Codechef round was postponed for an unrated round.

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

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится
  1. Is this Rated !!!!! ::: >>>
BIG SPOILER !!!!!!
»
22 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Is it ranted?

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

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

What does "unranted" mean?Unrated?

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

How did people fakesolved C, I'm interested, I have a knapsack idea but the number of states goes exponential if the number dishes with at least one person who want it is $$$\ge \sqrt(n)$$$

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

How did so many people get AC in C?

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

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

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

    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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Test case that dosent work whit the greedy solution 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 Output should be 13

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

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

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

my rank would've increased this round :(

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

This is just sad.

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

My best performance so far.

Bye Bye +125. Top 500 performance.

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

muda muda muda muda muda muda muda muda

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

bye bye +100 (real)

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

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

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

    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.

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

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.

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

    Easy hacking greedy passed the pretests.

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

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

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

    Speedcoding just does that to you

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

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

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

      B was guessable too

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

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

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

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

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

          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.

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

        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.

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

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

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

    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

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

This contest was a disgrace to the Joestar Bloodline

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

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

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

    Seems that greedy solution of C is not correct

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

    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

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

Great round and wcnm !

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

+114 ...and then its unrated

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

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

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

don't do it unrated pls

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

Not Happy with the contest making today :(

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

This contest is a disgrace to the Joestar Bloodline!

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

What was the problem with C?

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

    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.

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

      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?

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

        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.

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

    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

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

      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.

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

What the fuck?

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

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

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

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

    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

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

      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 ?

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

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

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

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.

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

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

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

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

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

why this round is unrated??

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

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.

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

    What is that extension bro?

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

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

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

      Carrot

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

      sorry, i misunderstood...

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

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

I'm curious how these testers test this round?

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

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

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

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

»
22 месяца назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

Trash Russian Round.

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

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]

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

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"?

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

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

»
22 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

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

How to prove B?

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

    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.

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

    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.

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

    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

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

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

»
22 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

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

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

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

Guys go easy on the Downvote Button
Mistakes were made

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

I think nmsl

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

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

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

    Greedy. Didn't even realize it was wrong lol

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

    As a contestant it is highly expected to come up fast with a wrong solution by intuition especially with greedy. But as a round tester a plenty of time is there to test the problems thoroughly. Such kind of mistakes wastes time of others.

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

Such a frustrating moment solved 3 problems in 30 mins and then what??UNRATED. Good Bye +170

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

    considering solution of B is cringe and everyone typed it without any proof i guess its fair

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

      The proof is simple though. If $$$gcd(a,b,c) = k$$$ then $$$gcd(a + b, c) \geq k$$$ since $$$ k \mid (a + b)$$$.

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

Hi @AndreyPavlov & fellow setters and testers

Questions are great, mistakes happen! I really enjoyed the questions and logic used. Doesnt matter if round is unrated but I really enjoyed the questions. Thanks for the contest. Much love <3

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

For C, 1 7 3 1 1 1 2 2 2 2 2 2 3 Actual answer is 7 with optimal selection type 1 table 3 type 2 table 1, 2 But Greedy gives 6 type 2 table 3 type 1 table 1, 2 one person with type 2 is not satisfied

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

Volveré y seré millones

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

respect. GOA T

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

Those who solved C what was your approach?

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

I wonder why coordinator and many testers didn't even realize this problem.

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

Imagine Masters not recognizing NP-Hard problem when they see one.

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

Is C unsolvable? We could just add stronger tests and re-judge all submissions. It is solvable surely because the first AC solutions were by GMs. Would like to know more about the reason behind taking such a big decision, skipping other alternatives like re-judging solutions.

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

    It can be proved to be unsolvable in polynomial time by reduction to 3-partition. The grandmasters who solved it were wrong.

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

      topg for a reason

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

        Can you please elaborate a little?

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

          to prove that a problem is NP-hard you can consider another problem known to be NP-hard, 3-partition in the comment by Everule, and then show a relation such that if this problem is solvable then 3-partition is solving.

          this means that this problems is atleast as hard as 3-partition which we do not believe to be solvable in polynomial time.

          everule is topG because he never guesses and anyone who never guesses is topG

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

            I see thank you. :)

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

            In C, sum of all numbers is bounded so you can't really make a reduction.

            3-partition is only NP-hard in number of elements, not when the sum if bounded

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

              Prolly, I didn’t look into the reduction, was just explaining what the process is

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

      You mean the other way around, reducing 3-partition to this problem?

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

        And even then it doesn't imply unsolvability in polynomial time (probably)

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

          I may have messed up the direction of reduction, because I don't have experience in theoretical CS, but solving this problem in polynomial time breaks the fact that 3-partition is strongly NP-complete. i.e., That even if the integers are bounded by polynomial in $$$n$$$, which it is, the problem is still not solvable in polynomial time.

          • »
            »
            »
            »
            »
            »
            22 месяца назад, # ^ |
            Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится
            • The original version was incorrect

            Let us pick a set $$$S$$$ of with sum and size divisible by $$$3$$$ to 3-partition. We bound every element in $$$S$$$ to $$$sum(S) \times \frac{3}{4n}$$$ and $$$sum(S) \times \frac{3}{2n}$$$. This is also strongly NP-complete. Now we make $$$n/3$$$ groups of people, each consisting of $$$sum(S) \times \frac{3}{n}$$$ people, and tables consisting of the sizes of $$$S$$$. The optimal solution to this is a 3-partition if it exists. Notice that any solution with all must be a 3-partition due to the bounds on set sizes of $$$S$$$.

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

              I just say that if P = NP then you can solve NP-complete problems in polynomial time

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

              That's not polynomial solution, that's pseudo polynomial solution, as the total sum, T, is bounded.

              I believe 3-partition can be solved in $$$O(NT^3)$$$ (which is pseudo polynomial) with a 3D DP, similar to double knapsack.

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

                3-partition is strongly np-hard, so probably you can't even solve it in poly-time when the input is given in unary (base 1).

                it looks like you are confusing dividing a set into 3 subsets with dividing an array into triplets

                edit: oops, looks like it was everule who confused them. you're right that the reduction everule posted is solvable in pseudopolynomial time.

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

                  Yeah I was wrong, splitting an array into 3 sets with the same sum isn't the same as splitting it into triplets...

                  I wonder if it's a first proven NP-hard problem on Codeforces

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

                  Yeah, I've fixed the reduction, I messed up while looking for it.

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

                3-partition can't actually be solved in pseudopolynomial time (assuming P != NP). And it's probably a different problem then you're thinking.

                The problem is: given an integer B, and a set of $$$3n$$$ integers, partition the set into n groups, such that sum in each group is equal to $$$B$$$.

                This problem is strongly NP-complete, so even if the numerical values in the input are encoded in unary (so a value of $$$A$$$, takes $$$A$$$ bits to encode), it is still NP-complete. The reduction from 3-partition to problem C is as follows:

                Given arbitrary instance of 3-partition, where numbers are encoded in unary. Then make $$$n \times B$$$ guests, divided into n groups of equal $$$a_i$$$, each of size $$$B$$$. The set of $$$3n$$$ integers S, just make that into $$$c_i$$$'s. Now you can show that answer to problem C for this input is $$$n \times B$$$ iff the instance of 3-partition was solvable, Almost... One problem we face is that inside one bucket there can be more or less than exactly 3 elements. To fix this, we can add a sufficiently big enough number to each number in the set S, and add three times that number to B. This enforces that not too many numbers can end up in one bucket.

                And it's a polynomial time reduction, because $$$n \times B$$$ is polynomial in the input size, (and even if you increase by that sufficiently big number, you can still choose that as polynomially as big as the input).

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

                  Jeroen there is another cool result, that makes the constraint on triplets quite easy in the wikipedia article

                  The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.

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

I find it so funny to see many people complaining about the round going unrated saying: "I solved three problems" when they literally fakesolved one of them.

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

"Rant" means "roar".

Then "Unrant" means "No roar"

Then writers means that "The contest is without roar."

Well...

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

For problem D,

Spoiler

Is this wrong? I think it's probably wrong, but looking at the #of submissions is making me think that smth like this might work. Can anyone tell me if this is the intended sol? Please no other spoilers about any intended solution btw.

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

    try with 35

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

      Thanks, I see the problem now. I'll try smth else and pray it works lol

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

    good idea, but i think there is an arbitrarily large number with weird binary sequence that can counter that, because the number could've just decided to troll you lol (A.K.A the input is always small, in which the queries would exceed 30). better way is to subtract it in a really interesting way to the point that its final form would be 2^input-1.

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

      Yeah, I found a solution that will work. I'm such an idiot lol. Will code it up after school. Edit: Got AC

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

    I tried the same.

    It does not work. Offline I tried for 10**9 and it needed more queries than the limit.

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

I would've become red today, if only it was rated :( /s

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

author, tester and contestant all guessed solutions

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

Contest would have been fine if C was just removed during testing or something

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

    People wasted time on it , that's why this is not fair

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

      "If C was removed during testing"

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

        Yes !

        some people got pretests passed fast and others took time

        this time affected other problems

        so it is not fair(although I was really good in the contest)

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

    Nah , some people who knew that greedy solution is wrong may have had wasted time on C which they could have used to solve other problems.

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

ABCD in 45 minutes and really near of reaching CM

If the author did a mistake it's ok ,but what were the testers doing !!!

I think the main testers job is to find things like this

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

There is no need to be harsh on tester guys! Everyone makes mistakes . I hope fellow testers learn from this and try not to do such mistakes in future!

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

Does anyone figure out the correct answer to Problem C even if it may get a TLE or MLE?

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

    You can just brute force all the possible combinations. There is probably also some dp solution, but it has non-polynomial time complexity.

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

I've found an easier version of problem C, how to solve it?

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

I would get about + 120 and the round was unrated ToT. Anw still a good contest

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

    Is the rating change just a guess or is there anywhere to calculate this estimate?

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

      There are extensions like CF Predictor or Carrot that let you see the rating change you are going to get while the contest is still running.

      These update live during the contest depenging on how you're doing compared to others but they are not always exactly correct (typically the actual rating change is within +/- 5 points compared to the predictor).

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

F

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

Actually today's situation remind me of a contest held many years ago, whose div1.b was also a greedy hacked by a talented coder Um_nik

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

Maybe C was a blunder, but after all last 3 problems are quite a challenge, so the setters are not as bad, as you think

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

I'm curious. You didn't even prepare a brute force solution to stress-test problem C? I thought stress-testing is a "must" when you prepare a problem?

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

Most normal contest in Ohio 💀

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

Thanks for the problems. D was a good problem btw but it seems more suited as a replacement for C.

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

gcd round :(

»
22 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

And this round

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

its still nice problemset mens, shit happens, but i like this round anyway

»
22 месяца назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Use me as a dislike button

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

so sad it got unrated, even though D is a fun question to do (as a math nerd and interactive problem fans lol :p). also, how do you dp problem C?

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

I want divide something, is it OK?

»
22 месяца назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

Me after the announcement:

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

Не расстраивайтесь, раунд все равно крутой.

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

    .

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

      Ну я с вами очень не согласен, задачи были по анимэ Jojo's bizarre adventure что очень обрадовало меня а также Задачи были очень оригинальные

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

        Не всем нравится Jojo

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

          Ну а оригинальность задач?

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

            Ну, лично мне не понравилось, что G — просто упражнение на суффавтомат. Оригинальность так себе...

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

for the sake of interest, it's still worth doing strong system tests against the greedy approach. my solution has been undergoing stress testing for more than half an hour. sorry for poor english

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

Problem F seems intresting. How to solve it?

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

    Sort the numbers, find the divisors for each number and then use mobius function with prefix sums and some tricks.

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

Regardless of problem C and the round being unrated, I really enjoyed the problems and it could have been my master round.
Thanks for making an amazing contest :D

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

    Agree if C was removed with the problems starting from D being shifted, it could've been one the best rounds made recently :)

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

Yes, the author's solution in C was incorrect. We haven't noticed it in 9 months. We stressed this solution (as it turned out, we stressed it terribly), I even wrote an analysis with a proof of this greed. Now an exercise for the reader, find the error in this tutorial:

Tutorial
  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -48 Проголосовать: не нравится

    1
    15 3
    1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
    7 4 4

    Courtsey — NemanjaSo2005

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

    In the second case, if $$$b_i$$$ are seated, then there are $$$0$$$ empty seats, but there are also $$$b_i-c_k$$$ extra people, compared to $$$c_k-b_j$$$ empty seats if $$$b_j$$$ are seated. It's not obvious that seating $$$b_i$$$ is better.

    In the third case, it's not necessarily true that having a larger maximum is better.

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

    It happens :) I am happy you did not let me lose my sanity over 1 hours while trying to solve C :P

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

    It's kinda hard to find a particular error in a text that doesn't make any sense. For some reason you are minimizing empty seats, how is it connected to the actual problem — I don't know. Then there are just random phrases like "it is better for us to have a maximum as large as possible". Why is it better?

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

      This is how I understand it: for each table they choose people from the same group — these are going to be the "satisfied" people for that table. The number of free seats is then some constant minus total number of satisfied people, so we try to minimize it. What they do in the "proof" is they prove that the solution is greedy, i.e. at each step we are indeed minimizing the number of free seats for the current table. The error is that they never prove that greedy actually works.

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

    "stressed this decision" -- solution, not decision

    It's incorrect translation from Russian, I guess

    Upd: fixed

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

    The main problem in the proof is that you never took into account that your choice for the current table might affect the other tables. If you were assigning people to only one table, the greedy is perfectly valid. Additionally, if all tables had the same capacity, your greedy is completely valid. Bullet point 3 is the one about which I am talking. You said that it is better for us to have maximum as large as possible, without providing proof for why. As it turns, that statement is incorrect as can be seen in the example above. I know that the proof looks quite logical and it seems to intuitively make sense. However, intuition can be really misleading sometimes.

    I honestly feel quite bad for you and the rest of the authors as this was your first contest and it went the way it did. I cannot imagine how bad you all are feeling, especially with all the hateful comments from some individuals in codeforces community. But I do not suggest you quit either CP or problemsetting because of that. (Your choice, I am just giving a recommendation) Everyone makes mistakes and it can be a great opportunity to learn and improve.

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

    Local best solution doesn't equal to global best solution I think. For example, let's seat 4*1 and 3*2 into 3 2 2, and surely placing 1 or 2 into 3 can fill this single table, but the cases after that become very different. Just like why we can't use DP sometimes.

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

    I think one problem is that you are assuming that "at the next iterations of the algorithm, it is better for us to have a maximum as large as possible", which is incorrect. If we have c = {3, 2}, b = {3, 2} gives a score 5 while b = {4, 1} gives only 4 although it has a larger maximum.

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

    what you are trying to convince in the last section of 2nd point is that for a fixed c array the lexicographically bigger b1 is always better compared to a smaller b2 (both having same sum and b1,b2 are sorted),now,what if c is exactly same as b2?

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

Could you please update rating only for those, who has positive delta?

UPD: Nevermind, just found out about C a little bit late

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

    Could you please update rating only for those, who have 0 delta?

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

I know the complex progress of contest preparation. It needs a lot of effort and attention, but there are many testers I am shocked by this annoying situation. The reason for my participation in Codeforces contests is not ranking. I am joining contests for having fun and learning some new things. But I thought my solution will get the wrong answer verdict while submitting but when it got accepted I got shocked. I hope testers and problem setters of this round will be more careful in the future.

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

why "locale=ru" in the tutorial link
Oh it's fixed now.

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

Авторы, раунд был клёвым! Спасибо вам за него, очень обидно видеть такое количество негативных голосов :(

Никого не слушайте, многим раунд понравился!

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

    ну да, легче похвалить авторов за провальный контест и написать что-то про зеленых (при чем тут они вообще? или ты так хвастаешься, что у тебя рейтинг слегка выше?), чем признать факты

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

      И в чём же помимо С контест провальный?)

      И о каких фактах идет речь?)

      А при чём тут зелёные — пролистай пару сотен комментов выше и проанализируй спектр рангов жалующихся пользователей. Хотя речь шла даже не о цвете, тебя я бы тоже к плачущимся зелёным причислил ;)

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

        Ошибка с С и означает, что контест провальный. Наверное, когда основной смысл этих соревнований — получение рейтинга, становление соревнования нерейтинговым — огромная ошибка, тебе так не кажется? А поводу зеленых — их просто больше, вот и жалоб больше

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

          Однако, не для всех основный смысл соревнований — получение рейтинга. Да, становление раунда нерейтинговым — проблема, да, косяк со стороны авторов, верно. Напомню, что были тестеры и координатор, которые не выявили проблемы. Так же, как и не выявило (бы) абсолютное большинство участников. Поэтому неплохо было бы быть объективным, а не судить с точки зрения что кому бы то ни было не додали рейтинга

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

        условный комментарий "мне не нравится задача X контест плохой/я не смог решить задачу X контест плохой" — субъективная оценка качества. Точно также, как и "мне понравилась задача X...". А когда раунд становится нерейтинговым по вине авторов — объективно, это провал. И не важно, насколько задачи (по твоему мнению) хорошие или плохие

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

          Хорошо, с этим доводом согласен. Переформулировка "Проблемсет был хорошим и мне понравился" тебя устроит?

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

A: If there's no odd numbers, or n==3 and there's 2 odd numbers, no solution. Otherwise we can find 3 odd numbers or 1 odd number and 2 even numbers.

B: Note that common divisor of (a,b,c) would also be common divisor of (a,b+c), it's always optimal to divide the array into 2 segments.

D: First let q=1 and query(q). If the bitcount is reduced, the last bit of n is 1 and you've just cancelled it, then you need to try for q=q<<1 (which means, left-shift q to the next unknown bit). Else the last bit of n is 0, and by count the difference of bitcount before and after the query, you'll know how many zero bits was on the tail of n, and you've just fliped them to 1 (and a 1-bit to 0). Then you can cancel these 1-bits in one query, and left-shift q to the next unknown bit. In the first situation, you've got the information of the least significant bit by one query, and in the second situation, you've got the information of at least 2 bits by 2 queries. Thus by repeating this process we can get the answer.

E: Sqrt decomposition. Consider for gcd(u,v) in [1,ceil(sqrt(L))-1], [ceil(sqrt(L)),L-1] and [L,R/2] respectively.

PS: It's regrettable that the contest was ruined by an incorrect problem, and many great contestants lost their positive delta. It's a pity that problem D,E are pretty well-designed.

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

Solve count for C shows why cf is just guessforces nowadays

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

So what happens to C about it being it problemset. I think C must be removed from problemset too.

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится +48 Проголосовать: не нравится

Brief solutions(hints) besides G,I'm weak in string problems.

A
B
C
D
E
F
»
22 месяца назад, # |
  Проголосовать: нравится +120 Проголосовать: не нравится

Solve count for C during contest shows why cf is just guessforces nowadays

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

first time got approach of D but unrated its ok:) :)

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

rip my >100 positive delta ;-;
Anyways it’s still a fun round with other problems being interesting

»
22 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

First time I solve 5 problems in div2. 140 positive delta. I would've been div1. Big bruh moment.

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

first time got approach of D but unrated , its OK :)

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

E could have been written as "Constructing a graph with vertices from $$$l$$$ to $$$r$$$" instead of "deleting all other vertices and all other edges", would be much easier to read and understand lol

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

    E could have been written without any graphs at all. You just assign weights and right after that throw them in the set to count the number of unique values. There is nothing graph-y about this problem.

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

this is my first time that I solve the last problem and rk110- in div.2,although it is unrated,I think it still be a good contest

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

meme

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

AndreyPavlov Please remove problem C from codeforces as it can be harmful for people who try to solve it later during practice or something.

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

What ever happen, I still love codeforces

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

what's wrong with problem c? this is the quickest i solved a,b,c and this round gonna be unrated fek

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

It's so terrible to do system testing C with the wrong test case.

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

I am kind of curious: how were there so many AC on C, even tho it could not be solved? Did people just submit a greedy solution?

Also curious: what would be the best possible runtime for a correct solution?

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

can problem B solved using binary search on answer?

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

Can anybody tell why the output for this test case is — 10 , Problem C

TC 16: 1 11 3 1 1 1 1 1 1 2 2 2 2 2 3 3 5

(1,1,1) (1,1,1) (2,2,2,2,2)

I thin we can make all 11 happy

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

Can someone give a test case where this approach gives a wrong answer to C?

  1. Calculate how many meals of each type and how many tables of each size there are.

  2. Go through the meals, if there is a table with the same size as the count of that meal, then put those people to that table.

  3. Put remaining meal and table counts to two priority queues. While there are still some empty tables or not all people has a spot: take the top of meals and put them at the biggest empty table, if some people who like that meal are still left, check if there is empty table with that amount of spots, if there is put them there, otherwise put that number back to priority queue.

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

    1

    15 4

    1 1 1 1 1 1 1 1 2 2 2 2 2 2 2

    5 4 4 2

    The answer is 15, but your approach would give 14.

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

      Thank you sir

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

      hello sir, my approach works for some of these type of test cases, can you tell me where my approach can go wrong? Sort the tables array in descending order, and we keep the frequency of elements in a multi set, and for every table from largest to smallest we find the lower bound of the table size in the multiset, and we assign the table size to that many people of same type, and erase the people that are sitting in the table in the multiset and the extra people left will be put inside the multiset again, we do this if the lower bound exists, and if the lower bound does not exist, we just assign the maximum element of multiset to the corresponding table. In test case 16: the array was 1 1 1 1 1 1 2 2 2 2 2, and the table given was 3 3 5 And the answer to this test case according to my solution is 11, but the given answer is 10 which is wrong.

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

        Your approach assigns people to the table without caring about what kind of effect it might have on other tables. That's the main reason why no greedy solution works.

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

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

    Nice one. I didn't solve C during the contest and was wondering how 1000 people solved it. Shows how people don't understand their solutions and can't prove it.

»
22 месяца назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

I hope Codeforces will hold a good competition next time, instead of being as rubbish as this one

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

D is really an interesting problem

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

i didn't participant in the contest yesterday, and only see people are talking about the unsolvable problem C. but now actually i even can't see what exactly is the problem statement, where can i find it? thanks

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

    The problem was something like this:

    You are inviting people to a party. There are $$$n$$$ people, and the $$$i$$$ th person likes the dish $$$a_i$$$ $$$(1\leq i\leq n)$$$. You have $$$m$$$ tables, and the $$$j$$$ th table has a capacity of seating $$$c_j$$$ people $$$(1\leq j\leq m)$$$. Now, for every $$$1\leq j\leq m$$$ you have to select a dish $$$x_j$$$ to serve at the $$$j$$$ th table, and the people seated at that table who like that dish will become happy. You have to maximise the total number of happy people by selecting what dish to serve at each table.

    Input: Arrays $$$a$$$ and $$$c$$$ were given in input

    Output: Just print a single integer, i.e. the maximum number of happy people possible

    Constraints: $$$1\leq n\leq 2\cdot10^3$$$, $$$1\leq m\leq 2\cdot10^3$$$, $$$1\leq a_i\leq n$$$, $$$1\leq c_j\leq 2\cdot10^3$$$ and $$$\sum_{j}c_j \geq n$$$ (i.e. total number of seats is more than number of people, so every person can be seated)

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

Hi guys! If you wanna know why problem C was wrong, and the editorials for A,B,C,D then you can check it here — https://www.youtube.com/@GrindCoding

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

Does this solution for C work?

Take the array of guests and put 1 extra element in it, let's call it breaker. Now go trough each permutation of that array. To process a permutation, you are going to only assign people before breaker to the correct table and you can ignore the rest. (ignore means to assign them to any table) How do you assign them? Consider each consecutive subarray [l,r] of equal elements such that a[l-1]!=a[l] and a[r+1]!=a[r]. (a is the permutation) You will add it's length (r-l+1) to the array b. Obviously, you are ignoring the elements after the breaker. Now that you have array b, you are going to assign each b[i] (apart from the last one) to exactly one table, such that the sum of capacities of tables that you assigned is minimal. That problem can be solved with greedy. Now, fill the remaining tables with the last element. If it is possible to do so, such assignment is valid. Now you just select the best of all valid arrangements and output it as a solution.

Why does greedy work? So, let's say that we have 2 arrays x and y who will describe any optimal arrangement of people. On table i, I will put x[i] people who like dish y[j]. Now, if we rearrange x and y in such a way that none y[i]=y[i+1] other than on some suffix of array y, we get a permutation. First x[1] elements are y[1], then x[2] elements are y[2] and so on. After that we can put the breaker and unused elements. Now, it is clear that all b[i] apart from the last one will be assigned to exactly 1 table. The optimal assignment of b[i] is so that capacity of unoccupied tables is maximized, so that last b[i] has enough tables to arrange the people from it.

Complexity of the solution is O((N+1)! * (N+M) * log (N+M)). Meaning that for N=10 and M=10, the solution would use around 4 Billion operations. Note that this is probably not the optimal solution and that it is likely that there exists a faster one.

Also, if you noticed any mistakes in my solution or proof, please let me know. Example:

15 4

1 1 1 1 1 1 1 1 2 2 2 2 2 2 2

5 4 4 2

One of the optimal permutations is:

2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 B

It will result in an array b like this: 5 4 2 4. We will assign 5 4 and 2 to the tables, leaving one table with capacity 4. We can assign the last element of array b (4) to it.

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

    Obviously you can do dp on subsets in $$$O(3^n m)$$$. Store the mask of people you didn't already sat somewhere, iterate over all tables, choose a mask of people to sit at this table. That's basically memoization of your bruteforce.

    But then we only care about the multiset of sizes of groups with the same taste, and the sum of these numbers is at most $$$n$$$. So we can write dp with memoization on reachable states, there will be at most $$$O(m \sum_{i=0}^{n} p(i))$$$ states where $$$p(x)$$$ is the [partition number](https://en.wikipedia.org/wiki/Partition_(number_theory)). This should work reasonably fast for $$$n \le 50$$$ or something.

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

Now we can say C >> A > B > D > E > F > G > H

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

Очень грустно, что на посты — объявления о нерейтинговых Дивах ставят много отрицательных голосов и авторы этих постов незаслуженно получают отрицательный вклад. MikeMirzayanov, пожалуйста, займитесь этой проблемой

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

Problem F says "Kira is not very strong in computer science, so he asks you to count the number of ways to invide friends."

It should say "invite" not "invide" I think.

»
22 месяца назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится
«Я был на третьем курсе ЛГУ. Зашел по делу к Мануйлову. А он как раз принимает экзамены. Сидят первокурсники. На доске указана тема: "Образ лишнего человека у Пушкина". Первокурсники строчат. Я беседую с Мануйловым. И вдруг он спрашивает: 
— Сколько необходимо времени, чтобы раскрыть эту тему? 
— Мне? 
— Вам. 
— Недели три. А что? 
— Так, говорит Мануйлов, — интересно получается. Вам трех недель достаточно. Мне трех лет не хватило бы. А эти дураки за три часа все напишут.» (Сергей Довлатов, «Записные книжки»)

Сколько времени нужно на решение этой задачи? Автору контеста двух недель достаточно, Um_nik двух лет не хватило бы, а эти фиолетовые за два часа всё напишут.

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

Ну просто биззарный дивизион!!!