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

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

Сегодня в 18:00 по Москве состоится GCJ Round 2. Напоминаю, что это шанс получить крутую футболочку — входите в число лучших 1000 участников и она ваша. 500 лучших участников проходят в Round 3.

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

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

Как решалась В?
UPD: Снова я без футболки остался...

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

    дополним каждый круг до квадрата со стороной степенью двойки с тем же центром, который этот круг содержит. Такие квадраты очень легко паковать

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

      на Small можно было упаковать круг в квадрат со стороной 2R и расставлять по периметру.

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

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

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

    У меня относительно хитро получилось так.

    Во-первых, у нас не кружки, а квадраты со стороной 2r и чувачками в центрах. Сразу поставим тех, которые капитально шире наших мат жадно в угол. Во-вторых, поймём, почему набор из квадратов со сторонами x1, x2, ... xn, таких, что сумма их площадей в ДВА раза меньше площади мата, всегда укладывается (а для начальных квадратов это верно). Развернём мат так, чтобы высота была меньше ширины. Пока есть квадраты со стороной минимум в полвысоты, кладём их жадно слева направо. А когда встретился квадрат со стороной l < h/2, откусываем от мата кусок шириной в l и высотой h и рекурсивно пытаемся положить на него как можно больше квадратов.

    Идея в том, что мы всегда кладя квадраты, поддерживаем, что остаток мата — прямоугольник, и его площадь в два раза больше суммы площадей всех оставшихся квадратов. Такая рекурсивная процедура это поддерживает, и поэтому она ну вот просто обязана работать из соображений индукции.

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

    Я тупо градиентно пихал в самую правую верхнюю позицию)

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

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

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

      Упорядочил квадратики рандомно и кидал их по очереди сверху вниз (аки в тетрисе). X-координату для броска выбирал рандомно 16 раз, самый нижний "пролёт" квадратика утверждал как окончательный. Морально готовился к перезапуску всей схемы "до получения результата", но всё укладывалось с первого раза=)

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

    Посортируем круги и будем брать сначала те, что побольше. Поставим самый большой круг R в левый верхний угол. Разрежем квадрат на две полоски ширины R и два "квадрата". Один уже занят кургом. Решим задачу рекурсивно, при этом ширину полосок можно просто уменьшить до 0, А размеры "квадрата" уменьшаются на R+Rmax, где Rmax — радиус самого большого круга на момент запуска функции для этого "квадрата". Доказывать это решение не умею, но оно прошло.

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

    Отсортируем круги по невозрастанию радиусов. Пусть мы расставили первые n кругов, ставим n+1-ый. Увеличим радиусы первых n кругов на радиус n+1-ого, получим фигуру, в которую не может попасть центр n+1-ого круга. Т.к. по условию площадь этой фигуры не превосходит 4/5 площади прямоугольника, n+1-ый круг можно гарантированно поставить куда-то, причем если искать это место рандомом то оно находится в среднем за 5 попыток

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

    Упорядочил по убыванию радиуса и ставил в ряды с центром на одной горизонтали. На всякий случай ещё использовал свободные места между рядами.

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

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

    Я подозреваю, что это решение можно доказать, аккуратно присваивая неиспользованную площадь кругам, но я этого не делал.

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

    Я решал так:
    1. Заменим круги радиуса R на квадраты радиуса 2*R, если мы разместим должным образом эти квадраты, то и круги тоже сможем разместить.
    2. Сортируем квадраты по убыванию радиуса.
    3. Начинаем с нижнего левого угла укладывать квадраты — первый центром в точку (0, 0), второй — вплотную к нему справа, ордината центра — 0.
    4. Делаем так, пока не упремся вправо.
    5. Сдвигаем нижнюю границу мата на 2*r[0], r[0] — размер максимального квадрата в нижнем ряду.
    6. Повторяем пункты 3-5, пока не закончатся квадраты.

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

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

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

      Мдаа... Первое, что в голову приходит. Думал, что не пройдет

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

    в small зашёл отжиг. На самом деле и в large должен зайти, но почему-то в окончательных результах написали ВА :(

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

      В смолл даже рандом заходит, кругов-то мало, максимум около 100 итераций потребуется.

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

        Hу так идея в том, чтобы отжиг и в large зашёл! ;)

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

        Да. Отжиг прекрасно заходит. Просто точности не хватило

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

