8:15 По текущим данным, тур отложен на 45 минут. На улице прошел дождик. Сейчас он вроде почти кончился, но тем кто сегодня поедет на пляж будет весело.

8:25 Ничего не происходит, никто не рассказывает о причинах задержки. В общем, удачи научному комитету не знаю с чем. В любом случае, она им сегодня понадобится не меньше, чем участникам.

8:42 Трансляция. Кстати у них пока не работает сервер с табличкой, и еще некоторые другие. Может быть это причины задержки? Зато солнце выглянуло...

8:50 Интернет работает как-то совсем печально. Или это все смотрят трансляцию.

8:51 Следующее заявленное время начала — 9, т.е с задержкой в час.

8:57 Участников пустили в зал. Тем временем один из ISC Member опроверг мои самые страшные мысли о причинах задержки. Это радует, но детали после начала контеста.

9:03 Если я правильно понял, то в зал забежал опоссум. Ну ок.. Тем временем ко мне присоединился eduardische

Контест начался.

0:14 Контест предположительно начался в 9:15. Уже есть 25 и 12 по первой, но они совсем не о чем, я не думаю, что много топа будет их писать. Условия будут, когда я поборюсь с интернетом. Scoreboard

0:29 Поборолся. русское английское Тем временем есть три сотни по первой задаче и одна по второй. Похоже, что все будет решаться на третьей.

0:37 Быстро появилось достаточно много сотен по первой. Впрочем, она действительно простая. Во второй есть правдоподобная жадность, которая оказывается верной. Вполне вероятно, что большинство участников просто не будет ее доказывать. Наши пока себя не показали никак. Видимо читают условия. Так тоже можно.

0:46 От KAN и tunyash 100 по caves. От malcolm 51. Только пока я это писал, случился rejudge.

0:50 100 по caves от zemen. А у остальных не сложилось. И опять никто не говорит что происходит.

0:58 У наших три сотни и 51 от malcolm. У YuukaKazami 200. Впрочем, резервные задачи по словам жюри еще проще.

1:00 KAN присоединился к YuukaKazami Одним словом надо решать game на сотню. game — это абсолютно стандартная, но достаточно сложная задача. Основная проблема с ней в том, что вчера на GA meeting выяснилось, что в ней заходит тупняк. Поэтому срочно пришлось повышать ограничения, и это делали ночью. Кроме того, для усложнения, в задаче поставили достаточно жесткий ML, который является основной проблемой для последних 20 баллов, по замыслу жюри. Собственно про проблемы с этой задачей я писал, когда говорил про худшие мысли о причинах с задержкой.

1:08 К KAN и YuukaKazami присоединились scott_wu и t0nyukuk. Остается вопрос, кто из них умеет писать двумерные динамические структуры данных. В KAN я уверен, вопрос в том, сколько времени это займет.

1:12 Уточнение: у scott_wu 210. Но понятно, что это делается за совсем моментально. Тем временем у malcolm 76 по cave. Мы с eduardische получать такой score, кроме как специально попортив 100 не умеем.

1:22 У KAN 10 по game. У tunyash 39 по robots. Я думаю это первый и третий subtask. Значит скорее всего у него есть правильная жадность, в которую надо добавить какую-нибудь структуру.

1:30 У malcolm 14 баллов по robots. Это похоже на вторую подгруппу, которая является частным случаем, и не является большим продвижением к решению.

1:33 А теперь у malcolm 76. Это похоже либо на безумный набор подгрупп из-за багов и слабых тестов. Либо на правильное решение с TL, написанное аккуратнее, чем у tunyash.

1:39 У zemen 14, у tunyash 53. Видимо Артур отдельно разобрал вторую подзадачу. Тем временем у Украинцев контест не задался — единственная 100 на команду сave у fedimser. У vlad107 200, у kostya_by 100, у двух других белорусских участников 100 нет.

1:46 У участника из Бразилии(Renato_Ferreira) 0-0-80. Неожиданное начало.

1:50 У zemen 90. Интересно, что бы это могло быть? TL на последней группе, из-за неаккуратной реализации?

