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

Автор Serega, 13 лет назад, По-русски

Всем привет!

Добро пожаловать на Codeforces Beta Round #90! Сегодняшний контест для вас подготовили студенты Саратовского государственного университета - я, Сергей Сухов, и Александр Игнатьев (aiMR). Благодарим Артема Рахова (RAD) за помощь и ценные советы, Марию Белову (Delinur) за перевод условий и Михаила Мирзаянова (MikeMirzayanov) за возможность провести этот раунд.

Удачи и высокого рейтинга!

UPD: К сожалению, в авторском решении задачи B была обнаружена ошибка. В связи с этим данный раунд будет нерейтинговым. Приносим свои извинения.

UPD2: Опубликован разбор задач A-D.

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

13 лет назад, # |
  Проголосовать: нравится -54 Проголосовать: не нравится
Good luck & Have fun :)
  • 13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится -32 Проголосовать: не нравится
    Edit : Ignore
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +43 Проголосовать: не нравится

      I always downvote GL&HF messages. I hate them.

      They don't provide any info, I need to scrool it to check, is it any useful meesages about topic(i.e. next contest now) here.
      As for me, they are OK for chat, but not for forum or blog comment
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -39 Проголосовать: не нравится

        Is wishing good luck bad at all??? Before any contest, any one can wish other good luck, this is like a love to all, or can be formality. But, why is this seems as down voted comment??? If anyone finds only useful info, then they only should search for that, not giving down vote to any comment which never seems like nonsense comment. Coz, every vote counts as contribution in Codeforces. So, we all should be careful of this.


        One thing, please look at this Blog, writer written in the last "Good luck and high rating!". So, what will you say? Is it down voted blog????

        • 13 лет назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится
          It contains "Good luck and high rating!" among other things. It isn't about the color, but for me saying "Good luck and have fun" sometimes looks like begging for contribution.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

            But, may be this is not like what you are thinking, Actually I never think of this. Always saying Good luck before any contest to all the contestastent (online or onsite). As Topcoder gives us chance to chat, we can say Good luck to everyone by a General post, In codeforces, it give chance by comments. So, I don't think that saying Good luck is like begging for contribution. If so, then I will never say good luck. Coz, I don't like this types of thought like begging for upvoting.

        • 13 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится
          The difference is that ErzhanDS wrote only "GL & HF" but the topic consists of some information about who is the problemsetter.
          I consider "GL & HF" messages annoying, that is the reason why I have downvoted it.
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
This round for div1 or div2 ?
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Because this contest for both of Division, so please make the problem for both Division (Not for Div 1 only) :-)
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Соревнования будут рейтинговыми или нет?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Иногда есть нерейтинговые.
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
возможно не в тему: но на главной ники в топике отображаются как теги!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Highest number of registrants this time ( 2000+ ) :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    wow it's 2010 registrants. it should be one more registrant and it would be cool :p
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      I said to a friend of this round, and he remembered the need of registration just a few seconds after registration was closed... He should have been the 2011-th :(
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Одного не хватило.. зарегалось 2010 человек
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Но участники контеста кто? Автор и 2010 человек = 2011 :D
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      "Сегодняшний контест для вас подготовили студенты Саратовского государственного университета...."
      Так что 2013 ;D
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Блин, почему я не зарегался:((
13 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится
По любому нужно менять систему входа на сайт. Последней каплей стало то, что я зарегистрировался на раунд, но как оказалось мне лишь показалось. Видимо меня опять перекинуло на страницу логина а я и не заметил, я ведь логинился.  Меня уже в край достало то, что логиниться нужно постоянно. Галка "запомнить на месяц" нифига не работает. на codeforces.ru и codeforces.com нужно отдельно логиниться. Я зарегался, три часа джал раунда, надеялся поконтестить вечером, и тут раз - ОБЛОМИСЬ! Офигенная ситуация. Я сейчас полон ненависти, и излучаю добро во все стороны. Пожалуйста, приведите систему впорядок, достало уже.
13 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
Почему распространяемые сообщения не появляются в "Вопросах по задачам"? А если кто-то случайно закрыл окошко и не успел прочитать?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Согласен.
    Тоже случайно закрыл окно... а перечитать сообщение не могу.

    Было бы неплохо их где-нибудь сохранять.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
unrated round, isn't it?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

Ну всё, раз нерейтинговый, тогда не буду дальше решать :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    CF нужен только для рейтинга?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Не то, чтобы только для рейтинга.
      Просто обидно, что из-за такого косяка авторов сливаются все.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Ну да. С этим не поспоришь.
        Но С я все-таки допишу =)
        Как-то тупо, что авторские решения проверяются посреди раунда, а не до него. А раунд так хорошо шел...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

    Закон подлости - я сейчас на полуфинале в Виннице, и не пошел на ужин и презентацию Коркуны (из Фейсбука) только ради того, чтобы написать рейтинговый матч и вернуться в более подходящий мне цвет (или закрепиться в красном).

    Сразу почувствовал, какой я голодный)

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

Нерейтинговый раунд?

Пацаны, расходимся.

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

    Люди столько сил, времени потратили на составление задач...

    А вас только рейтинг интерисует...

    Большое спасибо организатором контеста!

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

Нельзя было перед контестом пристально проверить все тесты на правильность?

Плохой контест((((

  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    У каждого бывают свои ошибки. Я думаю, что перед каждым контестом  авторы тщательно проверяют условия и решения. Но не будет забывать, что это beta round, и все мы обязались не расстраиваться сильно, если что-то пойдет не так. Так что простим авторам такую ошибку. Кстати раз уже он будет нерейтинговым, можно этот хитрый тест в студию?
13 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится
Спасибо за кучу хороших эмоций, уважаемые авторы раунда !!!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится
    Перечитайте соглашение, с которым вы соглашались, регистрируясь на раунд.
    Вы обязались не расстраиваться, если что-то пойдет не так =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      в соглашение скоро придется добавлять, что то вроде: "не гнать на авторов, если что то пойдет не так"
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Интересно что за "хитрый тест"?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Последний в наборе, скорее всего, - увидишь после контеста :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      это 9 тест моё решение на нём упало(
      • 13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Интересно что за тест там такой.... тоже на 9 запоролся ... Не думал, что за попытки снимают баллы (думал их снимают с задачи, если уж умудришься её решить)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          за попытки не снимают баллы. Вы правильно думали
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Я один, кому сейчас больше всего интересно, пройдет ли его решение вот этот хитрый претест по В? Только мне ресабмитить влом)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    по моему послать решение это не сложно =)

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Во мне 2 чувства борются - не трогать и продолжать дебаг С (ну и посмотреть после раунда на свое "честное" место), или же забить и на С, и на конец раунда)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я сделал ресабмит и нашёл ошибку. Случай добавлен действительно интересный=)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мое бы не прошло. 

    Хорошо, что контест нерейтинговый.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    У меня в комнате должно было упасть примерно 30 решений=) такой хак-эвент не удался=(
13 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится
Все равно раунд нерейтинговый, давайте хоть решения обсудим :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я думаю, в любом случае это лучше делать после окончания раунда.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть ли вероятность того, что они все таки сделают его рейтинговым?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет. Хотя бы потому, что половина кинула писать контест
  • 13 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится
    По всей видимости, нет. Как автор задачи, я приношу свои извинения за происшедшее.
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Мой первый codeforces по закону подлости оказался нерейтинговый(((
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
точно?
13 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
Парень одним местом чуял http://mirror.codeforces.com/blog/entry/2856#comment-57951
13 лет назад, # |
Rev. 5   Проголосовать: нравится +24 Проголосовать: не нравится

Эх, пришел после большого перерыва, придумал хак, который роняет всю комнату и... уронил решение жюри=(

UPD. http://mirror.codeforces.com/contest/119/room/11 - пруфлинк на тему всей комнаты
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скажи, пожалуйста, тест, когда раунд закончится
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Уже можно говорить.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      3 2
      1 2 3
      2
      Должен быть ответ 1 2, т.к. мы точно знаем, что среди двух имеющихся билетов третий вопрос не встречается
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        И в чем фича?

        Как я понимаю в том, что осталось больше, чем на билет?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Обновил коммент. Забавно, что претесты можно было пройти и с ответом 1 2, и с ответом 1 3
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Если проблема в том, что я написал, то по-моему это достаточно очевидный кейс.

            Ну то, что пройти можно было - это понятно. Об этом авторы не подумали => подобных тестов не было
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Нет, см. коммент на который ответил
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну, ты первый человек, у которого я увидел верный ответ на этот кейс. Хотя прочитал решение по B почти  у всей комнаты, видимо он не особо очевидный
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          нет, осталось - то ровно на билет (1 вопрос, как и в прочих билетах), но билетов-то всего 2 должно быть
          • 13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Ну я имел ввиду "хотя бы на билет". То есть можно сформировать билет, но мы видели все билеты. Мне кажется странным, что НАСТОЛЬКО много народу пофейлило это. Вроде бы достаточно очевидная вещь, даже не подумал залочить и смотреть это:)

            Точнее может и не очевидная, но куда логичнее проверить, все ли билеты мы увидели, чем то, сколько задач осталось. 
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Билетов 2, все они уже известны. в одном теорема 1, в другом   теорема  2. Третьей теоремы вобще не может появится, хоть билет и рассчитан на 1 теорему, и есть теорема, не прявязанная к билету.

              Тест что надо.

              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Не понял, что Вы мне хотели сказать.
                В чем прикол теста я понимаю, я его прошел, к слову.
                Я наоборот удивился, что столько людей на этом упало
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Отличный тест :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        1 3?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      8 3
      2 2 2 2 2 2 1 1
      3
      1 2
      3 4
      5 6
      Правильный ответ - 2.0 2.0
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        вот е мое... я еще подумал это предусмотреть, а потом подумал, да и без этого условия все хорошо будет((( идиот
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
what's the trick in problem B?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится
    Trick is we can already saw all k cards, but there are enough theorems to form one more card of the same size. Say n = 13 and k = 5
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I didn't understand your description, can you say an exact case?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        13 5
        1 2 3 4 5 6 7 8 9 10 11 12 13
        5
        1 2
        3 4
        5 6
        7 8
        9 10

        edit: some solutions will try to grab 12 and 13
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        8 3 
        12 2 33 3 33 3 3 3 
        1 2 
        3 4 
        5 6 

        ans is 7 18
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        8 3
        1 2 3 4 5 6 7 8
        3
        3 4
        5 6
        7 8
        Correct answer is 3.5 7.5, not 1.5 7.5
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          How is it? theorem 3-8 are seen,only 1 and 2 left. a card with 1st and 2nd theorem will average 1.5 .

          Am i wrong?
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            But we already saw all 3 cards
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              i just got it accepted. I have added an extra check,how many distinct cards i've seen so far.  Thanks everyone for helping.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            But it can only be divide to 3 cards. So 1st and 2nd theorem  can't form another card.

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            But there are only 3 cards (k=3) and all of them have been already used: 3-4,5-6,7-8. So there are no other cards on the table.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Помогите, пожалуйста,  найти ошибку в С. Не проходит 3 претест
Вот код :  http://pastebin.com/RMpwbrsw
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
даааа.... в этом раунде взломы делали все... 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I want to know what is wrong with problem B.
is problem B's description wrong or the author's solution wrong?
13 лет назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

Can anyone please help me as to why this solution of mine  to problem B is getting runtime error(on case 5).I have worked on it but not finding the reason.
This code is in JAVA.Here is the link.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    You use nonexistent elements of array "c". The size of array "c" is "t", but "i" is running from 0 to "card".

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think there should be more questions (maybe 7) in dual rounds, so there can be more easy ones for the low rateds.
The easy tasks could be assigned very few points, so the top rateds could just skip over.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "The easy tasks could be assigned very few points, so the top rateds could just skip over."

    But they wouldn't skip over them, because nobody is going to miss out on easy points, regardless of whether they are high rated or not.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Well if they would get more pts/min by going for the harder tasks, maybe they would :)
      Otherwise the joined competitions could be 2½ hours...
      But of course if more tasks would result in fewer competitions, that wouldn't be good.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    If you have such 7 problems already prepared, you can then simply run separated contests as usually...
13 лет назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

ппц. где можно было набажить в С? О_о

UPD у меня WA16. правильно ли я понимаю, что в том тесте у всех, кроме одного, границы от 10^16-100 до 10^16 ? такой тест у меня прога проходит

UPD2 а, нет, если поменять 2 сложности местами, то не проходит. буду разбираться

UPD3 мда... когда нумерация с единицы, надо и сортить соответствующий отрезок

  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    nevermind
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ето как такие числа получиться могли?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Никак, т.к. верхняя граница максимальная 10^16. То есть больше 10^18 никак не получится.

        Ну то есть от реализации зависит, конечно, но сделать так, чтобы нигде не вылезало за лонги -- элементарно.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Упс, наврал.
13 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
sorry, duplicate
13 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
sorry, duplicate
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Ничего себе, я второй. Как обидно, что нерейтинговый. С другой стороны, B прошла случайно: у меня правильная проверка лишь потому что так первым в голову пришло.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, в C сначала посортить забыл, потом перебирал не до b[j], а до a[j]+100, потом, оказывается, там сложности строго возрастать должны - 3x missread combo!
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Спасибо за отличные задачи, мне очень понравились!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Я рад это слышать ) Хотя, конечно, я согласен, что признание раунда нерейтинговым - весьма неприятный инцидент.
    Я и сам как-то участвовал в раунде, который был признан нерейтинговым, и это вызвало далеко не самые приятные эмоции. Расстраивает меня и резкое падение числа сабмитов по задачам к концу раунда. Всё-таки цель контеста - научиться решать задачи, а не повысить свой рейтинг. Задача D была довольно лёгкой, и её могло бы решить куда большее количество участников.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      нужно было сообщить о "нерейтинговости" после окончания раунда =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится
      Чтобы учиться решать задачи контесты не нужны
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Окей, контесты нужны чтобы учиться быстро решать задачи в напряженной ситуации.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Тут обсуждается почему бросили решать - ситуация уже стала не напряженной
13 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

i think its not right that contest is unrated , we can just ignore problem B and count points with 4 problems, for someone who wrote contest well is not fair not to update his rank , in all case authors are guilty not coders

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

    Imagine someone who spent his time on solving B correctly and then got his solution ignored. Someone else could skip B or have an incorrect solution, and that gives him an unfair advantage...

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

      i have 1528 rating, when i wrote 4th problem i was at 16 place, and i was happy and i thought my rank would be increased then authors wrote that round was unrated, is it my falt ?but at last my code had time limit at 28th test :( 

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

I think it's funny how the tricky case in B is so easy to miss that even the authors of the problem themselves missed it ;)

13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
В задаче B авторы контеста допустили ту же ошибку, что и 95% участников?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
В общем нормальный раунд, спасибо авторам. Отдельное - за суперзаковыристую задачу B.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In problem B, can anybody tell any efficient way to count distinct number of cards that Vasya has seen.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    set<vector<int> > myset;
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I've put all the used questions' numbers in a set and then when looking at the new card, I checked if that set already contains a question from it. If it does, we have already seen that card.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    bool used[n]; //used[i] true if we saw i-th theorem
  • 13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    If we count how many different theorems(not cards but single theorems) has Vasya seen then we can check that this number is lesser then (k*n/k) and this will do the job.

    To calculate number of different theorems you can use a set, or an array as RiaD-WaW said.

    The number of differrent cards is the number of different theorems divided by the number of theorems in a card.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Since two equals cards will be given as two (possibly) different permutation of the same set, and there won't be any theorem in two or more different cards, one could just pick any theorem i from a card (say, the smallest one) and set used[i] to true (where used is a bool array). The number of true elements in used will be also the number of different cards given.
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Вот как НЕ нужно писать КМП:

  1. FOR (i,1,z.size())
  2.         {
  3.                 int j = P[i-1];
  4.                 if (j > 0 && z[j] != z[i])
  5.                         j = P[j-1];
  6.                 if (z[j] == z[i])
  7.                         j++;
  8.                 P[i] = j;
  9.         }

=)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    только я не воткнул?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Там первый должен быть не if, а while. Иначе получаем странное для КМП время работы - линия без амортизаций.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        блин, точно, не заметил сам))

        уже чуть не подумал, что сам неправильно его пишу :о)

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

      Там вместо if (j > 0 && z[j] != z[i])

      нужно while (j > 0 && z[j] != z[i])

13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Now i get, why all this rounds are beta.
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
In test case 9 of problem B:
3 2
1 2 3
2
1
2
Answer is 1.00000000 2.000000000
Is that correct??? I think it should be 1.00000000 3.00000000.Please tell me if I am wrong??
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
не пойму только, зачем было делать анрейт и добавлять этот случай в претесты по В. 
ну сломались бы потом люди в финальных тестах. кого-то бы поломали, кто-то наломал бы. 
по-моему, вообще не нужно было делать клар о том, что авторское решение исправляется. можно было все сделать так, как будто этот случай не вошел в претесты намеренно - чтоб было больше взломов. а так какой-то бред получился
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ну, как я понимаю, там последовательность действий такая была:


    Чуваки начали сабмитить, кто-то залочил, придумал этот хитрый тест и побежал всех ломать.
    Система ему сообщает неправильный ответ на его тест, он пишет сообщение, авторы проверяют решение, а в это время уже чуваки во всю пытаются похожими тестами ломать и получают свои -25.
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      ок, тогда понятно, зачем вся эта шумиха поднялась с этой задачей. какую-то информацию надо было дать участникам, а анрейт в такой ситуации, наверно, на усмотрение авторов/(UPD)администрации ресурса

      UPD сам редко ломаю, так что как-то забыл о их нюансах ))

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

    Тут проблема, думаю, была и в том, что это нашли по клару adavydow. Т.е. был неуспешный взлом из-за неверного авторского решения. Это меняет ход контеста. Например, участник теряет время. Нехорошо.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну проблема видимо в том, что это все равно меняет ход контеста(взломы)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Помогите оптимизировать задачу D. TL на 8-м тесте
вот код: http://mirror.codeforces.com/contest/119/my
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Авторское решение работает за линейное время. Оно основано на использовании префикс- и z-функций. Скоро будет опубликован разбор.

    Ссылка, которую Вы дали, неработоспособна, ссылки на решения нужно вставлять по-другому.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Исправил ссылку
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Ошибка времени выполнения на претесте 8 - это не значит, что Ваша программа работает слишком долго. Ошибка времени исполнения может быть спровоцирована, например, выходом за границы строки или массива. В любом случае, очень больших тестов среди претестов нет.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Теперь TL все же.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Как я уже сказал, в этой задаче предполагается написание линейного решения. Ваш код явно этому критерию не соответствует. Претест 8 - это далеко не самый большой тест, который возможен в этой задаче.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Зашло N log N на яве в дорешивании. (Во время соревнования там тупой баг с RE был)
              Кроме z-функции использовал ещё и RMQ. Как понял, в авторском есть какая-то линейная амортизация.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Вот не пойму, зачем писать решения, которые точно дают TLE?

            Мало того, что там 2 вложенных цикла - там еще и массивы на 800 мегабайт, конкатенация строк по полмиллиона символов и еще StringBuilder.reverse() внутри этих for-ов - отличная комбинация!

            Неужели не очевидно, что на строчках длины 1000000 это будет годами выполняться?

            А еще оно и вовсе неправильное...

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Да вообще зачем писать неправильные решения
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Verdict: RUNTIME_ERROR
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Задачи интересные, спасибо. Но ошибка в условии немного подпортила общее впечатление...
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задачи очень интересные и красивые,лично по мне на ошибках стоит учиться,и народ переживет еще недельку без изменения рейтинга.Напротив по мне,это заманчиво когда находятся такие проблемки)
Все люди,все ошибаемся, но так или иначе спасибо большое) 
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
While there's an editorial yet, someone has some hint for problem D?