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

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

Доброго времени суток! Скоро состоится мероприятие под названием Codeforces Round #214 (Div. 2), автором которого являюсь я, Дмитрий Березин. Это мой второй раунд, и Сережа надеется, что последний :)

Личная жизнь — такое дело, в котором много счастья не бывает, поэтому вам снова нужно будет помочь Диме и Инне. И да, Сережа вовсе не выступает в роли негативного персонажа, скорее, в роли обстоятельств, с которыми вам придется порой бороться...

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, и Сереже Нагину (Sereja) за то, что любезно (покидает комнату) согласился помочь в тестировании.

Сережа передает привет, и настоятельно рекомендует прочитать условия ВСЕХ задач.

Разбалловку скажу, честно. А разбалловка 500-1000-1500-2000-2500.

Спасибо за внимание, хорошего раунда!

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

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

По просьбе человека, чье имя обещал не разглашать, за то, что он помог мне тестировать раунд, размещаю здесь небольшой пиар. (в правке)

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

    Хм, кто бы это мог быть... Думаю, сообществу никогда не раскрыть эту тайну.

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

    Сопоставляя ваши габариты, я с трудом верю в то, что это была просьба..

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

    Надо обещания выполнять:

    http://mirror.codeforces.com/blog/entry/9625#comment-151291

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

      Ох, так и вижу, что теперь полуголый Sereja будет появляться в комментариях каждого нового раунда на codeforces... :)

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

        Не стоит. Тут и так уже начинаются комментарии, что я несу "разврат в кодфорсес", думаю, пора остановится :)

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

          Как по мне в ваших задачах ничего такого нет.Легенды довольно забавные, и поэтому задачи приятно читать.

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

        С каждым раундом все меньше и меньше одежды!

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

Hope, there will be nice problem statements for English version ... :)

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

"и Сережа надеется, что последний"<--Сережа конкурентов убирает:)

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

Комнату не забудь убрать, качественно!

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

Study for exams or do CF round? Hmm. Screw exams. :D

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

This is my first round with "Java" and I hope not the last

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

    If it will help you, author solved his own tasks in java also :) I can recomend you to use "fastReader" you can find it in any code of any participant in java with high reiting. Have a nice round!

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

    Good choice, my friend :)

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

http://apps.topcoder.com/forums/?module=Thread&threadID=804294&start=0&mc=2

Can someone help me with above problem ? It is related to LRUcache. I use STL map and set but i get WA. Does anyone know of any test case where it fails ?

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

    If you ask for help, make a new blog post for it. Don't do it in the comment's section of something completely unrelated. This way, you won't get an answer, but just low contribution.

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

I was studying and hope to do well in this contest.

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

Своевременная разбалловка — это так прекрасно!

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

Ну и убожество в условиях.

