Size: a a a

2016 May 19
Leonid Volkov
Если кому интересно, тексты задач опубликованы здесь:
https://icpc.baylor.edu/worldfinals/problems/icpc2016.pdf

Для понимания того, насколько уровень ушел вперед.
Вот я занимался спортивным программированием очень плотно в 1997-2001 годах как участник, и еще потом 3-4 года как тренер и организатор; придумывал десятки задач, выигрывал немало соревнований.

И вот я сейчас смотрю на эти задачи, и что я вам хочу сказать. Понять условия я могу у всех (ура!); общую идею решения — у 4-5, не больше. Вот прямо так сесть и написать программу, которая решает задачу — наверное, только по двум задачам могу, и потрачу на это все пять часов.

А нынешние команды щелкают все это со скоростью 5 задач в час. Почему так? Потому что спорт высоких достижений. Чтобы быть в топе, когда в мире в этом участвовало 10 тысяч человек, мы делали две полноценных пятичасовых тренировки в неделю; когда же в мире в этом участвует 500 тысяч человек (и призы растут, и интерес ИТ-компаний к чемпионам растет), лучшие команды проводят, наверное, по 4-5 тренировок в неделю, плюс ездят на специальные сборы 3-4 раза в год, плюс участвуют в куче индивидуальных соревнований (которых раньше просто не существовало) и т.д.
источник
Leonid Volkov
А официальное табло результатов в реальном времени вот: https://icpc.baylor.edu/scoreboard/

Сейчас (1 час 50 минут после старта) у пяти команд по шесть решенных задач: СПбГУ, СПбИТМО, Токио, Шанхай, Гарвард. Быстро меняется ситуация в верхах, но лидер стабильно удерживает свою позицию — и очень хороший запас по штрафному времени, примерно сто минут. То есть при равенстве решенных задач питерцы всегда будут первыми.

Ну и сбылся мой прогноз: действующие чемпионы мира из СПбИТМО вышли в лидирующую группу, идут на втором месте.

Однако надо понимать: "действующие чемпионы" — это про вуз, не про команду. Есть важное ограничение: один и тот же участник не может участвовать в финале чемпионата мира более двух раз, так обеспечивается ротация и смена поколений. В прошлом году команду СПбИТМО к победе привел гениальный Геннадий Короткевич (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D0%BE%D1%82%D0%BA%D0%B5%D0%B2%D0%B8%D1%87,_%D0%93%D0%B5%D0%BD%D0%BD%D0%B0%D0%B4%D0%B8%D0%B9_%D0%92%D0%BB%D0%B0%D0%B4%D0%B8%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B8%D1%87), самый титулованный спортивный программист в мире, лидер в большинстве индивидуальных рейтингов спортивных программистов — однако, это был уже второй его чемпионский титул и Геннадий, хоть и остается студентом, больше не имеет права участвовать.
источник
Leonid Volkov
После двух часов игры команда Уральского университета — на восьмом месте с пятью задачами. Не ладится с относительно простой задачей G, уже две неудачные попытки. Но шансы на борьбу за самые высокие места еще не утрачены.

Почему особое внимание к уральской команде? Ну, во-первых, конечно, потому что я сам в ней играл, ее тренировал и всегда за нее болел. Но есть и второй фактор: именно эта команда выиграла прошлой осенью полуфинальный отборочный турнир в Санкт-Петербурге, опередив и СПбГУ, и СПбИТМО, и МГУ, и Саратов, и Нижний Новгород, причем выиграла весьма убедительно.

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

Впервые в финал нам удалось пробиться в 1999 году (Клепинин-Коган-Шамгунов), в 2001 году в Ванкувере мы завоевали бронзовые медали (Шамгунов-Петров-Волков), а начиная с 2004 года и до 2014 года команда Уральского университета 11 раз подряд участвовала в финале, неоднократно занимая места в первой двадцатке. Тут важна стабильность и преемственность: из-за правила "не более двух раз в финале для одного и того же студента", часты взлеты и падения: отучился какой-то яркий студент, и команда, которая всех громила, больше не показывает никаких серьезных результатов. А наши 11 финалов подряд показывали, что удалось добиться создания именно школы спортивного программирования, постоянно воспроизводящей высокие результаты с разными студентами из года в год. Ни один другой региональный вуз в России и близко не подходил к такому результату, как 11 финалов подряд — только МГУ, СПбГУ и СПбИТМО это удавалось.