2:00 У zemen и tunyash 90 по robots, у malcolm 100. KAN видимо пишет что-то крупное по game. А у меня 7% заряда на ноутбуке :(

2:07. Китаец, выигравший первый тур, закончил издеваться, и за 4 сабмита получил 100 баллов по cave. Этим он себе обеспечил место не хуже 4-го.

-2:20 Осталось меньше половины контеста. Последнее время ничего интересного не произошло. У Украинцев все еще одна сотня на команду. У белорусов дела получше. Три человека вверху серебра.

-2:08 tunyash сдал game на 27. Это кажется просто много одномерных деревьев. Или двумерное с багами?

-2:07 И у нас есть 100 по game от участника из Болгарии (Hristo Venev). Думаю скоро будет 300, но этого недостаточно для того, чтобы обогнать ACMonster.

-1:58 Еще 100 по game от Siarhei Kulik. Правда 46-53 по двум другим. Немного про задачи.

-1:56 tunyash сделал 37 по game. А что такое было 27?

-1:54 А эта табличка оказывается умеет показывать детали посылок.. У KAN за последний час три посылки на 0 по game. У остальных более-менее посылок кроме того, что в таблице нет.

-?:?? А если таблицу увеличить, потом уменьшить, то поедет верстка и часы в частности.

-1:35 У KAN еще 0 по games. Не пора ли написать стресс-тест. Мне два года назад в аналогичной ситуации с elephants помогло.

-1:32 malcolm сдал game на 37. Интересно чего они ждут, прежде чем сделать 37?

-1:30 zemen 63! Правда 63 от 80 отличается практически полностью.

-1:25, а KAN 80 по game!

-1:21 Тем временем Кулик 46-90-100.

-1:07 Тут случился обед, и две посылки по cave от malcolm. У KAN есть еще одно 80.

-1:00 У KAN и zemen уже почти однозначно золото. Двум остальным надо что-то сдавать. От tunyash нет посылок уже час. Видимо он решил писать game, а не получать 10 баллов по robots. У malcolm сабмиты по двум задачам. К чему бы это?

-0:57 YuukaKazami 300! Что ответит другой китаец?

-0:51 80 по третьей от Димы. Интересно, он теперь пойдет ее заталкивать на 100 или подумает над первой?

-0:48 У tunyash сабмит на 10 баллов по games. Ждем в 8 раз больше. А лучше в 10...

-0:45 Интересно, какой сейчас размер очереди тестирования?

-0:38 21 по cave от malcolm. Хм...

-0:28 Две посылки по 51 от malcolm 0 от zemen еще несколько 80 от KAN и уже пол часа ничего от tunyash.

-0:20 Кулик 76. У Артура остался запас в 2 места. Нужно сдавать 63 или 80.

-0:14 Запас кончился. Надо сдавать. А лучше еще и Диме сдавать.

-0:13 Дима 100 по game. И все еще 76 по cave.

-0:09 Есть сабмит от tunyash. 37. Очередь похоже где-то 7-8 минут. То есть вердикты по новым посылкам скорее всего уже не придут.

-0:08 zemen 80 по game!

OVER

Мы пошли к детям. Увидим, что получится.

Решения написаны белым цветом, чтобы желающие могли порешать сами. Оно становится заметным, если его выделить.

caves. В задаче дано N дверей, и N переключателей. Можно 70000 раз сходить устоновить переключали в любое положение, и узнать какая дверь закрыта первой. Надо узнать какой переключатель соответствует какой двери, и какое из двух положений открывает какую дверь.

Решение Будем определять переключатель по двери, начиная с первой. Зафиксируем все предыдущие двери открытыми, после этого можно считать, что их просто нет. Соответствующий переключатель после этого ищется бинарным поиском. Возможно нужно делать это достаточно аккуратно, чтобы уложиться в 70000 на последней подгруппе. Конец решения

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

Решение Я напишу жадность, которую умею строго доказывать. Сделаем бинпоиск по ответу. Отсортируем вещи по убыванию длины. Будем отдавать вещь самому слабому роботу, который сможет ее поднять, у которого еще есть свободное время. Оставшиеся задачи раздадим маленьким роботам. Это делается за NlogN c деревом отрезков. Вроде бы, если развернуть, то будет достаточно сета. Получится жадность вроде отдавать слабым роботам в порядке возрастания силы самые большие игрушки, которые можно. Это делается с сетом. Конец решения

game. Есть поле 10⁹ × 10⁹. Надо отвечать на запросы изменить значение в клетке, и посчитать gcd на прямоугольнике. Изначально везде нули. Решение В задаче русским по белому написано, что надо сделать какую-то двумерную струтуру данных. Например двумерное неявное дерево отрезков, или дерево отрезков декартовых деревьев. В любом случае надо искать баланс между временем и памятью и прочими радостями жизни. Слава богу, у топа время на написание будет предостаточно. Конец решения