Вот и зови школьников писать див2 раунды :(

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

    Ну вот я прочитал условия и не вижу ничего убожеского. Легенды забавные, но небольшие и не отвлекают, и вроде бы в каждой задаче понятно, что просят сделать.

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

    Пожалуйста, аргументируйте. Мы стараемся учитывать мнения участников по поводу условий. Что конкретно вам не нравится?

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

      Ну, теоретически в них есть подтекст, который 16+ или 18+. Наверное претензия именно в этом.

      Согласитесь, читать такое 12 летнему ребенку — не стоит.

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

        Ого. Даже не знаю, что и сказать. Укажите, пожалуйста, место в условии, которое может смутить ребенка. Если оно действительно есть, прошу прощения, ибо никаких подтекстов в мыслях не держал :)

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

          "Дима, Инна и Сережа собрались в комнате. Правильно, кое-кто лишний."

          Наверное, все же поторопился, насчет 18+ подтекста, видимо просто для взрослого все так "очевидно" или может опыт жизни в общежитии подсказывает :)

          UPD. В любом случае нельзя забывать, что то, что забавно для 20 летнего, может быть чересчур откровенным для 12 (а то и 10) летнего школьника

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

            А Вы любите проводить свидание с девушкой в присутствии соседа (пусть и очень хорошего) ?

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

              Я люблю не писать о своих отношениях везде, где могу. Тем более в условиях задач по олимпиадному программированию.

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

                То-есть если б автор контеста написал вместо своего имени — любое другое, всё было б нормально? =)

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

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

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

                  Если такой умный чего ты контесты не даешь?

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

                  ================================================================ Как по мне, автор достаточно серьёзно отнёсся к подготовке соревнования. Задачи интересные и в меру сложные. А легенда задаче так или иначе нужна. Или интереснее было бы, например, в первой задаче прочесть что-нибудь такое:
                  "Даны четыре четвёрки чисел a,b,c,d. Если среди них есть такая, для которой выполняется min(a, b) + min(c, d) < n + 1, выведите её номер, min(a, b) и n - min(a, b)"?

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

                  В таком случае это уже было бы не условие, а решение)

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

                  почему Сергей Соседов сам не поет? :)

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

              Естественно нет. Легенды забавны и приятны для чтения с этим не поспоришь.

              Но теперь представьте, вы бы хотели чтобы Ваш сын в 10 лет читал об этом? Повторюсь, я не юрист, и не моралист, но теоретически существует ситуация что чтение легенд может нанести будущим звездам спортивного программирования "психический, физический и нравственный ущерб"

              Пока смотрю вики, на предмет точных формулировок.

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

                Я думаю, что "испорченных" детей такими текстами не испортить, а чистые душой ничего такого в них и не заметят. Это обсуждение и занятая моралофагами радикальная позиция намного вреднее самих условий, имхо

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

                Вы правда считаете, что дети в 10 лет о чем-то не знают?

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

                  Интересно, много десятилетних детей решают раунды КФ?

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

                  Если человек в 10 лет уже в состоянии программировать, то он достаточно взросл, чтобы узнать всю правду о нелегких отношениях Димы и Инны)

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

                  А это что то меняет?

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

      В следующей раз почаще пишите что Инна и Дима любят друг друга, это очень важная информация. В каждом условии есть "Дима любит Инну", "Инна любит Диму", "Сережа "лишний"" и т.д. и т.п. Еще добавьте в следующий раз поцелуев в задачку, чтобы нам еще интереснее было. Можно еще интриги: "Инна ревнует Диму", "Дима пришел позже чем обычно". Ну и конечно побольше подробностей из их жизни вроде "Дима и кровать" и т.п.

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

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

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

          Сопли и разврат, это если бы было написано: "я ее любил, а она мне не дала".
          Знаешь, не каждому приятно читать что то вроде: "в Берляндии живет Ариктафен" или подобное. Всегда будут недовольствия, и без этого никак.
          А запрещать писать что то конкретное, у нас тут демократия как никак. Каждый имеет право на что то свое, возможно необычное. И свои недовольства большая просьба не навязывать. Хотел бы скинуть картинку по этому поводу, но боюсь это уже будет из категории "18+".

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

        Может Вам просто завидно что Вы прыщавый задрот, и у Вас нет девушки?

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

          О вкусах не спорят. Математическая формулировка задачи ясна (я надеюсь). Некоторые участники (клянусь, они не подкуплены!) считают, что мои легенды забавны и приятны для чтения, и даже не мешают решать задачи!

          Спасибо за критику, впрочем, не в той форме, в которой бы ее хотелось читать.

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

            Оооооо! Задачи интиресные, думаю тут не поспорят. И условие тоже, вроде, без всяких замыслов

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

        Действительно, куда интереснее "Диме подарили на день рождения массив".

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

          ахахах, да-да, даже помню была задачка, где ему подарили очередь, стек и дек =)

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

            Я тоже хочу на день рождение в подарок, красивый массив и очередь ^_^

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

      Мда, видимо, это было слишком резко, извините.

      С другой стороны, надеюсь, автору не очень обидно, раз уж он считает ежедневную ругань по любому поводу забавной, нормальной и подходящей для легенды.

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

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

        О Г-ди! Куда же катится моя жизнь! Прочел, так страшно стало :)

        Могу лишь посоветовать немного проще относится к жизни. Можно начать с условий моих задач :)

        Мне жаль, что условия не пришлись Вам по вкусу, но нравится всем, согласитесь, желание не очень.

        Извините еще раз, если затронул чего-то или кого обидел. Не хотел.

        А вот формулировки оскорбляющие прекрасную девушку, добродушную вахту и хорошего соседа, я считаю, неуместны. Особенно учитывая, что это реальные люди. Не стоит их обижать.

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

          Ну, не стоит — так и не обижайте. Можно подумать, это я тут вывешивала неприятные подробности ваших отношений с девушкой.

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

            подкупом жалких вахтерш

            девушкой, роль которой сводится к тому, чтобы пилить и стругать салатики;

            Читать не приятно, при том, что это не так. Ругаете за то, что условия слишком переплетены с реальностью, не подумав, что есть и часть вымысла, и сами строите транспонированный граф.

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

              Почему не подумав? Да пусть они хоть полностью вымышленные, эти условия — вымысел-то все равно неприятный.

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

                А в прошлом раунде от этого автора, Codeforces Round 208 (Div. 2) Sereja надавал Berezin пинков. Вот и ещё один затравленный персонаж появился — хилый Berezin, который не может за себя постоять =(

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

                Наталья, поверьте, то, что Дмитрий описал в своих задачах (с долей вымысла и гиперболы), не имеет ничего общего с настоящими проблемами жизни в некоторых общагах. Честно.

                Вот если бы был сделан контест по мотивам этих проблем — тогда бы реально ему нужно было бы ставить возрастной рейтинг наподобие 16+, а то и 18+. Там реально были бы вещи, от которых детей стоит ограждать.

                Так что попробуйте, пожалуйста, отнестись попроще к сегодняшним задачам. Вам же будет легче...

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

                  Да я верю, что можно было написать еще хуже, чего тут обсуждать.

                  Вы с автором оба так просите, чтобы я отнеслась к этим задачам попроще, что мне кажется, что это вам от этого станет легче, а не мне :)

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

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

                  Смотрите: Вы восприняли ситуацию в негативном ключе — в итоге испортили настроение по меньшей мере двум людям: себе и автору контеста.

                  А я просто пытаюсь склонить Вас к тому, что такой юмор на самом деле не настолько плохой, чтобы из-за него у кого-то портилось настроение.

                  Кстати, весьма вероятно, что девушка автора прочитала условия и от души над ними посмеялась :).

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

                  Спасибо за защиту :)

                  Настроение не испортилось, а, скорее, поднялось :)

                  Правда забавно было тут про разврат почитать.

                  Девушка, я вам больше скажу, помогала придумывать условия, за что ей большое спасибо :)

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

                  Ну, я немного по-другому на это смотрю: автор испортил настроение мне, я — ему, все честно. До итога дело еще не дошло — может, в итоге в следующий раз условия будут получше?

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

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

                  Рекомендую почитать следующий раунд :)

                  Я уже даже придумал условие на всю эту тему :)

                  Заключающий пост в ветке: 1) такое надо выяснять в личку, это неприятно читать многим. 2) не надо мне портить настроение :) 3) в сумме в ваших комментариях негатива для чтения гораздо больше, чем во всех моих 10-ти условиях (моё скромное личное мнение).

                  Спасибо за то, что посетили раунд. Хорошего дня!

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

      Выскажу свое мнение.

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

      1) "Каждая вахта состоит из двух вахтерш." — ну, казалось бы, вахтерши работают на вахте, а не вахта из них состоит :)

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

      3) "любой целой цены начиная от 1" — аналогично

      4) "Единственный способ потратить 10 рублей, ..., будет купить" — криво с точки зрения грамматики

      5) "Чтобы задобрить первую вахту нужно" — нет запятой.

      6) "вахта, которую мы модем задобрить — третья" — во-первых, опечатка, во-вторых, запятой нет.

      Возможно, есть и другие ошибки, которые я пропустил при беглом просмотре.

      Я понимаю, что есть масса людей, для которых подобные опечатки не важны, однако лично мне даже мелкие ошибки всегда бросаются в глаза. Именно поэтому я перед контестом всегда по много раз перечитываю свои условия, стараясь найти и исправить мельчайшие ошибки. Странно, что координатор раундов ничего не заметил в этот раз ;)

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

        Спасибо большое за Вашу критику. Читать ее действительно приятнее.

        Приношу свои извинения за подобные "ляпы", в свое оправдание могу лишь сказать, что объем работы большой, и не всегда сил хватает в сотый раз вычитывать условие, хочется отдать предпочтение составлению тестов и т.д.

        А по факту да, действительно, не должно быть такого, буду работать надо собой.

        Спасибо

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

      Мне в основном не нравится легенда в задаче B:

      Благодаря вам Дима чудесно провел выходные, но пришло время делать дела. Естественно, что Дима, как и все мужчины, у которых есть женщина, все делает не правильно.

      Инна и Дима сейчас вместе в одной комнате. Инна ругает Диму за каждое дело, которое он делает в ее присутствии. Поругав Диму за какое-то дело, Инна удаляется в другую комнату и там ходит по кругу, причитая, какой у нее непутевый суженый. За это время Дима спокойно успевает сделать k - 1 дело. Затем Инна возвращается и за следующее дело, сделанное в ее присутствии, вновь ругает Диму, после чего снова удаляется в другую комнату. Описанное продолжается до тех пор, пока Дима не сделает все свои дела.

      ...

      Не любая история подходит для легенды. Эта конкретная история мне кажется неподходящей для широкого круга читателей. Я считаю её некорректной.

      (Например, я ни разу не видел задачи, условие которой построено на сортирном юморе. Считаю, что она была бы примерно настолько же некорректна.)

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

        Не понимаю как можно сравнивать такие вещи. Если есть желание объяснить мне, можем поговорить в личке.

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

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

    Жду новых приключений:D

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

