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

Автор Ripatti, 14 лет назад, По-русски
Привет всем!

Автором задач сегодняшнего раунда буду я. Это мой третий контест на Codeforces и первый контест для первого дивизиона.

Я благодарю Артема Рахова, Марию Белову, Павла Кузнецова и Михаила Мирзаянова за помощь в подготовке раунда.

Веселых взломов!

Победитель - tourist.
Разбор задач.
  • Проголосовать: нравится
  • +183
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +118 Проголосовать: не нравится
У меня есть конкретное предложение. Давайте перестанем писать "Я благодарю...". Конечно, нам приятно читать эти слова, и мы не меньше вашего (больше!) благодарны пользователям, которые проводят раунды. Это очень здорово, что в нашем сообществе есть такие люди.

Но с точки зрения информации, лично мне было бы интересней узнать где вы учитесь. Чем увлекаетесь? Может музыкой? Может был в вашей жизни спорт? Просто поместите ваше забавное фото, и для меня из абстрактного хэндла Ripatti вы превратитесь в человека с лицом :)
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Всем удачи сегодня на контесте!
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Можно попросить в пост добавить номера предыдущих контестов? =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Это можно узнать в истории его блога.
  • 14 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится
    Сделаю ставку на то, что в задаче E будет (аккуратная) реализация + форматированный инпут %).
14 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
Мне очень нравились тематические турниры, на мой взгляд, было-бы не плохо подбирать к задачам определенную тематику.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится
    По мне так пусть лучше ничего не меняет. Оба его раунда мне очень понравились. Интересно, что он приготовил на раунд для первого дивизиона.
14 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
Вот это да....... 1111 зарегестрировавшихся.... :) круто =)))!!!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хоть что-то должно было "пойти не так"... Обломали всех тех, кто копипастит пример вывода из условия ( хех:) хорошо, что я копипастил с примеров:) )
14 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится
время от времени "он отравляет свою секретаршу" - директор то с юмором. 
14 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится
Nice problems really. Thanks a thousand times :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что не говорите, а решать задачи типа сегодняшней С - одно удовольствие. Хоть сама идея задачи малость боянистая, но все равно:)

Такое намного приятней, чем сначала кодить пачку скучных алгоритмов (геометрия, допустим), потом это долго дебажить, потом еще впихивать в ограничения точности или ТЛ... Хотя и такое тоже полезно делать, и это тоже требует навыков, но... 

Подумать головой и припомнить матчасть - мне лично приятней. 

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А в С действительно нужен был 64битный тип?!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как решать С?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Я построил граф из всех диагоналей и соединил смежные. Потом решил посчитать количество компонент связности.
      Это правильно?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Как доказать, что ответ gcd(n-1,m-1)+1? Я доказал и использовал только более слабое утверждение и решал обходом в глубину. А именно: в хотя бы одной оптимальной расстановке все стоят у одной стены. Можно для каждой клетки у стены узнать, в какую клетку этой же стены мы придем, если пройдемся до противоположной стены и обратно (начав в одном из двух направлений, одного в углу). Так клетки у стены разбиваются на компоненты связности, их количество - ответ.
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Ой, а в B, оказывается, заяц может никуда не двигаться! Вот это провал
14 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Отдельное спасибо за задачу Е. Давно ничего такого не попадалось

Скорее бы дорешка :о)

14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Не смог соответствовать условию первой задачи, всего 1 челлендж :(
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Более идиотской баги, чем неумение создавать дерево интервалов нулевого размера я придумать не мог :(
14 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится
Ух ты!!! Вопросики вместо устрашающего НЕ ПРОЙДЕНО. Спасибо администрации - )
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Похоже маленький баг (скорее недочёт): при систестах во вкладке задачи, заблокированные и не тестированные ещё решения отображаються красным.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Дабл пост.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
1111 users have registered to this contest. We like binary, don't we? :)

By the way, nice problems in this round. I will be waiting for the editorial :)
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Спасибо админам за новый дизайн сис.тестирования.

