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

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

Примерно через 15 минут по плану должен начаться первый тур IOI 2014.

Результаты
Результаты от снарка
Видеотрансляция
Таблица по странам от Снарка

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

0:03 Судя по таблице контест начался по расписанию. Чтобы быть в этом уверенным, я дождусь появления первых баллов, после чего выложу условия.
0:04 У них что-то кешируется слишком злобно, так что если у вас все еще "подождите" Ctrl+F5 должно помочь.
0:12 На IOI-Conference подтвердили, что тур начался по расписанию.
0:13 Первые баллы! 42 от stevenkplus
0:17 Первые баллы по rail. 8 от Conor Griffin из Ирландии. Пока я это писал появились еще одни 8.
0:21 Так же быстро появилось много 8 по wall. Это простое моделирование того, что описано в условии.
0:26 dhh1995 получает 100 по game! Решение пишется достаточно просто, если его быстро придумать. При этом с придумать бывают проблемы. Вроде бы, она пробивается как-то еще с использованием мощных структур.
0:30 Еще одна сотня по game от участника их тайлайнда, и 30 по railes от уже известного Conor Griffin. У нескольких участников из Казахстана и Украины 8, остальные пока молчат.
0:31 И еще 3 сотни по game. У scott_wu xyz111 Baklazan и участника 0:38 24 по wall от stevenkplus. Это разбор частного случая, который видимо не очень поможет для полного решения.
0:39 30 по race от LeMieux.
0:42 61 по wall от Dominik Smrž из Чехии.
0:43 56 по rail от akshatb. Как видите участники пошли совсем в разнобой.
0:45 Scorpy 30 по rail 0:46 stevenkplus and Jacob Jackson 100 по walls!
0:49 KAN 30 по rails. По текущей статистике это не правильный выбор задачи. Впрочем,на IOI-контесте порядок задач не особо важен. Сегодня надо сдавать все.
0:52 Еще одна 100 по wall. От yutaka1999.
0:53 zemen и -imc- 100 по wall!
1:00 xyz111 200! Может и действительно 300 будет раньше, чем я ожидал.
1:04 scott_wu присоединяется к 200.
1:07 Baklazan 200. Кажется 200 это уже не событие.
1:12 У KAN посылка на 0 по game. Вообще это достаточно странно. Реализация решения вроде совсем простая, думаю скоро разберется. 1:34 У sivukhin 30 по rail. Видимо тоже не тот порядок задач. Я пока автоматизирую слежку. 1:38 30 от sivukhin быстро превратилось в 56.
1:48 230 у dhh1995.
1:51 У KAN посылка на 0 по walls. К чему бы это.
1:55 100 по rail от asterius. Итого все задачи открыты в 1:49.
1:58 256 у dhh1995.
2:00 Наши активизировались. У KAN 100 по wall, у zemen 8 по rail, у -imc- 42 по game.
2:01 А вот и первые 300. Поздравляем scott_wu. Даже не пол часа быстрее меня в 11-ом году.
2:07 В соответствующем посте появились фотографии с открытия.
2:23 Miras321 и emachaidze 162, -imc- 142, KAN 130, zemen 108. У остальных за кем я слежу меньше 100. Тем временем 200 сейчас это 5 место. И таких 11 человек.
2:31 Прошла половина контеста. Все американцы сдали game, все китайцы сдали wall. Наши как-то затихли.
2:32 У sivukhin 8 по wall.
2:35 И из 8 очень быстро получилось 61. Интересно что это. Скорее всего это надо достаточно сильно доделывать до 100.
2:39 Появились английские условия. Спасибо делегации Армении. А они ведь давно лежат на сайте, да?
2:45 У sivukhin еще раз 61 по wall. Видимо он хочет больше.
2:47 dhh1995 300!
2:48 sivukhin 8 по wall?!
2:52 Zlobober предположил, что Никита пихает корневую. Это может плохо кончиться.
3:02 KAN zemen -imc- больше часа сидят без посылок. Надеюсь скоро что-то произойдет.
3:15 KAN 100 по game!
3:16 zemen 42 по game. Прогресс. Никиты, присоединяйтесь :)
3:23 Scorpy поднялся на 30 место со 172 баллами.
3:24 От KAN еще одно 30 по rail. Будем ждать больше.
3:25 sivukhin 42 по game. Отложить wall это правильное решение в такой ситуации.
3:34 sivukhin 100 по game! Интересно, что он будет делать дальше. Видимо у него есть плохое решение по wall и никакого по rail. 3:40 KAN присоединился к большой группе по 256 3:47 -imc- уже сидит без посылок почти два часа. Интересно, что бы это значило? Пишет какой-то ад по rails?
3:53 Тем временем, все еще только два человека имеют 300. И 10 256. Вероятно отсечка золота после первого тура будет проходить по отметке 230. Причем очень сильно деленному 230.
3:58 -imc- послал 8 по rail. Ну хоть что-то за 2 часа.
4:05 Еще одно 300 — Leoyu
4:14 sivukhin 30 по rail. Интересно. Видимо он написал что-то другое с багами.
4:23 От zemen как уже больше часа ничего. Интересно, что он сейчас делает? Надеюсь скоро увидеть 100 по game или 56 по rail.
4:34 Привет сборной Казахстана. Miras321 100 по game, NurlashKO 30 по rail с интервалом в 10 секунд.
4:35 Пока писал последний пост -imc- сделал 30 по rail
4:42 Очереди тестирования кажется совсем нет. Ну либо они пишут во времени посылки время, когда она протестирована. Тем временем еще 30 по rail от -imc-.
4:44 Внезапно, 261 от AstroConjecture 4:47 Я ушел ближе к месту проведения, так что видимо это последний пост. Надеюсь кто-то из ребят еще порадует в последние минуты. 4:59 Удачно прошел. sivukhin 100 по rail, zemen 30 по rail. 5:00 Контест закончился,возможно еще несколько не протестированных посылок.

