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

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


День труда в этом году начался для меня 1-го мая в 9 часов утра, а закончился спустя сутки. В Будапеште десятый раз проходил 24-часовой контест Challenge 24.

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

Формат финальных соревнований таков: команда из трёх человек, без ограничений по возрасту, приносить можно компьютеры, литературу, спальные мешки :-). Большинство участников принесли по лэптопу, но некоторые местные команды приволокли мощные десктопы и целые дата-центры. Средство связи используется ровно одно - локальная сеть, каждой команде выдаётся до четырёх статических ip-адресов. Мобильники и другая связь с внешним миром, как водится, запрещены. Общение с жюри по IRC. Сдача решений исключительно напрямую по TCP/IP: для каждой задачи объявлен хост и порт, протокол общения зависит от задачи.

Проблемсет в этом году включал восемь задач, оценённых от одной до семи тысяч баллов. Половина задач - вполне традиционные алгоритмические, в духе ACM. Остальная половина - разнообразные, от игровых а-ля Java Challenge / Code Game Challenge до развлекательной задачи "Объём". На каждую ACM-подобную задачу было сразу опубликовано по 10 тестов стоимостью 100 баллов каждый (штрафа за неудачные подходы нет). Требовалось отсылать жюри только ответы на тесты, прямо присоединяясь к указанному хосту/порту, например телнетом.

Чуть подробнее о четырёх нетрадиционных задачах. Задача, оптимальное полиномиальное решение которой неизвестно, оценивалась исходя из максимума в 1000+1500. Тысячу можно было набрать, предъявив в каждом из десяти тестов решение лучше чем у других участников. (Точнее: отдельно по каждому тесту корректные ответы команд сортировались по оптимальности; лучшее решение получало 100 баллов, остальные меньше, по приведённой в условии формуле.) Ещё до полутора тысяч можно заработать, отправив жюри свой пример входных данных со своим ответом. Подробности начисления баллов в этом случае не были описаны подробно.

Игровая задача на 2500 баллов - танки. Танки умеют торговать оружием и стрелять. Условие задачи странным образом опускало всяческие подробности правил, предлагая участникам написать решение и запуская его, выяснить как там всё устроено. В общем это единственная задача, на которую мы ничего не написали. (Хотя какие-то баллы заработать следовало.)

Последняя, главная, задача - вертолёты (7000 балов максимум). Требовалось написать управление вертолётом, с учётом физики, случайного ветра. Лететь к заданной точке, управляя несущим и рулевым винтами, оказалось непросто. Перевозить коммерческие грузы из пункта А в пункт Б, не задевая за препятствия - ещё сложнее. Разрешалось губить вражеские вертолёты, задевая корпусом за их несущий винт; наша команде первой удалось это сделать, за что мы получили специальный диплом :-)

Ах да, и ещё одна прекрасная задача на тысячу. Как и на алгоритмические задачи, было дано десять наборов входных данных. Каждый набор - это три-пять рендеров (в формате .png) некой трёхмерной сцены. На сцене всегда присутствует белый кубик единичного объёма  и предмет, объём которого необходимо определить. В десятом тесте, например, была симпатичная корова. По каждому тесту ответы команд ранжировались по удалённости от истинного объёма, далее начислялись баллы за первое-третье места: 100, 80, 66; за четвёртое и последующие места: 60-2*место. Каждая команда знала, сколько получила баллов за каждый тест, и имела право раз в час ресубмитить свой вариант.


Несколько слов о моих впечатлениях. Соревнования оказались очень увлекательны: по духу напоминают участие в тренировочных сборах. Сутки пролетели незаметно, разве что около трёх часов ночи и около шести очень хотелось спать. Полседьмого была зарядка на улице - весьма ободрила! Будапешт оказался очень красивым городом. Всем рекомендую участвовать в следующем году.


  


P.S. Результаты: победили поляки, на втором Венгрия, третьи (с существенным отрывом) словаки, четвёртые шведы (в составе Fredrik Niemelä, организатор финала в Стокгольме в 2009), пятые ЮАР+ЮАР+UK (включая Bruce Merry aka bmerry), шестые - Сербия, седьмые - Венгрия+Венгрия+Сербия, восьмые - словаки, девятые - немцы, десятые - мы, одиннадцатые - Львовчане, всего приехало 28 команд.

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за статью! А как организация? Были ли у них баги/реджаджы?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Сайт соревнований был неудобный: гиперссылки не кликались, отправлять решение большинства задач логичнее было бы веб-формой, а не телнетом. Реджадж я подозреваю в одной задаче из-за теста, который у меня упорно не проходил (а остальные 9 проходили), но после жалобы в жюри по IRC и пятикратного ресабмита всё же прошёл. По другой задаче были временные проблемы, просили не субмитить, потом починили.

    В кабинете сидело по 3-4 команды, отделённые друг от друга ширмами. Все 24 часа было достаточно еды и напитков. Вечером несколько часов подряд желающим делали массаж :-)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Очень интересно! Псасибо за статью). Ну в следующем году ты намерен завоевать 1-е место?!:)

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо, Кать! Да, осталось Игоряна подбить участвовать на тот год)))))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А в задаче про объем тесты были не даны участника заранее? А то легче глазом объем угадать:).
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так всё и было, гадали глазом+линейкой, тесты сразу дали, вот несколько примеров:

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Интересно, а что-нибудь о расстоянии до объектов или между было известно? А то по этим рисункам с перспективной проекцией, по-моему, его невозможно определить, а соответственно и объем может быть сколь угодно большим или малым.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хотя, если был известен результат после каждой посылки, то можно было организовать тернарный поиск даже не глядя на картинки. Правда попытак маловато получается... :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Никакой дополнительной информации не было. Но поскольку давалось по три-пять картинок с разных сторон, можно было определить взаимное расположение объекта и кубика. Клетчатый пол тоже помогает.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Эх, а у нас не получилось поехать..