Теперь намного удобней и понятней.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хочу сказать огромное спасибо за хорошие претесты. 
Особенно претест #3 по задаче B. Ну уж куча решений свалилась на нем :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    ИМХО претесты как раз были уж больно полными, ибо ситуация по взломам совсем невесёлая... Но в любом случае это лучше чем слишком слабые тесты. Автору спасибо за интересные задачи и почти идеальное проведение контеста - )
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
А кто знает, в С++ можно как-нибудь нахаляву посчитать количество элементов контейнера, со значениями в некотором диапазоне? Т.е. кол-во x: i<=x<=j. Это я к задаче D если что.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Count_if вроде может Не заметил слово "нахаляву". Он за O(N) работает
  • 14 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится
    Быстрее чем за их количество нельзя. В деревьях в реализации STL обычно не хранятся размеры поддеревьев, а без них вроде никак. Тем не менее наверно есть всяческие ухищрения, позволяющие решить эту задачу без своих структур данных (я долго не думал и написал декартово дерево).
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Посмотрев чужие решения (shik,lxyxynt) обнаружил что дерево фенвика можно успешно строить на map'e. Очень прикольно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://www.cplusplus.com/reference/algorithm/count/
    Здесь можешь посмотреть пример с сделать свою функцию. Или воспользоваться
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Эх, слил контест. Надо было в C все-таки загнать перебор для небольших значений (до 50) и найти закономерность, вместо того, чтобы разрисовывать большое кол-во случаев на бумаге.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Можно было просто идти по верхней строке и если мы сейчас стоим на клетке не под ударом, увеличить ответ и запустить поиск в ширину/глубину от нее, чтобы найти клетки, которые из нее можно побить. Разумеется, ходить нужно не по одному шагу, а сразу до следующего края доски. Состояние это координаты и направление движения. Количество состояний О(Н+М).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я так и хотел писать, но не смог грамотно реализовать все случаи отражения.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      А еще можно было немного порисовать отражения доски и превратить поиск в простое сложение по модулю.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну тут уже рисовать надо :) Я просто написал как можно было решить не включая мозг и не рисуя случаи на бумажке. Правда кодинг того что я написал занимает на порядок больше времени, чем считывание вывод gcd.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      я так делал. 32 мегабайт не хватило для рекурсии :( 
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Значит не зря я побоялся писать рекурсию и написал бфс.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          А я как-то сумел с рекурсией WA22 получить. Вроде сейчас даже погонял в "запуске" - не, стека хватает. Какой-то эпичный баг, видимо...
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            У меня рекурсивный вариант прошел.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Если поставить 128(а лимит вообще 256) то проходит, я не спорю.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                На GCC без шаманства проходит.

                 

              • 14 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
                Всё, нашёл свой эпичный баг.
                Погодите, так там ведь в опциях компиляции уже стек 256 МБ. Вот сейчас поставил специально прагмой размер стека 1 Б - всё равно прошло. Из этого следует, что ключи имеют высший приоритет, чем директива в коде? И если да, то как это согласуется с Вашим постом? Ничего не понимаю %)
                P.S. Короче, вопрос формулируется так: каким образом компилятор устанавливает размер стека?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  мне кажется что нельзя ручками поставить очень малелький стек - меньше 1М или что то в таком духе..
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится +5 Проголосовать: не нравится
                    ------------------------------------------------------
                    Ой, да Мегатерик, оказывается, на Pascal пишет. Тогда понятно. А я на C++ как ни пытался крэшнуться хоть со слишком маленьким, хоть со слишком большим размером стека - не получается. Даже локально. Видимо, нельзя выставлять ниже некоторого порога, а искусственно выставить много больше и даже пытаться эту память использовать - это компилятор соптимизирует. (Но это всё только экспериментальные гипотезы. Если кто-то читал учебники, буду рад услышать правильное мнение.)
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится

                      Ээ... суровые компиляторы типа GCC оптимизируют только то, что укажешь им в параметрах, и ничего лишнего. ;) Т.е. по-умолчанию подразумевается флаг -O0 - никаких оптимизаций.
                      Если говорить о размере стека - то это особенности конкретной ОС и кое-где возможно конкретного компилятора. Например, в linux ограничение на размер стека для нового процесса можно задать командой %ulimit -s, и т.о. "крэшнуться" элементарно - если задать 1кб, то почти любая прога при запуске выдаст segfault.

      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Извини меня=) прост сам напоролся на это, поставил 100М и на макс тесте у себя запустил. На будущее - у тебя было очень много параметров в рекурсии 128 канешно хватило но будь внимательнее))
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Во-во. А у меня наоборот: настолько боялся переполнить рекурсию параметрами, что, оказывается, затирал там глобальную переменную. Да так ловко затирал, что этот постмодернизм прошёл 21 тест =)
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Кстати, мне одному кажется, что системное тестирование стало быстрее идти, чем раньше?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    Намного быстрее. И это очень круто.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, только вот висят в состоянии 100% уже больше 5 минут.
14 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится
Very interesting problem.
A funny fact:
In problem A, the example said that tourist win, and it will comes true. :)
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Только что заметил, что в С++ коде fi подсвечивается синим. Удобно