Краткий разбор задач (разбор белым шрифтом, если выделить станет виден) (Условия только русские, официальные я вчера забыл скачать)

rails. Условие (EN). Говорят, что если отсортировать все станции по расстоянию от нулевой, то можно определять их положение и тип по очереди, делая два дополнительных запроса. Если честно, я не пока не разбирался в деталях.

wall. Условие (EN). Будем хранить наш массив в дереве отрезков. Опрецией обновления в нем будем считать "загнать числа в отрезок [l, r]". Последовательное применение таких операций, является операцией такого типа, поэтому можно стандартный способ делать груповые опрерации будет работать. Надо быть осторожным с тем, что операция некомутативна.

game. Условие (EN). Будем поддерживать инвариант: внутри компонент связности нет ребер, про которые еще не задан вопрос. При этом всегда, когда можно ответить да, с сохранением инварианта будем отвечать да. Это не сложно реализовать за квадратичное время, при этом легко доказать, что граф в итоге окажется связным. При этом в первый момент когда это будет так, не будет неизвестных ребер внутри компоненты, а значит вообще.

Комментарий. Задачи выглядят достаточно простыми по отедльности, однако во всех трех надо придумать некоторую идею, с которой могут быть сложности. При чем скорее всего у разных людей в разных местах. Так что мой прогноз — все задачи будут решены на 100 достаточно быстро разными людьми. Полные баллы будут но ближе к концу контеста и не очень много. Увидим насколько он оправдается

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

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

Первые баллы. Хотим условия!

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

Если кликнуть по профилю участника в таблице, можно увидеть названия задач второго дня и разбалловку по группам тестов. Вряд ли это даст кому-то преимущество, но все равно похоже на баг.

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

    Насколько я понимаю, это пробный тур, а не второй день.

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

    Нет. Это задачи пробника. Но все равно похоже на баг.

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

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

PavelKunyavskiy можно пожалуйста условия на английском тоже? Ну и если вдруг на онсайте что-то про видеотрансляцию известно, тоже сообщи, пожалуйста.

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

Вопросы в английском языке, пожалуйста!

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

Первая сотня по game!

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

Уже несколько сотен по game!

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

Видео доступно по следующему адресу.

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

ИМХО полных баллов сегодня будет достаточно много)

По wall, кроме участников с сотней, есть так же и Dominik Gleich с 61 — что такого можно придумать, чтобы оно проходило первые 3 группы, но не проходило последнюю? Корневую написать вместо дерева отрезков?

На стриме только ~40 человек пока что... Я думал, это мероприятие более популярное.

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

    Многие спят, к тому же линк опубликовали на офиц. сайте только 10 минут назад.

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

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

UPD Конечно, не зайдет, тут плохое матожидание :)

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

    Если перестраивать целиком за N^2, то не зайдет, конечно

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

А вот и 300.

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