Условие А — полное говно. Больше пытался понять, о чём вообще речь.

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

    Согласен! "You will slowly and carefully climb up your original vine, so that the new vine you are holding will become horizonta" Как вторая лиана может стать горизонтально в том же 3 тесте если ползти вертикально вверх? В общем ну их в баню с такими условиями, я плюс ко всему ещё в переводчик лазил, а то Индиано-Джонсовских словечек накидали)

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

      will become horizontal — either to its full length

      Либо она станет горизонтальной, либо натянется до максимума. В третьем тесте лианы станут буквой V.

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

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

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

          Да это лучше. Спасибо. В моём объяснении не хватит разгона долететь до конца.

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

          Можно, но в реальности это потребует бесконечной силы :)

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

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

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

      Чел вначале держит первую лиану так, чтобы она была натянута, далее он прыгает и может зацепиться за лиану, которую он пролетел.. получится, что у него в руках две лианы, он их натягивает так, что теперь обе они будут горизонтальны, и теперь он может ещё их перебирать в руках так, чтобы они остались горизонтальными и он находился между их корнями. Затем он может опять прыгать. Нужно добраться до бабы, которая в конце, при условии, что можно вот так менять лианы.

      Я решал эту задачу перебором от начала и смотрел для следующих лиан смогу ли я на них попасть и какой максимальный радиус я смогу описать всякой лианой (минимальный — 0), до которой достал. Ну и теперь если есть хоть одна лиана, которой мы можем попасть в конец зоны, то YES, иначе NO.

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

        Спасибо.

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

        Мне особо понравилось то, что герой может лазить по верёвке во время полёта, причём с невероятной скоростью. Т.е. на тест типа

        1
        1000 1000
        1000
        

        ответ: YES.

        И ещё пишут: "you are not a fictional hero". Ну какая нах тут правдоподобность?

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

Забавно, что 1004 человека набрало >= 21 балла. Интересно, выделит ли Google 4 дополнительные футболки? :)

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

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

    UPD: потому как моему знакомому два года назад с местом, ниже границы на где-то 20 позиций, футболка пришла. И это вряд ли кто выше отказывался :-)

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

Не хватило несколько секунд на B-small — скачать файл, скопировать, переименовать, запустить прогу...

Обидно :(

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

    Потому что ctrl+A, ctrl+C, ctrl+V быстрее, чем скопировать и переименовать файл.

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

      gcj.py download B small 0 && B.exe && gcj.py submit B small 0- быстрее

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

        Опасно так. Ты даже не просматриваешь, что вывела твоя программа, перед сабмитом?

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

          Если есть очень мало времени, то очевидно нет. Обычно это две команды между которыми можно посмотреть.

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

            Я к тому, что ты написал команды через &&, не успеешь ты посмотреть перед отправкой.

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

              А я еще раз повторяю, что это вариант для осталось 30 секунд до конца контеста.

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

    Мне также) Только у меня решение неправильное оказалось.

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

Как решать С?

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

    Утверждение: всё хорошо, когда отрезки (x, to[x]) вкладываются. Необходимость очевидна. Достаточность сейчас вытечет из алгоритма.

    Будем рекурсивно придумывать высоты горам с a-ой по b-ую с условием, что тангенс угла наклона между b и a равен k и все остальные горы на этом отрезке строго ниже отрезка ab. Берём последовательность гор x1 = a + 1, x2 = to[x1], x3 = to[x2], ... , xk = b и кладём их все на прямую с тангенсом k + 1. А содержимое отрезков [x1, x2], [x2, x3], ... покрываем рекурсивно, но уже с тангенсом угла k + 1. Более-менее очевидно, что это даст нам то, что нужно — из внутренности отрезка ab ничего не увидеть, потому что снаружи отрезка ab тангенс угла наклона меньше.

    Нам потребуется не более чем 1 + 2 + 3 + ... + n места, то есть порядка n^2. Как-то так.

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

    Я делала такую магию. Построим функциональный граф (из каждой вершины дуга в наибольший видимый из нее пик). Сначала юзаем последнюю вершину и ставим ей очень большую высоту. Потом начиная с первой непоюзанной вершины строим цепочку, заканчивающуюся в какой-нибудь поюзанной. Юзаем вершины получившейся цепочки и расставляем для них высоты так, чтобы они были на одной прямой. Затем обрабатываем следующую цепочку и т.д. Для каждой следующей цепочки увеличиваем наклон. Решение за квадрат. Если порисовать — понятно, почему работает.

    UPD. Решение фактически как у Zlobober, только без рекурсии. Случай Impossible удобно отсекать в самом конце проверкой за квадрат.

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

    Идём с конца и поддерживаем список гор, которые ещё могут быть видны как самые высокие. Вначале в этом списке только последняя гора. Если очередная гора видит гору не из списка, то impossible, иначе удаляем из списка все горы перед той, которую видит текущая, после чего вставляем текущую в начало списка. Чтобы получить высоты, рассмотрим дерево, в котором родителем каждой горы является гора, которую она видит. Будем обходить дерево (вначале заходим в вершину, потом в каждое поддерево по возрастанию номера) и присваивать каждой вершине угловые коэффициенты луча на самую высокую гору по возрастанию (например, последовательные целые числа).

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