Надеюсь, будет разбор, а то уж ооочень интересные задачи :D

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

Как решалась D?

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

    Переберем минимальное значения они только можно быт lk значении. Для каждое значние находим такой путь, нижний предел не больше lk и минималное значение верхних пределов будет максимално. Этого можно делат с Алгоритмом дейкстры с кучам. Если это значение d[n], тогда лояльность равно (d[n]-lk+1). Обновим ответ этим значением.

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

Как решать С?

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

    Крутая задача, очень понравилась.

    sum(a) / sum(b) = k

    sum(a) = k * sum(b)

    Домножим все b-шки на k, тогда нужно набрать так, чтобы sum(a) = sum(b).

    Как это делать: Преобразуем каждый предмет из пары (a,b) в одно число (a-b), наберем подмножество с нулевым таким весом и максимальной стоимости.

    Итого: O(n*k*max_cost)

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

      Но как найти такой подмножество?

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

        Рюкзак же.

        Вес: (А — Б), стоимость: (А), запускаем самый обыкновенный рюкзак (с отрицательными весами), максимизирующий стоимость, и выводим ответ для нулевого веса.

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

        Рюкзак с линией памяти.

        Тут лучше код посмотреть, так понятнее будет: http://pastie.org/8505500

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

      А как объяснить то, что такой рюкзак с линией памяти, в этой задаче работает? Почему не происходит занесение в массив несуществующих значений?

      Гораздо более понятна реализация с dp[n][max_cost].

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

    Присоединяюсь.

    Всё, до чего смог додуматься — все калорийности домножить на k..

    Вместо них в принципе можно хранить разности вкусности и калорийности. Тогда требование будет выполняться при таком наборе ингредиентов, у которого сумма таких разностей будет равняться нулю. Вопрос остался только в том, как найти такую сумму с максимальной суммарной вкусностью за 3 цикла..

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

