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

Автор AndreyPavlov, история, 3 недели назад, По-русски

Привет, Codeforces!

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

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

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

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

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

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

        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.

      • »
        »
        »
        »
        2 недели назад, # ^ |
        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.

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

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

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

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

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

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

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

    You mean Bits-chef??

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

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

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

Tester is me

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

As a tester I can say that I am a tester

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

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

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

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

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

almost OrangeForces lol

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

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

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

I take my words back ;(
DISAPPOINTED

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

omg orange round

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

Hoping to solve till D in this round.

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

wish every contester good luck and happy rating++ !

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

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

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

I wish to all positive delta!!!

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

Masters' Round!

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

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

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

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

Update: Now the rating has been updated.

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

What should I do To become Specialist

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

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

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

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

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

Unrated?

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

Why will this round be unrated?

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

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

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

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

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

"Unranted"

what an absolute bruh moment

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

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

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

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

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

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

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

»
2 недели назад, # |
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!

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

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

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

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

    same question?!

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

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

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

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

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

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

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

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

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

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

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

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

    idk man, maybe pretests are well below the constraints.

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

    Perhaps with some input data greedy doesn't work

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

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

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

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

    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

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

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

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

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

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

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

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

the round is unranted, not unrated guys.

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

nothing here

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

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

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

how is problem C not solvable

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

    Truly an "Unranted" contest:(

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

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

Garam krke thanda kr diya -_- .

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

Baler contest setter.

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

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

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

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

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

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

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

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

    • »
      »
      »
      2 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Testcase
      Greedy Answer(Probably Yours Too)
      Something Better
      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 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

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

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

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

How is problem C unsolvable ?

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

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

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

      But, ideally, it should be 13.

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

Can anyone explain why Problem C can not be solved?

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

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

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

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

Unrated. Thank you so much.

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

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

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

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

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

Why unrated? Sad. I think constraints are ok

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

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

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

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

»
2 недели назад, # |
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.com/blog/entry/103170 https://codeforces.com/blog/entry/103108

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

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

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

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

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

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

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

Is it ranted?

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

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

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

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

What does "unranted" mean?Unrated?

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

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

How did so many people get AC in C?

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

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

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

How the C number problem is unsolvable when there are almost 3K+ accepted submissions? Please clarify it as problem C looks legit.

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

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

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

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

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

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

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

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

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

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

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

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

my rank would've increased this round :(

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

Всё же не рейтинговый =(

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

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

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

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

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

This is just sad.

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

My best performance so far.

Bye Bye +125. Top 500 performance.

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

muda muda muda muda muda muda muda muda

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

bye bye +100 (real)

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

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

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

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

    Easy hacking greedy passed the pretests.

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

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

    Speedcoding just does that to you

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

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

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

      B was guessable too

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

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

      • »
        »
        »
        »
        2 недели назад, # ^ |
        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.

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

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

    • »
      »
      »
      2 недели назад, # ^ |
      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)?

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

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

This contest was a disgrace to the Joestar Bloodline

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

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

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

    Seems that greedy solution of C is not correct

  • »
    »
    2 недели назад, # ^ |
    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

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

Great round and wcnm !

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

+114 ...and then its unrated

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

Testcase for problem c that dosnt work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5

»
2 недели назад, # |
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

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

don't do it unrated pls

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

Not Happy with the contest making today :(

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

This contest is a disgrace to the Joestar Bloodline!

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

What was the problem with C?

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

    • »
      »
      »
      2 недели назад, # ^ |
      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?

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

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

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

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

What the fuck?

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

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

  • »
    »
    2 недели назад, # ^ |
    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

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

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

        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.

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

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

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

atleast open it for everyone who miss the contest but came late to solve the problem : (

AndreyPavlov

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

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

»
2 недели назад, # |
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.

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

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

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

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

why this round is unrated??

»
2 недели назад, # |
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.