В 2015 году впервые с 2003 года наша команда не пробилась в финал: была болезненная смена поколений. Были вложены все силы тренеров, организаторов и самих студентов в подготовку новой сильной команды, и вот в этом цикле нам не просто удалось вернуться в финал, а удалось — впервые — с первого места в полуфинале, в статусе фаворитов. Очень надеюсь, что эта ноша не окажется для ребят слишком тяжелой.
источник
Leonid Volkov
источник
Leonid Volkov
Половина соревнования позади, на манеже стабильно все те же.
Сейчас пойдет помедленнее, все легкие задачи,  как и все задачи средней тяжести, уже решены — остались трудные и "гробы" (организаторы традиционно пытаются дать хотя бы одну задачу, которую никто не сможет решить, или, идеально, которую сможет решит только чемпион). При этом команды, когда писали легкие задачи, безусловно успевали подумать и над трудными, у всех есть какие-то заделы и наработки, которые теперь надо превращать в решения — на это есть еще два с половиной часа.

Продолжает лидировать СПбГУ, без запаса по задачам но с неплохим заделом по времени; ни одного сюрприза в группе лидеров, пожалуй что, нет.
источник
Leonid Volkov
Восемь задач из 13 решены хотя бы одной из команд, но из оставшихся пяти только на две были хотя бы попытки решения (все неудачные), а на три задачи —  H, I, J — даже ни одной попытки пока не было.

Прочитал их. Ну, что вам сказать: условия я понимаю, и понимаю, почему H очень сложная (точнее, крайне муторная), а про I и J не вполне понимаю. Хорошие задачи: по формулировке кажутся совсем нетрудными, но придумать хотя бы общую идею решения с наскока не получается.
источник
Leonid Volkov
Только это написал, как прочитал в твиттере у Петра Митричева идею решения J, и теперь хочу биться головой об стол прямо в зале судебного заседания (благо, судья ушла выносить определение по нашему ходатайству) — настолько все просто. Ну то есть идея простая. Реализация очень трудная и муторная, поэтому, вероятно, команды откладывали задачу J на потом.

Это тоже вопрос тактики: если у тебя есть две задачи, простая и сложная в реализации, тебе важно выбрать и первой сдать простую. Например, сдаешь одну на 10-й минуте, вторую на 60-й, получаешь 70 минут штрафа. А если начал сначала писать сложную, сдал ее на 50-й минуте, а потом более простую на 60-й — у тебя 110 минут штрафа, при том же количестве решенных задач.

Поэтому, скажем, геометрические задачи (которые часто бывают не очень трудными, но требующими длинного программного кода) многие команды интуитивно и даже не вдаваясь в детали откладывают "на потом" при первом прочтении комплекта задач.
источник
Leonid Volkov
Токио и Шанхай первыми сделали все 8 относительно простых задач и лидируют "ноздря в ноздрю": разница в 5 минут штрафного времени — это как сотые доли секунды. Скоро восьмую сдаст и СПбГУ и вернется на свое первое место, благодаря хорошему запасу по штрафному времени.
В лидирующей группе (7 задач) также MIT, СПбИТМО, Гарвард, Нижний Новгород, МФТИ. В группе с шестью задачами — Варшава, МГУ и УрФУ (ребята набрали тонну штрафа на задаче G, но все же продрались через нее с пятой попытки).
Команды, у которых сейчас 5 задач и менее, уже точно не примут участие в борьбе за медали.
Начинается самая интересная часть соревнования: "обязательный норматив" лидерами сдан, теперь каждая из лидирующих команд выберет 2-3 задачи из последних 5, которые будут стараться довести до ума в последние два часа. От того, насколько правильно будут сделаны эти ставки, насколько верно оценена трудность задач, и будет зависеть итоговый результат.
источник
Leonid Volkov
источник
Leonid Volkov
Интересные вещи происходят!
У обеих питерских команд (между прочим, последние четыре (!) чемпионских титула принадлежат им — СПбИТМО чемпионы мира 2012, 2013 и 2015 годов, СПбГУ — 2014 года) что-то не ладится с задачей А, последней из "относительно несложных".
(Впрочем, в твиттере Петр Митричев говорит о том, что пока не вполне понимает, как ее решать).
Зато MIT и Гарвард присоединились к Токио и Шанхаю в группе решивших 8 задач, и теперь MIT лидирует благодаря наименьшему количеству неудачных попыток.
Но главное: команда Уральского университета, разобравшись с затыком в задаче G, в течение десяти минут после этого сдала еще две, и тоже присоединилась к лидирующей группе, пусть и с большим отставанием по времени. Молодцы!
источник
Leonid Volkov
Михаил Рубинчик, тренер уральской команды, пишет мне из зала соревнований:

"Задачу J пишут пара команд
Шанхай и Токио
но вяло пишут
Остальные с 8-ю пока обсуждают что-то
у наших Олег что-то рассказывает по J, но там вроде не решение, а пока только какие-то идеи"