The terrible English problem statements ....

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

What is the approach for C? I tried subset sum type memoization with a variation but got wa on 6th pretest ....

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

    me too, i got TLE on 6th pretest

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

    It is subset sum, or knapsack. For each fruit i, assign an object with volume a[i] — kb[i] and value a[i], and the answer is the set with maximum value and zero volume.

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

      why does the solution considering the subset with max(total taste/ total calories) won't work ? it gives wrong answer on pretest 6

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

        The problem is get k = (total taste/total calories) where total taste is as big as possible.

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

Задачи интересные. Условия забавные. Автор молодец. А я дурачок =_=

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

    Поздравляю!
    не один ты "дурачок". Из-за невнимательности у меня не пошли ни А, ни В. стоило только изменить в А один символ, а в В -- добавить один символ --> все пошло

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

      Бывает.

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

      С чем поздравляешь-то?) Я в А тоже опечатался. Про остальные свои косяки уже товарищам нанылся :)

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

        Я сначала закодил решение для трех вахт. Я даже не читал значения для четвертой вахты, ибо думал, что их всего 3. Хорошо(да-да, именно хорошо, потому что я успел исправить решение), что взломали решение.

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

Можно ли было в Е заранее подсчитать 8 координат для каждой ноты (самая верхняя-левая, самая верхняя-правая, итд) и далее просто пройтись по массиву q, попутно релаксируя ответ?

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

