Примерно через 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 достаточно быстро разными людьми. Полные баллы будут но ближе к концу контеста и не очень много. Увидим насколько он оправдается
Первые баллы. Хотим условия!
Если кликнуть по профилю участника в таблице, можно увидеть названия задач второго дня и разбалловку по группам тестов. Вряд ли это даст кому-то преимущество, но все равно похоже на баг.
Насколько я понимаю, это пробный тур, а не второй день.
Нет. Это задачи пробника. Но все равно похоже на баг.
По идее должна быть видео трансляция, как в прошлом году (потому что я сделал чуть больше чем дофига графиков для неё), но линк на неё пока неизвестен мне (как и во сколько она планирует запуститься). Как только он мне станет известен, я его сюда запосчу.
PavelKunyavskiy можно пожалуйста условия на английском тоже? Ну и если вдруг на онсайте что-то про видеотрансляцию известно, тоже сообщи, пожалуйста.
Вопросы в английском языке, пожалуйста!
Первая сотня по game!
Уже несколько сотен по game!
Видео доступно по следующему адресу.
ИМХО полных баллов сегодня будет достаточно много)
По wall, кроме участников с сотней, есть так же и Dominik Gleich с 61 — что такого можно придумать, чтобы оно проходило первые 3 группы, но не проходило последнюю? Корневую написать вместо дерева отрезков?
На стриме только ~40 человек пока что... Я думал, это мероприятие более популярное.
Многие спят, к тому же линк опубликовали на офиц. сайте только 10 минут назад.
В game зайдет такое?: построим рандомный остов, и будем перестраивать его, только если спросили про ребро, которое в него входит, и его можно удалить, не теряя связность.
UPD Конечно, не зайдет, тут плохое матожидание :)
Если перестраивать целиком за N^2, то не зайдет, конечно
А вот и 300.
Не думаю, что кто-то реально хочет получить 100 за корневуху. Скорее, это что-то вроде "на 100 не могу придумать, напишу за 30 минут на 60, а потом вернусь, если че."
Еще, мне кажется, что в этой задаче, в процессе написания корневой, очень хорошо придумывается ДО.
.
Там еще бывает log^2 который непонятно успеет ли, и медленный. Возможно это. В любом случае, лучше бы ему это отложить сейчас.
А как за log^2?
Там какая-то магия с двумя деревьями. Видимо призывается Zlobober или кто-то из Казахов, кто мне об этом рассказывал.
.
А я так и не нашел в правилах. Участники видят результаты других?
Нет
А трансляция контеста где-нибудь есть?(Контест с аналогичными задачами)
Из Беларуси один не приехал?
Нет, у него полно посылок.
Судя по тому, что у него уже 12 сабмитов в статистике — приехал...
А как смотреть сабмиты?
UPD Уже нашел.
Жми на имя-фамилию в таблице, будет всплывающее окно с именем, фамилией, фото, статистикой и т.д. Выбираешь нужную тебе задачу в списке справа, жмешь show, внизу этого окошка появится график по этой задаче и статистика по сабмитах.
Его попытки были не зря. Он очень старается!
Просто Фёдор любит экстрим и структуры данных. Еще eps по остальным и зашло бы для первого дня
Просто Федор заставил изрядно понервничать за него двум преданным поклонникам национальной сборной Беларуси, которые смотрели всю трансляцию и не спали всю ночь из-за этого.
P.S: Дайте ему кто-нибудь щелбан от меня за это. Но вообще, молодец, справился с волнением :)
Я тоже не спал из-за этого:) Молодец, конечно! Но надо бы второй день не слить, и лучше бы без нулей по задачам.
А я, находясь в Тайване, проспал первые три часа трансляции >.<
Из Тайваня наблюдать за IOI так же скучно? Уж слишком мало динамичности:(
seland, похоже, немного не то решает... Только что сабмит по rail на 0, по wall до сих пор без посылок.
261 у sivukhin
Немного странно видеть 0 по wall у Alex_2oo8.
При том, что он всегда сдает реализации пострашнее на codechef..:(
Господа! (и дамы)
Допустим, в game я делаю следующим образом: я ранжирую вершины (у вершины, которая впервые встретилась в вопросе раньше, ранг больше, если одновременно встретились, то неважно). Понятно, что с каждым вопросом ранг можно доопределить, причём каждый раз, когда новая вершина получает ранг, он будет ниже всех предыдущих. Далее, для каждой вершины я храню количество уже заданных вопросов про неё и вершины низшего ранга (если для какой-то вершины ранг ещё не определён, то она явно не участвовала ни в каких вопросах). Итак, как только мне задали вопрос, я доопределил ранг, у меня есть 2 вершины различного определённого ранга, от меня ждут ответа. Я беру ту из них, что имеет больший ранг, и отвечаю, что ребро есть ровно в том случае, если все остальные рёбра, соединяющие эту вершину с вершинами низшего ранга, уже были спрошены. Легко видеть, что всё это дело делается за линию.
UPD: пардон, линия количества запросов, то есть, квадрат, я глуп
Внимание, 2 вопроса:
1) Нет ли тут косяков?
Вроде бы, нету: в каждый момент времени, кроме последнего, если неизвестные рёбра окажутся существующими, то как бы мы ни доопределили ранг, каждая вершина окажется соединённой с какой-то вершиной низшего ранга, то есть, граф связен. Если же неизвестные рёбра окажутся несуществующими, то вершина наименьшего имеющегося ранга, для которой есть хоть одно неизвестное ребро, соединяющее её с меньшими рангами, окажется отрезана от меньших вершин, а у всех вершин большего ранга степень в меньшие ранги равна 1, так что граф несвязен. То есть, до последнего момента отгадывающий не сможет определить связность. Тогда вопрос номер
2) Отличаются ли ответы, получаемые этим алгоритмом, от ответов в предложенном в посте решении? Я имею в виду, строится ли в итоге один и тот же граф? Заранее спасибо.
Похожее решение рассказывали на live stream, только там пошли еще дальше — вершинам заранее раздали ранги в порядке их номеров, и при обработке запросов просто считали для каждой вершины, сколько еще осталось ребер в нее из вершин с меньшим номером. Как было сказано, это решение предложил один из тестеров, авторы его изначально не увидели. В трансляции это решение довольно точно охарактеризовали как pure magic.
Can we submit the problems anywhere ???
Думаю, Scott Wu возьмет 600 баллов.
Похоже, что нижние границы баллов для золота/серебра/бронзы будут близкими к прошлогодним: 480/360/220.
А как писать белым шрифтом?
Уот так уот
Обсуждения по сути форум, тут работает "font". для примера: <фонт колор="блек"></фонт>
спасибо
Разбор задачи Game :
Что такое инвариант ???