UPD: а fj не подсвечивается :о(

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как я в задаче C додумался до формулы gcd(N - 1, M - 1) + 1... Посмотрел на задачу, там какие-то преломления по двум осям. Тут сразу понятно, что что-то завязано на GCD. Посмотрел ответ для матрицы 1 x M, он равен M. Посмотрел ответ для матрицы 2 x M он всегда равен 2. Далее - посмотрел на тесты из примера. Ясно, что получить большее число мы можем только при одном из аргументов равном нулю или равном самому числу. То есть надо отнимать единицы от аргументов. А стало быть GCD(N - 1, M - 1) + константа D, которая без труда определяется из 4 известных мне случаев и она равна единице. Один в один такая же формула была на ВКОШП 2006 года в задаче про кинотеатр. 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я догло сидел, и хотел найти признаки групп(очевидно, что убирать нужно с первого столбца), а потом посмотрел , что там есть период, и написал решение:
    пока Н не равно М , от большего отнимаем меньшее-1. Ответ: полученное число.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я после всех своих неудач в B прочитал C, понял, что это решается disjoint set-ом, но запутался в индексации координат лучей, в итоге недописал.
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
I remember a problem similar to the problem E:
I have solved this, the solution is also construction, and the problem in the recent contest seems a sub-problem of this one.
But codeforces contest is just 2-hour, so it's difficult to finish it.
And it's not easy to imagine this stuff and run it in mind.
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Сегодня во время контеста я заметил, как дезинформирует ранклист С идущем таймером, но БЕЗ автообновления ))
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Опечатка с русской С в условии это жестоко, лично для меня - 15 минут потраченых неизвестно на что в начале контеста. (Всегда во избежания опечаток все строки копирую из условия).

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Ух ты! Новый цвет!
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Apparently I don't get problem C. Why is the answer 4 for a board 4 by 4?

Edit: Ignore that, I just saw the part of the stament I misinterpet. "More formally, first one of four diagonal directions is chosen and the billiard ball moves in that direction. ". Apparently the author meant that just one of the possible four directions is chosen.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда разборы примерно будут? 
14 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
Спасибо за отличный (как всегда) контест :)
Предыдущие див2 раунды от Ripatti - мои любимые див2 раунды за все время. Каждый задача в наборе отлично служила своей цели и решать действительно было весело :)
Сегодня тоже очень удачный контест.
Жаль только, что моя D дописалась через минуту после конца контеста...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится
    Сдается мне, что Артем Рипатти вполне может получить медаль Кормена как лучший автор задач этого года :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I register a contest as a team member (in the All-Ukrainian School Olympiad in Informatics ).
After the contest, I resubmitted the problem and solved it in the PROBLEM SET page.
But, the system deal it as a team, not a person. The problem not turn to green.
I think it is a BUG.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Не такой уж плохой раунд для взломов. Если бы в А не было претеста с отрицательным баллом ответа - было бы как раз норм. для взломов. Вот В нормально можно было ломать, только, видимо, народу лень было в чужом коде разбираться.
У меня затуп смешной, я проверял максимальное количество минут, которые можно безопасно прятаться от контролера, в цикле for (i=l;i;--i) вместо for (i=l;i+1;--i), т.е. я не проверял случай, когда ловят на первой же минуте. В результате на системках ВА 13. Полистал результаты системок - редкостный баг, у большинства что-то другое.
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
deleted
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Было бы интересно услышать чего особенного в 14 тесте задачи D, ибо у меня на нем упала таска, и до сих пор найти багу не могу (даже при использовании скачанного верного решения и генератора тестов).
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Да вроде ничего особенного. Обычный большой рандомный тест.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      Спасибо за ответ. Значит буду дальше генерить, пока не найду в чем же проблема.

      Added: Проблема нашлась, она была в том, что я забыл что у людей могут быть номера большие чем число вешалок, когда добавлял фиктинвый узел, поэтому он мог конфликтовать с реальным узлом... Жесть. =)

      PS: Спасибо за помощь.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест! Задачки очень понравились!