C. dima and salad:-

i had a n! solution in mind..

lol

where can i get its solution/editorial

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

А почему условии второй задачи вывод при втором наборе входных данных 3 4 6, а не 3 4 4?

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

    Нужно потратить ровно N рублей. Во втором примере N = 10, поэтому потратить 8 рублей недопустимо, так что можно купить одной из вахтерш более дорогой подарок.

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

    Потому что сумма должна равняться 10.

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

I'm unable to tell in words about problem description !!!! :/

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

solution or ediorial ?

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

I just want to know... if an user registers 3 hours before the contest for Div2, and then gets the first place... Isn't quite obvious that he is an Div1 user...?

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

The statement was as terrible and lengthy as last Round Codeforces Round 208 (Div. 2). So time-consuming to read them...

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

The statements was very funny =), Problem D was my favorite (although I got WA), I get confused with a simple dijkstra but when I realized about that it need to be careful with segments, the contest was finishing.

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

Although some people are complaining about the English, I had no problems with the statements (some were lengthy indeed, but hey, that's part of a contest :P).

For me, the problem selection was very nice (although I was not able to perform well :P). Some dp and graph problems with some easier ad hocs, that's more ICPC style than many other rounds (and for me, who wants to practice for next year's ICPC, it was good :)

Nice job!

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

can any one explain what "Denial of judgement" is ? it got one on 'C' problem today .

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

can any body explain what "Denial of judgement" is ?

i got one on problem 'C' this round .

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

Anyone got WA on test 9 at problem D? I don't know what this test case has in particular

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

    it has something to do with multiple edges between the same pair of vertices

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

      Can you give an example, please?

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

        or

        2 2
        1 2 1 3
        1 2 1 2
        

        The answer is 3 for both tests, but your solution might fail on one of them

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

          My solution works for both :S

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

            Well, my first attempt failed on 9th test and fails on one of these. After I made it work on these tests, got AC. Sorry I wasn't able to help you :)

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

          Thanks, but it passed both the tests.

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

Почему такой ответ в задаче А не верный 100000

25000 50000 75001 50001

25000 50000 75001 50001

25000 50000 75001 50001

25000 50000 75001 50001

Мой ответ 1 75000 25000

Верный ответ 1 25000 75000

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

    потому что для второй вахтерши за 25000 ничего путного не купишь...

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

    Вы заплатили за подарок второй вахтерше меньше, чем ей нужно хотя бы на один из подарков.

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

    Вы покупаете подарок для второй вахтерши за 25000, тогда как подарок для второй вахтерши должен стоить как минимум 50001.

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

    Не существует второго вахтёра, который бы был доволен подарком за 25000.

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

servers seem to be responding well to the loads now . There was much less glitches than previous times .

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

Спасибо за интересные задачи.

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

Good Problems :D

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

На самом деле вы оскорбили Кобейна

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

I am wondering why the time limit of E is 3s ? Please see the solution http://mirror.codeforces.com/contest/366/submission/5228621

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

Замечательные задачки, с удовольствием порешала что смогла, остальное буду дорешивать позже. Похоже, третью можно решить с помощью дерева Фенвика, четвёртая — образцово-показательное дин.программирование, по пятой пока не понятно (кроме как злобным перебором). Желаю счастья в личной жизни Диме и Инне, а Серёже — терпения и удачи! :)

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

