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

Всем привет!

Добро пожаловать на VK Cup 2012 Уайлд-кард раунд 2!

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

В основном конкурсе этого раунда участвуют те, кто официально прошел в VK Cup 2012 Раунд 2, но не прошел в VK Cup 2012 Раунд 3. По результатам VK Cup 2012 Уайлд-кард раунд 2 лучшие 25 участников завоюют право участия в VK Cup 2012 Раунд 3. Все остальные члены сообщества могут принять участие вне-конкурса, just for fun.

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

Удачи! Пусть победит сильнейший!

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

И да, огромное спасибо Nickolas за великолепную задачу!

UPD: Контест закончен, тестирование завершено. Поздравляем первые 25 мест — результаты, вы вышли в VK Cup 2012 Раунд 3!

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

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

Повторюсь — можно ли в предстоящих соревнованиях указать сколько будет длиться этот раунд?

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

Нельзя делиться результатами (в том числе просто сообщать баллы) запуска своих решений на каких-либо тестах.

Ого! Не будет вообще никакой информации о текущих результатах других участников?

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

i really like this rules, although i'm an unofficially participant. i think it's like Marathon in top-coder a little bit, and it means that the problem is more real. i hope this kind of contest can be hold in the future regular.

look forward for it & good luck for everybody! have fun!

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

Sorry for a bit off topic. Mike, is the site having some trouble in recent hours? I’m not able to view solutions on the standing pages.

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

Спасибо, будет очень интересно поучаствовать в таком необычном соревновании!

Вопрос: будет ли раунд рейтинговым для конкурсных участников (прошедших в Round 2)?

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

у кого-нибудь есть такая проблема: запускаю check.exe или gen.exe — системная ошибка: отстутствует libgcc_s_dw2-1.dll?

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

    я скачал, но потом требует другую libstdc++-d.dll))

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

      можете ссылку дать где скачали?

      P.S. не надо, можно скомпилировать исходник gen и check, они там есть и ничего не скачивать

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

    Скомпилируй файл gen.cpp (аналогично для check.cpp) из папки src любым C++ компилятором и запусти его.

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

    Перекачайте архив

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

      а где можно скачать? невижу

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

      может стоит сделать, чтобы run-gen и run-checker не закрывался сразу после запуска?

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

        Он вроде не закрывается. Ты используешь батник или шелл-скрипт?

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

          батник

          да это не проблема, ну просто для порядка, поставить какой нибудь _getche(); вконце, чтобы не закрывался как бы его не запускали

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

            Как-то неприлично так в программах делать. Допиши в батник строчку pause.

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

              а почему неприлично?

              так же неприлично, как и метки использовать?

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

                Из чуть более логичных соображений — программа может запускаться не только руками, но и в автоматическом режиме. В случае наличия лишнего интерактива (как, например, "Нажмите любую клавишу") это становится сильно труднее, что неправильно — легче дописать строчку в bat'ник, чем просить у автора исходник программы и пересобирать.

                По этим же причинам ввод/вывод на олимпиадах, казалось бы, происходит в достаточно чётком формате, без приглашений, комментариев и GUI.

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

            Ты видимо запускаешь батник из папки в обозревателе Windows, поэтому у тебя и закрываетя. Варианта 2: либо запускай из cmd.exe или farа, либо сделай так как написал ниже Hohol

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

              да я пробовал с cmd, тоже какой-то путь не находит

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

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

            Мой первый дабл-коммент.

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

@JOKE@ Забыли добавить уже традиционную запись "Пожалуйста, чтобы раунд для вас был еще интереснее, прочитайте условия ВСЕХ задач." ^_^ @JOKE@

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

    И в комментах должны спросить про взломы и динамическую стоимость.

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

А какой максимальный балл можно получить по задаче? (пока)

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

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

    Число баллов не ограничено явно, но оно зависит от решения, поэтому его ограничивает только теоретически оптимальное решение.

    З.Ы. А ответ по поводу того, какое максимальное теоретически возможное число баллов можно набрать на претестах, даже если эта инфа есть у авторов/админов/коготоещедругого — думаю, является обсуждением задач, что правилами запрещено.

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

      Вот, кстати, интересно, если кто-то наберет максимум возможных баллов на претестах, у него статус изменится на "претесты пройдены"? :)

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

        хватит вам уже задачу обсуждать

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

