В ноябре программисты Ижевского государственного технического университета заняли второе место в четвертьфинале чемпионата мира по программированию среди студенческих команд ACM ICPC.  С очередным "разбором полетов" - эксперт сайта Елена Шевякова.

Как известно, 1 ноября для программистов Ижевского государственного технического университета стартовал очередной цикл соревнований в рамках чемпионата мира среди студенческих команд ACM ICPC. Две команды ИжГТУ приняли участие в четвертьфинальном этапе (восточный подрегион северо-восточный регион NEERC).  Одна из них - Izhevsk STU Imba (Виктор Камашев, Евгений Кузяков, Антон Чудиновских) заняла по итогам турнира 2-е место и получила путевку на полуфинал нашего региона, который состоится в С-Петербурге 26 ноября.

Мы попросили прокомментировать итоги этого этапа одного из лучших программистов нашего университета - Александра Скиданова, который не понаслышке знает многие аспекты спортивного программирования - он двукратный медалист Чемпионатов мира ACM ICPC, участник финалов по системе TopCoder Open и Google Code Jam. Кроме того, Александр принял участие в online-туре на задачах восточного подрегиона четвертьфинала (тур проходил параллельно с основными соревнованиями), поэтому его оценка по некоторым вопросам может показаться довольно интересной.

Оценка задач четвертьфинала

По мнению А. Скиданова, среди предложенных 11 задач 2 были "поощрительными" - т.е. совсем простыми и их решили практически все. На другом полюсе сложности - задача "А", которую участникам четвертьфинала решить не удалось, а вот победителю online-тура (китайцу LouTianChen, программисту с очень высоким личным мировым рейтингом) эта задача оказалась по силам. Александр характеризует задачу как "большой перебор с оптимизацией".

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

Одна из задач оказалась "спонсорской". Дело в том, что кроме постоянного спонсора четвертьфинала в Екатеринбурге (СКБ "Контур") в этом году была еще одна компания, выпускающая игрушки-головоломки. Вот одну из них - змейку из маленьких кубиков 1х1, из которых можно получить кубик 3х3, получили все команды за 2 дня до начала соревнований. Наш Е. Кузяков сказал при этом своим товарищам, что на турнире обязательно будет задача по этой игрушке. И не ошибся.

Особый разговор о задаче "D". На четвертьфинале кроме нашей команды эту задачу сдали только победители - команда Ural SU Fusion (Даниил Айзенштейн, Алексей Самсонов, Игорь Чевдарь). На online-туре задача тоже была решена единицами. Наш А. Скиданов задачу не решил потому, что не понял условия. Как показали обсуждения после окончания турнира, не понял не только он один. Условие нашли некорректным несколько команд, более того, нашлись специалисты, которые предоставили в оргкомитет тесты, на которых засчитанные системой решения как правильные, "падали". В результате принятые решения участникам online-тура были аннулированы,  а участникам четвертьфинала - оставлены (в соответствии с правилами ACM ICPC принятое в ходе турнира решение отмене не подлежит ни при каких условиях, хотя обратное - принятие незасчитанного ранее решения по результатам апелляции возможно. Как говорят при этом сами программисты, "+" на "-" не меняется). Поэтому в итоговом протоколе четвертьфинала ничего не изменилось, а вот итоговый протокол online-тура изменился, в частности, А. Скиданов с 6-й позиции переместился на 5-ю и решил в точности те же задачи, что и наша команда в Екатеринбурге, если не считать задачу "D".

Оценка итогов

По мнению Александра, победа на четвертьфинале команды Ural SU Fusion (Уральский государственный университет) была ожидаемой. В копилке этой команды участие в финале Чемпионата мира-2008, один из членов команды - Алексей Самсонов - имеет высокий личный рейтинг в мире и неоднократно был финалистом турниров TopCoder Open.

Второй год подряд сильно выступает на четвертьфинале команда из Челябинска South Ural SU 1: Александр Бич, Олег Василенко, Павел Майоров (Южно-Уральский государственный университет). Эта команда знакома нам и по победе в последнем семинаре-олимпиаде, недавно завершившимся в нашем университете. Правда, в прошлом году ребятам не удалось хорошо выступить на полуфинале, но в этом году у них появилась еще одна хорошая возможность отличиться.