То есть действительно все команды сейчас застопорились и думают, что делать дальше. Тренерам хорошо видно, что команды делает — кто сидит и быстро что-то вбивает, кто совещается, кто в прострации, кто нервно жует какие-нибудь мюсли-батончики.
У каждой команды своя стратегия для таких ситуаций; есть разные модели работы. Где-то есть явно выделенные "математики", которые мало программируют сами, но умеют раскалывать самые сложные задачи; где-то все участники команды универсальны и взаимозаменяемы.
источник
Leonid Volkov
Осталось полтора часа.
Действующие чемпионы мира из СПбИТМО первыми сдают первую из "сложных" задач — задачу F — и впервые за соревнование выходят на чистое первое место (а я предупреждал!).
В группе преследования, сдавшей "квалификационный минимум" из восьми относительно простых задач еще 9 команд: для всех них соревнование, как я уже писал, по сути сейчас начинается заново
источник
Leonid Volkov
Тут что важно понимать: я так пишу про "квалификационный минимум" и "относительно простые 8 задач", но это все действительно очень относительно.

Это финал чемпионата мира: 128 лучших команд, продравшихся через многоступенчатый отбор. Все они очень крутые. И те задачи, которые "относительно просты" для них, вовсе не просты для всех остальных.

И даже для финалистов: может не заладиться день, может болеть голова, можно чего-то не додумать, можно заглючить на простой задаче, можно неверно распределить силы.

Мы с вами обсуждаем лидеров, а ведь из 128 команд-финалистов по состоянию на сейчас лишь 43 решили 5 и более задач — а у двух третей финалистов четыре задачи и меньше (у лидеров, напомню, 8-9 за то же время!). И не сказать, что это слабые команды: Стенфорд, МИФИ, Беркли в районе 40-го места с 5 задачами, там же очень сильный Белорусский госуниверситет; у Пекина 4 задачи, у знаменитого Карнеги Меллона - 3 задачи и 88 место.

Это реально спорт, достаточно жестокий; статус фаворита сам по себе ничего не дает. Важен настрой на конкретное соревнование, фарт, спортивная форма.
источник
Leonid Volkov
источник
Leonid Volkov
Уральцы сдают вторыми задачу F и выходят на второе место! Ура!
И сейчас в тройке лидеров только российские команды.
источник
Leonid Volkov
Осталось чуть больше часа.
Из пяти "трудных" задач, только задача H остается задачей, которую никто не пытался сдать.
Все остальные пытались: Урал, ИТМО и Гарвард сдали F, СПбГУ сдал J, а Шанхай сдал M.
Теоретически это значит, что положение СПбГУ и Шанхая в группе лидеров самое устойчивое — относительно более простая F у них "в запасе". По штрафному времени все пять лидеров очень близки.
источник
Leonid Volkov
А теперь самое важное (и грустное): по давней традиции и по правилам соревнования, таблица результатов за час до конца замораживается. И не будет обновляться.
Чтобы "сохранить интригу до награждения". Интрига сохраняется, но для спортивности это, как мне кажется, большой минус.
Шарики тоже носить не будут. Поэтому о происходящем в последний час предстоит догадываться лишь по косвенным признакам: мы будем видеть, какие решения команды направляют на проверку, а пара тренеров обещали писать мне об эмоциях, которые они смогут со своих мест на лицах членов команд. (Естественно, в ходе соревнования команды изолированы от внешнего мира, не общаются с тренерами, не имеют доступа в интернет. Зато вердикты жюри им будут приходить — в том числе и в последний час)
источник
Leonid Volkov
источник
Leonid Volkov
Замороженный монитор выглядит так: фиолетовым цветом отмечены попытки, вердикт по которым нам не покажут. Причем отдельно количество попыток до заморозки и после.
Другими словами, у команды не может быть решено задач больше, чем зеленых плюс фиолетовых. И если, например, у уральцев фиолетовых нет вообще, значит они точно остаются с девятью задачами пока.
И напротив, шанхайцы имеют фиолетовые отметки уже по двум задачам: весьма вероятно, что они уже сдали десятую и теперь двигают и доводят одиннадцатую.
источник
Leonid Volkov
Лидеры — СПбГУ — довольно давно сделали первую "фиолетовую" попытку по задаче М, потом было долгое молчание, и вот фиолетовая попытка по задаче F. С очень большой вероятностью это означает, что задача M ими сдана.
Иначе бы они делали бы еще попытки по ней, не разбрасывали бы силы в последние 20 минут на несколько задач в их турнирной позиции.
Благодаря малому штрафному времени, сданная с первой попытки десяткая задача практически гарантирует питерцам победу — чтобы их обойти, кому-то надо будет сдать одиннадцать.
источник