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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится
Не смог соответствовать условию первой задачи, всего 1 челлендж :(
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Более идиотской баги, чем неумение создавать дерево интервалов нулевого размера я придумать не мог :(
15 лет назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится
Ух ты!!! Вопросики вместо устрашающего НЕ ПРОЙДЕНО. Спасибо администрации - )
15 лет назад, скрыть # |
 
Проголосовать: нравится +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 :)
15 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

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

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

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

                 

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

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

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

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

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

15 лет назад, скрыть # |
 
Проголосовать: нравится 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 года в задаче про кинотеатр. 
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    А я догло сидел, и хотел найти признаки групп(очевидно, что убирать нужно с первого столбца), а потом посмотрел , что там есть период, и написал решение:
    пока Н не равно М , от большего отнимаем меньшее-1. Ответ: полученное число.
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Я после всех своих неудач в B прочитал C, понял, что это решается disjoint set-ом, но запутался в индексации координат лучей, в итоге недописал.
15 лет назад, скрыть # |
 
Проголосовать: нравится +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.
15 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится
Сегодня во время контеста я заметил, как дезинформирует ранклист С идущем таймером, но БЕЗ автообновления ))
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Опечатка с русской С в условии это жестоко, лично для меня - 15 минут потраченых неизвестно на что в начале контеста. (Всегда во избежания опечаток все строки копирую из условия).

15 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
Ух ты! Новый цвет!
15 лет назад, скрыть # |
← 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.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Когда разборы примерно будут? 
15 лет назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится
Спасибо за отличный (как всегда) контест :)
Предыдущие див2 раунды от Ripatti - мои любимые див2 раунды за все время. Каждый задача в наборе отлично служила своей цели и решать действительно было весело :)
Сегодня тоже очень удачный контест.
Жаль только, что моя D дописалась через минуту после конца контеста...
15 лет назад, скрыть # |
 
Проголосовать: нравится 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.
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Не такой уж плохой раунд для взломов. Если бы в А не было претеста с отрицательным баллом ответа - было бы как раз норм. для взломов. Вот В нормально можно было ломать, только, видимо, народу лень было в чужом коде разбираться.
У меня затуп смешной, я проверял максимальное количество минут, которые можно безопасно прятаться от контролера, в цикле for (i=l;i;--i) вместо for (i=l;i+1;--i), т.е. я не проверял случай, когда ловят на первой же минуте. В результате на системках ВА 13. Полистал результаты системок - редкостный баг, у большинства что-то другое.
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится
deleted
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Было бы интересно услышать чего особенного в 14 тесте задачи D, ибо у меня на нем упала таска, и до сих пор найти багу не могу (даже при использовании скачанного верного решения и генератора тестов).
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +6 Проголосовать: не нравится
    Да вроде ничего особенного. Обычный большой рандомный тест.
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится
      Спасибо за ответ. Значит буду дальше генерить, пока не найду в чем же проблема.

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

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