Если бы я принимал реальное участие в соревновании (т.е. выкладывался на полную и соревновался за место в топ-25), то мне бы сильно помогла кнопка, аналогичная топкодеровской history of submissions.

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

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

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

Или я туплю, или в визуализаторе бага.

Инпут:

72 84
2
11 59
9 58

Аутпут:

49.1 2.1 60.1 61.1
60.2 3.1 69.2 61.1

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

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

Ффу, теперь можно и поспать.

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

Извините, я не совсем понимаю, почему во вкладке стутус у кого-то написны баллы, а у кого то "х претестов из 10"? Как можно пройти претесты, тут ведь в том то и соревнование кто больше баллов наберет. Или на каждом претесте нужно набрать какое-то минимальное число баллов?

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

    Претест можно пофейлить — то есть получить на нем WA, PE, TL, RE.

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

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

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

Тестирование повисло.

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

Hello,

Are we allowed to include the checker's code in our submissions?

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

Nickolas в своем репертуаре...

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

    Собственно, это (марафоны) и есть мой основной репертуар, ULR — это так, баловство :-)

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

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

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

А входные ширина и высота прямоугольника только целочисленные? И после масштабирования должна ли сохраняться целочисленность? Вроде в первый раз читал, это было в условии, а сейчас не нашел. Или я сонный такой уже %)

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

Я делаю довольно много отладочной печати в поток cerr, но не знаю, разрешено ли это вообще. Не получу ли я внезапно какой-нибудь Security Violation на систестах, если много писать туда буду?

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

    Если не получишь ТЛ все будет нормально. Но лучше обернуть весь дебаг вывод в ifdefы.

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

Вопрос немного не по теме, но почему перестали показываться коды решений в прошлых контестах при двойном нажатии на них? Или это только у меня так? И если нет, связано ли это с VK Cup 2012 Уайлд-кард раунд 2?

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

 Марафоны писать — китайская народная забава?

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

Только я не могу посмотреть код участников в любом раунде?

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

Кстати, теоретически возможно такое, что у нескольких участников в итоге будет одинаковое число баллов. Если 25ое место будет поделено, по какому признаку будут выбирать тех, кто прошел? По более раннему последнему сабмиту? Или дальше пройдут все?

О, спасибо что показали. Уже и забыл о тех правилах, искал только в локальных.

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

    Цитата из анонса Vk Cupa : "В случае, если несколько участников имеют одинаковый балл в отборочном этапе и попадают на границу отбора, то все они выходят в следующий раунд."

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

It looks like that the grader stopped working.

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

Раунд окончен, ждем тестирования.