Всего от подрегиона в полуфинал Северо-Восточного Европейского региона согласно квоте вышло 12 команд, причем места в этом году распределились таким образом, что  Уральский государственный университет использовал максимальную квоту представительства в полуфинале - три места (Ural SU Fusion, Ural SU Pensioners, Ural SU Coding Spirits). Часть команд с 5-ю задачами попала в полуфинал, а вот еще 2 команды, решившие тоже по 5 задач - Ural SU Team.GOV (Уральский государственный университет) и  Ural STU Frogs (Уральский государственный технический университет УПИ) по основной квоте не попали. Похожая ситуация возникла на финале-2006, когда занявшая 13-е место команда Петрозаводска оказалась единственной, решившей столько же задач, как и бронзовые медалисты, но осталась за чертой призеров. Тогда обращение команды в оргкомитет было рассмотрено, и по специальному решению организаторов команда была тоже награждена медалями. Вспоминая это, ребята из Ural SU Team.GOV и  Ural STU Frogs тоже отправили организаторам письмо с просьбой выделить им дополнительную квоту для участия в полуфинале. В итоге наш подрегион получил два дополнительных места и будет представлен 14 командами:

Об итогах четвертьфинала в других подрегионах

Помимо Екатеринбурга, отборочные соревнования прошли в Центральном (Рыбинск), Южном (Саратов), Западном (Минск), Киргизском (Бишкек), Московском (Москва), Восточно-Сибирском (Красноярск), Западно-Сибирском (Новосибирск), Грузинском (Тбилиси), Казахстанском (Алматы), Северном (С-Петербург), Узбекском (Ташкент), Дальневосточном (Владивосток), Армянском (Ереван) подрегионах NEERC. Задачи на этих турнирах обычно не дублируются, а определяются организаторами конкретного четвертьфинала. Это обстоятельство приводит иногда к некоторым неожиданным последствиям. В этом году, например, возникли такие диаметрально противоположные ситуации, как выход в полуфинал с 2-мя задачами (Саратов) с одной стороны, и досрочное решение всех 11-и задач (С-Петербург) - с другой. В связи с этим среди специалистов и поклонников спортивного программирования завязалась довольно оживленная дискуссия на форуме.

По мнению нашего эксперта А. Скиданова, в четвертьфинале обычно 2-3 команды экстра-класса, половина - среднего уровня и остальные - откровенно слабые. Поэтому если задачи будут преимущественно сложные (как, вероятно, получилось в Саратове), то это приведет к борьбе за 1-3 места, что вообще-то не принципиально. А вот для команд среднего уровня объективной картины получить не удастся. С другой стороны, при сравнительно слабых задачах может возникнуть резкая потребность в дополнительной квоте представительства на полуфинале (по типу уже описанного прецедента в нашем подрегионе). Поэтому, как правило, турнир проводится на "средних" задачах, к которым добавляют для подстраховки 1-2 сложных. Правда, судя по результатам в С-Петербурге, или сложных задач организаторы не предусмотрели, или подготовка питерских команд в этом году такая высокая, что сразу 5 команд закончили соревнование досрочно. Окончательно ответ на этот вопрос нам даст только полуфинал.

О нашей команде

Александр Скиданов вполне оптимистично оценивает перспективы нашей команды в этом сезоне. На сегодняшний день ее результаты практически полностью повторяют график прошлого сезона (14-е место на летних сборах в  Петрозаводске, 2-е - на  четвертьфинале). Новый член команды (А. Чудиновских) по имеющейся информации уже "работает". Правда, Александра несколько удивляет то обстоятельство, что число штрафов на четвертьфинале оказалось достаточно большим. Во-первых, это всегда опасно, а во-вторых, еще летом команда заявила, что проводит турнир по новой стратегии - если на какой-то задаче допущен штраф, то задачу "не добивают", а переходят к решению другой. Летом эта стратегия оправдала себя, а вот на четвертьфинале есть задачи, сданные даже с 4 штрафами. Что это: изменение стратегии или вынужденный шаг - А. Скиданов пока комментировать не берется.

Заключение

Такой вот оказался взгляд на итоги четвертьфинала ACM ICPC нашего программиста и эксперта Александра Скиданова, который буквально "корнями пророс" в спортивное программирование, хотя еще полгода назад, после финала в Канаде, считал, что наконец-то забудет и про тренировки, и про соревнования. Не получилось. Но он об этом не жалеет.