Почему D-small такая дешевая? Начал ее писать вместо B-large и слил...

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

    Мне тоже кажется, что написать обход графа состояний (или перебор) + простую динамику стоит больше, чем 8 баллов.

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

    Ага, я накодил А и потом сел за D. В итоге, у меня даже D small не прошел. Сел дебажить и опомнился только за час до конца. Хорошо, хоть забил на нее и стал делать B и C.

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

    Там проходит простое моделирование. Пусть изначально состояние — множество клеток, из которых достижима пещера. Ограничения позволяют сгенерировать все состояния (множества), достижимые из исходного путем применения команд для всех клеток множества сразу. Их можно прямо хранить как векторы в сете. Ответ Lucky, если достижимо состояние из одной клетки-пещеры.

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

Вообще задачи не понравились:(

В A еле разобрал условие.
В B многие писали, "ну может это работает", не доказывая
Сам в C тоже сдал "Сперва сделаем примерно, а потом подгоним".

Надеюсь, Round 3 будет покруче

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

    Надеюсь, что не как в прошлом году, когда 2е от 67го отличалось только временем...

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

    Ещё разбалловка странная. Посмотрев на разбалловку В (за large гораздо больше чем за small), поверил, что на В.large всякие халявы не прокатывают. Зря.

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

      Я, чтобы поверить в успех по B-large, перед его скачиванием набросал генератор больших тестов и убедился, что моё решение без труда с ними справляется.

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

0 украинцев в топ-50, 1 украинец в топ-100... Затащили... Надеюсь, в следующем раунде будет круче.

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

    Как тонко границы проходят... украинцы на 51-м и на 101-м местах :)

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

Did anyone else sort for B and then forget to reverse it before doing the output? Because... I did.

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

It seems that everyone got D-large wrong. Is there a bug in the testdata, or is the testdata extremely tricky?

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

    Probably no one knows how to solve it properly so they tried some heuristics which didn't work.

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

Кстати. А то что их commandline tool показывает полный вердикт чекера, а не слово incorrect это баг или фича?

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

    А что именно содержит этот вердикт? Может он ещё показывает и вердикты для .large по ходу контеста? :)

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

    А можно поподробнее про ведикт, для тех кто command line tool не юзал?

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

      Ну он выдал сообщение вида Incorrect. В 13-ом тесте 6-ой видит 9-го, а должен 8-го.

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

        Ого, круто. Установлю-ка я эту штуку к следующему раунду.

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

          Мне кажется это баг, а не фича. Хотя непонятно, как можно "случайно" добавить функционал, который получает вердикт по посылке. И непонятно, почему об этом нет нигде не слова.

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

            Ну например скрипт который dashbpard его тоже получает и вырезает, а этот случайно не вырезал.

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

          Я думаю, что это баг и его прикроют.

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

    Скажем так. Правда ли, что в веб-интерфейсе точно никаких подробностией кроме Incorrect не увидишь?

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

Пожалуйста, подскажите что не верно в следующем решении C-small. Случайно генерирую высоты для гор h[]. Затем для каждой горы i выбираю гору j впереди с максимальным тангенсом, тоесть значением (h[j] — h[i]) / (j — i). Если j совпадает с обозримой наивысшей горой, то продолжаю. Если хоть одно не совпадает — генерирую заново.

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

    Вердикт Incorrect? Отработать успевает? Если оба да, то бага в реализации скорее всего.
    Дай код поглядеть)

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

      Да вердикт Incorrect. Код: http://ideone.com/zW78R

      Под правкой иллюстрация на триал тесты.

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

        вы уверены, что 105 итераций хватает для нахождения ответа, даже для n <  = 10? Мне это неочевидно, вроде для n = 10 различных тестов может быть около 5 тысяч, и непонятно, насколько часто при рандоме получается ответ на тот или иной.
        UPD а в строчке 18 по-моему все-таки лучше сравнивать используя eps, хотя при рандоме это не особо влияет вроде

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

        Во-первых, числа в аутпуте должны быть от 0 до 10^9, во-вторых, мне всё равно кажется, что 10^5 итераций — слишком мало.

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

In problem B, once we fail enough attempts to say it isn't possible to add the current circle, should we start all over again or backtrack to when we added the previours circle?

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

    Backtracking works. I try 20 different locations then go back to the previous circle.

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

    As stated in the analysis, we always have at least 20% chance to succeed. So the probability to fail x times is 0.8^x, which decreases rapidly. I also tried a solution without backtracking and it worked very fast. It means we only need to repeat the randomize progress until finding a consistent point. (you may take a look at tourist's code)

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

Is there someone who get T-shirts?