Не думаю, что кто-то реально хочет получить 100 за корневуху. Скорее, это что-то вроде "на 100 не могу придумать, напишу за 30 минут на 60, а потом вернусь, если че."

Еще, мне кажется, что в этой задаче, в процессе написания корневой, очень хорошо придумывается ДО.

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

.

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

    Там еще бывает log^2 который непонятно успеет ли, и медленный. Возможно это. В любом случае, лучше бы ему это отложить сейчас.

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

А я так и не нашел в правилах. Участники видят результаты других?

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

А трансляция контеста где-нибудь есть?(Контест с аналогичными задачами)

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

Из Беларуси один не приехал?

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

    Нет, у него полно посылок.

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

    Судя по тому, что у него уже 12 сабмитов в статистике — приехал...

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

      А как смотреть сабмиты?

      UPD Уже нашел.

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

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

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

      Его попытки были не зря. Он очень старается!

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

    Просто Фёдор любит экстрим и структуры данных. Еще eps по остальным и зашло бы для первого дня

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

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

      P.S: Дайте ему кто-нибудь щелбан от меня за это. Но вообще, молодец, справился с волнением :)

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

        Я тоже не спал из-за этого:) Молодец, конечно! Но надо бы второй день не слить, и лучше бы без нулей по задачам.

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

          А я, находясь в Тайване, проспал первые три часа трансляции >.<

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

            Из Тайваня наблюдать за IOI так же скучно? Уж слишком мало динамичности:(

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

seland, похоже, немного не то решает... Только что сабмит по rail на 0, по wall до сих пор без посылок.

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

261 у sivukhin

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

Немного странно видеть 0 по wall у Alex_2oo8.

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

    При том, что он всегда сдает реализации пострашнее на codechef..:(

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

Господа! (и дамы)

Допустим, в game я делаю следующим образом: я ранжирую вершины (у вершины, которая впервые встретилась в вопросе раньше, ранг больше, если одновременно встретились, то неважно). Понятно, что с каждым вопросом ранг можно доопределить, причём каждый раз, когда новая вершина получает ранг, он будет ниже всех предыдущих. Далее, для каждой вершины я храню количество уже заданных вопросов про неё и вершины низшего ранга (если для какой-то вершины ранг ещё не определён, то она явно не участвовала ни в каких вопросах). Итак, как только мне задали вопрос, я доопределил ранг, у меня есть 2 вершины различного определённого ранга, от меня ждут ответа. Я беру ту из них, что имеет больший ранг, и отвечаю, что ребро есть ровно в том случае, если все остальные рёбра, соединяющие эту вершину с вершинами низшего ранга, уже были спрошены. Легко видеть, что всё это дело делается за линию.

UPD: пардон, линия количества запросов, то есть, квадрат, я глуп

Внимание, 2 вопроса:

1) Нет ли тут косяков?

Вроде бы, нету: в каждый момент времени, кроме последнего, если неизвестные рёбра окажутся существующими, то как бы мы ни доопределили ранг, каждая вершина окажется соединённой с какой-то вершиной низшего ранга, то есть, граф связен. Если же неизвестные рёбра окажутся несуществующими, то вершина наименьшего имеющегося ранга, для которой есть хоть одно неизвестное ребро, соединяющее её с меньшими рангами, окажется отрезана от меньших вершин, а у всех вершин большего ранга степень в меньшие ранги равна 1, так что граф несвязен. То есть, до последнего момента отгадывающий не сможет определить связность. Тогда вопрос номер

2) Отличаются ли ответы, получаемые этим алгоритмом, от ответов в предложенном в посте решении? Я имею в виду, строится ли в итоге один и тот же граф? Заранее спасибо.

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

    Похожее решение рассказывали на live stream, только там пошли еще дальше — вершинам заранее раздали ранги в порядке их номеров, и при обработке запросов просто считали для каждой вершины, сколько еще осталось ребер в нее из вершин с меньшим номером. Как было сказано, это решение предложил один из тестеров, авторы его изначально не увидели. В трансляции это решение довольно точно охарактеризовали как pure magic.

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

Can we submit the problems anywhere ???

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

Думаю, Scott Wu возьмет 600 баллов.

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

Похоже, что нижние границы баллов для золота/серебра/бронзы будут близкими к прошлогодним: 480/360/220.

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

А как писать белым шрифтом?

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

Разбор задачи Game :

Будем поддерживать инвариант

Что такое инвариант ???