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

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

Меня попросили не выкладывать условие, пока не будет официальной версии на сайте олимпиады, но обещали сделать ее существенно быстрее, чем на первом туре. Увидим.

Для тех кто не следил за первым туром напоминаю: есть 6 полных баллов, 1 261, и 19 256. Количество золотых медалей — то ли 26, то ли 27. То есть борьба за них будет достаточно суровой.

0:00 Ух ты. И правда быстро выложили.
0:05 Пока ничего не произошло. Я пока пишу какие-то мысли про задачи.
0:12 Еще какое-то количество 10 и 20 по гондолам.
0:17 По гондолам появились 25. Кажется это уже не только первая из трех задач, которые там есть. Впрочем, кажется что две из трех тривиальны совсем.
0:26 zemen 20 по гондолам. emachaidze 23 по holidays. Видимо это разбор случая, когда начало в нуле. Или что-то большее с багами (например забытый long long).
0:27 fabik 27 по friends. Это кажется разбор частных случаев.
0:29 Po-En Chen 55 по гондолам. -imc- 10. Это выглядит как 20 с багами на самом деле.
0:30 KAN 20 по гондолам. А -imc- еще 10. Бывает.
0:33 HYPERHYPERHYPERCUBELOVER 75 по гондолам. Когда же будут 100? 0:34 Miras321 55 по гондолам. А у -imc- еще 10 :(
0:35 zemen 55 по гондолам. scott_wu 35 по друзьям. Это вроде бы тоже разбор случаев.
0:37 С четвертой попытки у -imc- все-таки 20 по гондолам. Интересно, что это было.
0:38 Po-En Chen 90 по гондолам.
0:40 Добил до 100. В целом, эту задачу все должны добить. Вопрос в том, сколько времени на это уйдет. У zemen вот уже 75.
0:42 AstroConjecture выходит на первое место в 55 по гондолам. KAN 75.
0:44 Появилось несколько 47 по holiday. Это разбор частных случаев + перебор. На самом деле первые 5 подгрупп в ней имеют мало отношения к полному решению.
0:45 Miras321 100 по гондолам. zemen 90. Если цель этой задачи была скушать время, она с ней справляется.
0:47 sivukhin 15 по гондолам. O_o это как? 0:50 KAN 100 по гондолам. Теперь ему придется думать.
0:51 Algiz 47 по holiday. Таких уже достаточно много. Это все кроме собственно задачи.
0:52 dhh1995 выходит на первое место с сотней по гондолам. У -imc- 55. У zemen еще 90.
0:55 zemen 100 по гондолам. Ждем Никит. Кстати, если кому интересно, автор этого треша — misof.
1:00 Xu и Yu закрыли гондолы и теперь три китайца делят первое место с 400. К KAN присоединилось еще два человека с 356.
1:03 -imc- 75 по гондолам. Кстати о Китайцах. Кажется ребята говорили, что после первого тура, команда США учила команду Китая традиционной китайской карточной игре.
1:05 sivukhin 10 по гондолам?! Как-то они не пошли.
1:07 zemen разобрал один из частных случаев в друзьях и вышел на первое место по туру со 119.
1:08 sivukhin 25 по гондолам. А zemen разобрал еще 2 частных случая. Можно еще написать перебор, паросочетание в двудольном графе (это будет 69 кажется) и начать решать задачи.
1:09 scott_wu решил, что ему не нравятся гондолы и сдал друзей на 100. В целом, это тоже не очень сложно. У -imc- еще одно 75.
1:12 А у sivukhin еще 25.
1:14 scott_wu начал заниматься гондолами. 10 это не самое хорошее начало.
1:15 На самом деле, происходящее сейчас имеет не очень много смысла. Я верю, что большая часть участников претендующих на золото получит 100+46+47. Дальше будет не очень большая группа которая из 46 сделает 69. А на оставшихся двух подзадачах все будет решаться. Впрочем, иметь на них 3,5 часа приятнее чем 2.
1:17 А у -imc- еще одно 75.
1:19 scott_wu вышел на первое место по туру с 40 по гондолам и 100 по друзьям. А у sivukhin еще 25.
1:21 уже 65. Минут через 15 наверное будет 100. Дальше 47 вообще не проблема. А вот дальше...
1:22 И еще 25 от sivukhin. Сколько можно :(
1:23 KAN 0 по друзьям. Вероятно это 100 с багами. Или неправильное решение. Во всяком случае, на вид в частичных ошибаться негде.
1:27 Miras321 пошел набирать частные случае в друзьях.
1:32 Po-En Chen выходит на 2-ое место с 200 за второй тур!
1:33 scott_wu присоединился к 200 за второй тур. 47 думаю будет быстро. Вопрос придумает ли оставшуюся подзадачу.
1:35 -imc- додолбал гондолы. Остался sivukhin. Как-то у него не пошло совсем.
1:38 Американцы первые все сдали гондолы.
1:43 sivukhin отложил гондолы и получил 46 по друзьям. Сменить деятельность иногда помогает в таких случаях.
1:48 У KAN еще один 0 по друзьям. Кажется самое время получить 11 и стресс-тест.
1:50 ecnerwala кажется первый написал паросочетание в friends. Кажется получить 100 это не поможет.
1:51 А у KAN еще один 0.
2:00 Спустя два часа отсечки медалей 350-245-139. Думаю к концу отсечкой золота будет примерно 449.
2:01 Baklazan третьим получил 200 за второй тур.
2:11 Как-то все наши затихли. Опять до конца третьего часа?
2:13 Кстати scott_wu тоже не спешит получить 47. А вот Po-En Chen уже набрал 24
2:15 KAN прошел только третий subtask в holiday. Это как интересно? Мне казалось они вкладывают тесты, а первая подгруппа подмножество. Ладно, похоже на мелкие баги, скоро поправит.
2:17 Miras321 сдал паросочетание в friends.
2:21 Ух ты. Там 4 по 100 по holiday. Или эти ребята очень суровы, или тесты отстой. Я боюсь, что все-таки второе. В таком случае вероятно 300 будет. В том числе 100 есть у svanidz1
2:29 zemen тоже разобрал двудольный граф в друзьях.
2:31 У KAN 24 по holiday. Забавно, я не умею решать третью не решив вместе с ней вторую, хотя формально по ограничениям они не вложены.
2:33 Еще одна сотня по holiday. Видя монитор, все бы понеслись пихать. А так...
2:38 Кажется отвалился scoreboard. Надеюсь, это единственное, что сломалось.
2:45 Судя по таблице, первый тур потерялся, а второй перетестируют :)
2:46 Ну вот, теперь ничего не понятно. Интересно, а там откуда я выкачиваю список сабмитов тоже треш?
2:49 Кажется все починили. За этого время случилось 550. От наших вроде ничего.
2:54 А, нет. От Кости еще 56 по друзьям, от sivukhin 24 по holiday и 35 по гондолам. Пока я писал 24 превратились в 47. А -imc- уснул?
2:58 sivukhin 55 по гондолам. Скорее всего 100 по ним ему на золото уже хватит, хотя и впритык. Лучше бы что-то еще.
3:00 Тем временем -imc- вылетел из серебра. Интересно, что он делает последние 1.5 часа.
3:03 И у нас есть первый total! Поздравляем scott_wu. А в тесты в holiday я все-таки не верю.
3:05 Все-таки с табличкой что-то не то. После Ctrl+F5 total исчез.
3:07 О. Вернулось. Ну ладно. Ерунда какая-то. А от наших все ничего.
3:09 KAN подтвердил предположение, что тесты полный отстой. Все подзадачи, кроме второй. Думаю ее он сейчас просто заглушит.
3:20 Надеюсь тестирующей системе не так плохо, как табличке.
3:21 Кажется табличка не обновляется с 3:08
3:29 В json с сабмитами мне пришло 100 от KAN по holiday. Надеюсь, он разберется что у него там с друзьями.
3:31 Еще пришло 19 по friends от KAN и 47 по holyday от -imc-. Ну наконец-то.
3:32 sivukhin получил 60 по гондолам. Надеюсь скоро добьет.
3:34 Alex_2oo8 со своим очень странным первым днем поднялся в золото с 247 за второй.
3:36 Кажется табличка сейчас адекватна.
3:40 От sivukhin еще одно 60 по гондолам.
3:42 От KAN еще одно 19. Возможно он решил, что золото уже есть, поэтому или 100 или в принципе не важно.
3:44 Я боюсь, что Костя может писать какую-нибудь жесть в holidays. Это может плохо кончится на самом деле. А главное, без сданной friend не поможет.
3:48 И еще одни 60. Интересно, что там не так. 3:52 От Коли 0 по friend. Видимо у него неправильное решение. Ну задача же прекрасно стрессится, почему он этого давно не сделал?
3:53 30 по friends. Прошел первую позадачу. Может наконец-то написал перебор? Или опять слабые тесты?
3:56 sivukhin добил гондолы! Похоже, на второе золото. Хотя для безопасности неплохо бы добить еще одну. Ну или хотя бы 69 по friends.
3:58 KAN прошел другие две группы в friends. Интересно, что более кривое, его решение или тесты жюри?
4:01 zemen еще одно 58 по friends. Он серьезно? Ему 0 по последней могут еще простить. draconic не простят.
4:03 Тем временем KAN посылает какой-то треш по друзьям. И появилось еще одно 600.
4:04 О, zemen 69 по друзьям. Этого даже наверное хватит на серебро. Но, блин, что за 0?
4:10 Как-то я совсем не понимаю, что делает -imc-. Это печально. До бронзы ему осталось два места.
4:13 Кажется KAN так и не написал перебор. А делает какой-то треш. Видимо правда сейчас он склеит из него 46. Потому что решения проходящие каждую из подзадач у него уже есть.
4:17 Я считал, что тому, что нули это плохо учат сильно раньше. А у sivukhin 23 по holiday. К чему бы это. 4:19 Сдал на 19. Ну слава богу. И zemen на 24. Ну так хоть не так нецензурно. 4:23 Кажется, если не произойдет каких-то чудес, должно быть два золота и два серебра.
4:26 KAN 300! А -imc- сдал на 46 друзей.
4:32 zemen 47 по holidays. Границы на текущий момент 447-330-209.
4:37 Кажется таблице опять плохо.
4:43 Еще 300. Китаец.
4:45 Как бы sivukhin не вылетел из золота. У него 5 мест запаса. Лишние 2 балла в первый день могут сыграть. 4:49 Пойду встречать ребят. Думаю, сейчас уже мало интересного произойдет. 4:59 Кажется ничего не случилось. 5:00 OVER. В целом сегодня ребята молодцы. Ниже не опустились. Чтобы Косте с Никитой подняться в золото им нужно было 300. Не делать это странно называть плохо выступили.

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

gondola Условие en
Достаточно простая но мутроная задача. Точнее даже три задачи. Разбор на GA выглядел как "Первые две подзадачи тривиальны, в третьей нужно немного комбинаторики". Пожалуй, я не пойду дальше
friend Условие en
Введем для человека стоимость за то, чтобы его не взять. Тогда людей можно удалять с конца пересчитывая эти стоимости. Стоимость будет меняться только для человека, который позвал. Как меняется достаточно несложно разбирается для всех трех способов.
holidayУсловие en
Это выглядит как жесть. Какие-то мысли. Если зафиксируем отрезок, то ответ на нем — это сумма нескольких максимальных. Это можно считать какой-нибудь двумерной структурой, или персистентным деревом. Кто-то из казахов рассказывал мне, как довести это до nlogn запросов к такой структуре, но я если честно не готов был это ни аккуратно проверить ночью, ни воспроизвести сейчас. Жюри обещает какой-то красивый devide-and-conqure.

Комментарий. Тур выглядит в целом сложнее первого. Для наших ребят это скорее хорошо. Если придумать holiday на 100, это может помочь неплохо отыграться.