Rating?

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

Я думал,что я один опечатался в A.У этой задачи какае-то карма волшебная:)

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

In the first page of the rank list there is only 6 regular blue coders in top 20. Rest 14 contestants are new participant(holding top 5 in today's rank list). I was wondering what is the secret behind it??? If after a codeforces round, the change of rating depends on the position in the rank list then it is a very annoying and heartbreaking for div-2 coders if div-1 coders participate with a new handle in each div2-only contest. I have one more question. Will my handle be banned if my contribution underflows 32 bit signed integer for any of my post???

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

Why is rating updation so slow? zzzzzz

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

I just miss the clarification about problem C and can't solve it in contest time. Bad luck for me. :(

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

rating:1696 TvT

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

missed the contest, coz of semester exams ... diverse set of questions # :)

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

В задаче "С" надо выбрать отрезок???

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

It is hard to understand Pro D. Can anybody tell me what's the result about these tests: test1: 4 4 1 2 4 8 1 3 1 3 2 3 4 8 3 4 4 8

test2: 4 4 1 2 4 8 1 3 1 4 2 3 4 8 3 4 4 8

5 and 1?

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

can anyone please give link to a similar problem or tutorial to problem C : Dima and Salad

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

    You can first try simple subset sum problem and knapsack problem and then try to relate this problem with those two concepts .

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

    It is a tricky variant of classical subset sum problem(at least i felt so). The observation I made during the contest was something like this:

    we have three conditions : 1.a/b should be exactly K; 2.We have to maximize a; 3.we have to pick at least one;

    condition one: a/b= k => a=b*k =>a-bk = 0 since k is only 10 a,b<=100 , a-bk should fit in 2*10^4 , I kept abs(a-bk) and a flag(say signflag) that distinguishes state a<=bk or a>b in previous choices.

    then from each position we have two choices, whether we select the current one or not.

    I also kept another flag(say takenflag) to keep track of whether i have taken at least one salad or not. When i have decided to take some ai,bi, I have updated my current difference according to the status of my signflag that tells me whether in previous choices a<=bk or a>bk.and then updating the takenflag into 1. Therefore, Our next call would be a[pos]+rec(pos+1,newdiff,newsignflag,1); see taken flag is 1, we have choose at least one.

    And if we don't choose current position, our another possible option is: rec(pos+1,olddiff,oldsignflag,takenflag); just an increment in position keeping other values unchanged.

    now we must have to take maximum between these two options: therefore we return dp[pos][olddiff][oldsignflag][takenflag]=max(a[pos]+rec(pos+1,newdiff,newsignflag,1),rec(pos+1,olddiff,oldsignflag,takenflag)); why do we keep max??? because we have to maximize a in a/b=k;

    base case:

    if(pos==N) we have no choices left, its time to decide by observing what happened in past. Form the states we can say what happened in past. If oldiff==0 then we can say the way we came to pos==N maintains a-bk=0 => a=bk => a/b=k. Also we have to check the takenflag whether we took any salad or not. SO, if(pos==N and olddiff==0 and takenflag==1)return 0; else return -inf;//inf=any large integer

    Now we are sure that if there is such path to choose from the given sets such that a/b=k, we shall definitely reach at if(pos==N and olddiff==0 and takenflag==1)return 0; and get a positive answer. Otherwise, whenever we have no option to choose we are returning -inf which is a very large negative number. That means our maximization process returns a negative number when there is no way to satisfy a/b=k for given set.

    It was a very naive formulation by me. But there are plenty of excellent source codes that will reduce the state and your coding complexity but the idea is almost same. For example if you start from a very large number and in the base case you reach at that same number then you can say that there is a way, because you are actually shifting all integers by a large value(20000 should be enough) and thus you don't need the signflag.

    Sorry for poor English.

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

can't appreciate language used in problem description, had to go through test cases first and then tried to understand.. btw where can i find editorials?

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

won't there be any discussion post on the problems of this round?? i'm trying to find out in which pattern i should save the results in problem C Div 2