Кто как решал?

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

    Жадник.

    Ставим первый прямоугольник в угол. На каждом шаге перебираем, какой прямоугольник поставить следующим, какой стороной, как его растянуть и куда поставить. Ставим так, чтобы угол нового прямоугольника совпадал с одним из старых углов, то есть при фиксированной ориентации и размере есть 8*n возможных расположений. Каждый раз жадно выбираем следующий ход. Еще стоит запустить жадник несколько раз. У меня не было времени особо все оптимизировать, поэтому я успеваю сделать немного — на ста прямоугольниках всего раз пять-шесть.

    После этого выбираем лучший ответ и пытаемся его улучшать. Я это делал локальными оптимизациями: возьмем один прямоугольник и попробуем его чуть-чуть куда-нибудь подвинуть. Если ответ улучшился, двигаем.

    Само собой, на это навешана куча всяких эвристик вроде сортировок по параметру MAGIC, запрета на сужение/расширение в определенном интервале, чтобы один прямоугольник не занял все свободное место, и тому подобное. Написано все практически за одну ночь и один день — я слишком поздно понял, что раунд скоро кончается :) Результат — 5171 на претестах.

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

      Я тоже писал похожую жадность, только без фичи с углами. Плюс в конце, после расстановки всех прямоугольников, увеличивал те, увеличение (без перемещения) которых ничего не портит. Ну и тоже всякие мутные эвристики. Из-за того, что вариантов расстановки очень много, пришлось ставить отсечение по времени. Результат на претестах — 4257.

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

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

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

          После добавки оптимиза с увеличением в конце мой балл на претестах увеличился на 3 :) Но я все равно оставил, хуже точно не будет. У меня лучшие подъемы были после подгонов с сортировкой и с масштабированием. Я не придумал как можно вменяемо масштабировать (перебор позиции + коэффициента работает уж очень медленно), поэтому пришлось подгонять отдельно; видимо, это главный провал моего решения.

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

      Тоже самое.

      Были ещё отсечения такого вида — для каждой точки можно хранить информацию какой угол в ней заканчивается, тогда соответственно в эту сторону растягивать не имеет смысла.

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

      При равенстве очков, выбирал с наименьшим периметром, а среди таких наибольшую по |x|+|y|, т.е. как бы сдвигал все в одну сторону, а в конце пробывал когда сдвигам при равенстве очков выбирал с минимальным |x|+|y| — это хорошо когда у нас последовательно стоят блоки, тогда он их сможет растащить.

      Также пробывал двигать не только на чуть чуть, а до упора в какую либо сторону и чуть чуть не до упора. Количество итераций на больших тоже очень маленькое... 4-5.

      Результат 5314. Максимальный был 5380, но это с rand(0), а так привязал rand к входному тесту.

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

    Тоже жадный алгоритм.

    Сортируем по "вытянутости", тоесть по величине w/h. Берем первый прямоугольник, вытянутый в одну сторону, ставим (увеличивая по максимуму: не более чем в два раза и чтобы хватило места), берём второй вытянутый в другую сторону — ставим, но ставим переворачивая. Соприкосновение получаеться по стороне что подлиннее. Так расставляем всё, что можем. Получаем как бы стопку из прямоугольников.

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

    Потом еще брал один сильно вытянутый прямоугольник и ставил его поперек между третьей и четвертой частями. При этом прямоугольники состыковываем с этим вертикальным (но только те, что дадут + к баллу). Он много место жрал, но зато +60 балов на претестах я получил :).

    Вот иллюстрация второго претеста (тут разбиение на 3 части и прямоугольник между вторым и третьим "столбиком"): картинка

    Решение на претестах получает 4990.8 баллов

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

    Я написал перебор, который хранит линию границы уже поставленной области. Каждый раз беру левую нижнюю точку и ставлю туда самый выгодный прямоугольник. Либо не ставлю ничего и сдвигаю эту точку. Для выбора прямоугольника используются всякие шаманства, а также перебор отсекается по времени. Чтобы лучше работало, я перебираю внешним циклом магическую константу и затем уже для нее запускаю перебор на 0.05 секунд либо 1000 итераций (что раньше наступит). В самом конце жадно улучшаю ответ. Набирает 5602 на претестах.

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

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

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

        Вот ссылка. Я не сильно заморачивался и не удалял из кода лишние функции и переменные. Там много всего лишнего, но если не пытаться разобраться, то использовать можно :)

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

          Красивейшие результаты.

          Вот например очень радует

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

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

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

    Ну, на картинке понятнее, думаю (уже после оптимизации, финальный вариант на втором тесте):

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

    Я клал прямоугольники слоями, стараясь делать так, чтобы верхние прямоугольники образовывали лесенку с чередованием цветов. А затем запускал оптимизу, которая заполняла пустые места маленькими прямоугольниками. Мой код.

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

How much time is the testing on the final tests expected to take? :)

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

Will the sources be open after the contest?Or is there going to be any tutorial or summary? I'm just wondering how they(especially who with a high score) got that high score...

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

А можно узнать хотя бы приблизительные сроки оглашения результатов?

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

в чем дело, почему до сих пор нет системного тестирования? во вкладке "статус" можно поставить фильтр "вердикт: выполняется" и удивиться: там "выполняется" тест двухдневной давности!

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

The system test has ended!!! It took so long a time...

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

How about publishing the submissions, now the contest is over?

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

Will it be possible to submit in practice mode later on?

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

I think the link of stndings in UPD is wrong.

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

как у yefllower может быть отрицательное кол-во баллов??

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

    Цитата из условия:

    Если пара прямоугольников имеет одинаковую ориентацию (то есть оба не были повернуты или оба были повернуты относительно своего первоначального положения), то из баллов вычитается lij.