Все новости от 28 ноября 2001 г.

Чемпионат по программированию: комментарии тренеров

Всего для участия в полуфинале нынешнего сезона зарегистрировалась 171 команда. Из них 99 команд завоевали это право на соответствующих четвертьфиналах или еще в прошлогоднем сезоне, а 72 — принимали участие в чемпионате по интернету. Сейчас подводятся итоги прошедшего полуфинала, но для большинства команд на питерском этапе нынешний сезон заканчивается: борьбу продолжит только одна команда от каждого из лучших российских вузов.

В преддверии этих полуфинальных соревнований мы попросили прокомментировать итоги двух завершившихся олимпиад (московской и рыбинской) и поделиться планами на предстоящие два этапа чемпионата по программированию (питерский и финальный) тренеров и руководителей ведущих московских команд.

На вопросы ZDNet отвечают:

Александр Чернов, тренер команд механико-математического факультета и факультета вычислительной математики и кибернетики МГУ, член жюри Московской олимпиады по программированию;

Виктор Малышко, руководитель команд факультета вычислительной математики и кибернетики МГУ, член оргкомитета Московской олимпиады по программированию;

Евгений Панкратьев, руководитель и тренер команд механико-математического факультета МГУ, член жюри Московской олимпиады и четвертьфинала ACM ICPC.

Каковы особенности прошедших олимпиад — Московской и четвертьфинала ACM в Рыбинске? Отличались ли задачи по сложности и почему задачу F в Москве решила только одна команда?

Александр Чернов:

Авторам очень трудно оценивать сложность своих задач. Чаще всего они ее сильно занижают. Но задачи Московской олимпиады оказались достаточно удачно подобранными по трудности, хотя в тематике был некоторый перекос в сторону графов. По относительной сложности задач наша Московская олимпиада занимает промежуточное положение между четвертьфиналами и полуфиналом в Санкт-Петербурге. Задачи составляются с учетом примерной оценки силы команд. Обычно на Московской олимпиаде состав сильнее, чем в четвертьфинале (поскольку нет ограничений на присутствие команд Московского государственного университета).

В этом году первые шесть мест в четвертьфинале заняли команды, участвовавшие в Московской олимпиаде. Команда МАИ-1 на Московской олимпиаде была лишь 20-й, а в Рыбинске заняла 6-е место. Поэтому можно утверждать, что комплект задач четвертьфинала был достаточно простым. Уже несколько лет по крайней мере одна команда МГУ решает все задачи, когда до контрольного времени остается еще более часа.

Евгений Панкратьев:

Обе эти олимпиады проводились по правилам ACM, лишь на московской были небольшие отступления. В частности, на олимпиаде в Москве члены команды необязательно представляли один и тот же вуз — были команды, составленные из студентов разных учебных заведений. Кроме того, допускалось наличие нескольких старшекурсников. Подбор задач на Московской олимпиаде оказался очень удачным: задачи в сумме были достаточно сложными, так что со всеми справилась только одна команда и всего за несколько минут до конца соревнований. Впрочем, среди задач попадались и простые, так что нулевых оценок было очень мало.

В соревнованиях подобного рода очень важно распределить задачи в порядке возрастания сложности, и большинству команд это удалось. За сложные задачи они брались только после того, как сдавали более простые. Этим, в частности, объясняется малое число попыток сдать задачу F в Москве.

В Рыбинске задачи оказались полегче: пять команд решили их все, причем одна из них («Пофигисты», команда первокурсников с факультета ВМиК МГУ) сдала последнюю задачу за два часа до конца соревнований. Однако в итоге эта команда заняла только третье место, несмотря на то что первый и второй призеры сдали последнюю задачу на час позже. Мне кажется, что решающую роль здесь сыграло ошибочное распределение приоритетов: в первую очередь команда бралась за наиболее сложные задачи. Такая тактика хороша на соревнованиях школьников, где за полностью решенную задачу начисляется определенное количество баллов минус штрафные баллы за дополнительные подходы (и где можно сдавать частично решенные задачи, работающие на неполном наборе тестов). На студенческих олимпиадах засчитываются только полностью решенные задачи и за каждую начисляются штрафные баллы по числу минут, прошедших от начала соревнований до момента сдачи, плюс еще по 20 штрафных баллов за каждую неверную посылку.

Чем можно объяснить то, что на Московской студенческой олимпиаде победили школьники, а результаты четвертьфинала фактически повторили итоги соревнований в Москве?

Виктор Малышко:

К победе школьников на Московской студенческой олимпиаде организаторы относятся спокойно. Правда, возникла мысль как-то узаконить (или, возможно, запретить) участие команд школьников в олимпиаде. До сих пор правила олимпиады до конца не сформулированы. В этом году появилось еще одно новшество — участие смешанных команд, объединивших студентов разных вузов. Все это подталкивает нас к принятию четких правил или устава олимпиады.

Евгений Панкратьев:

Путь к финалу у студенческих команд складывается по-разному. Одни команды пробиваются в финал благодаря упорным тренировкам. К таким я отношу, например, команду Южно-Уральского университета. Другие добиваются успеха благодаря таланту их лидеров, проявивших себя еще в школьные годы. Наиболее яркий пример, на мой взгляд, Николай Дуров из Петербургского университета. За команду школьников, победившую на Московской олимпиаде, выступал Петр Митричев, который получил золотую медаль на Международной олимпиаде по информатике, еще когда учился в 9-м классе.

Относительно объективных и случайных факторов: бывает, конечно, что команда проваливает соревнования или выступает неожиданно успешно, но это случается не так уж часто. В состязаниях же команд примерно одного уровня (а к таким я отношу, например, пятерку первых команд из четвертьфинала) роль фактора случайности весьма высока. Поэтому их относительные результаты в четвертьфинале и на Московской олимпиаде несколько отличаются, а в Петербурге, по-видимому, будут совсем другими.

Каковы дальнейшие планы оргкомитета Московской олимпиады?

Виктор Малышко:

Весной будет факультетская олимпиада (ВМиК МГУ). Вероятно, отрытая и командная. Пока все очень туманно. А следующей осенью состоится V Московская олимпиада по программированию. Может быть, на ней, как знать, снова выступят победители этого года, но уже защищая цвета какого-нибудь московского вуза...

Как вы оцениваете результаты прошедших олимпиад и шансы ваших команд в дальнейшей борьбе?

Виктор Малышко:

По поводу прошедших соревнований могу сказать одно: все хорошо, что хорошо кончается. Вузы были представлены на олимпиадах достаточно широко. Надеемся, что сенсационный результат Московской олимпиады — победа команды школы 57 — привлечет внимание к нашим будущим соревнованиям. Оглядываясь назад и сравнивая результаты олимпиады в Москве с результатами соревнования в Рыбинске, можно составить представление о том, как обстоят дела в Москве сегодня. Тренеры и руководители команд могут использовать результаты московских соревнований в своей работе, нацеливаясь на чемпионат мира под эгидой ACM.

На Московской олимпиаде команды взяли неплохой старт. Наша молодая команда, состоящая из первокурсников («Пофигисты»), продемонстрировала высокий уровень и заняла третье место. Восьмое место наших «ветеранов» — команды Prodigy — вызывает меньше приятных эмоций, но, с другой стороны, задача войти в тройку лидеров перед ними не ставилась. Целью было пройти в рыбинский четвертьфинал через негласно проводимый отбор команд МГУ — и они успешно ее решили. Кстати, в прошлом они уже были призерами Московской олимпиады, и, по-моему, призовые места для них не столь привлекательны, как для новичков.

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

Александр Чернов:

На самом деле, это была всего лишь их вторая командная олимпиада, и ребята допустили много ошибок из-за своей неопытности и невнимательности. Например, в условии задачи сказано, что программа должна считывать данные из определенного файла, а они считывали их со стандартного ввода. Это стоило им нескольких штрафных попыток. Так что, мне кажется, такой исход (когда их оттеснили на третье место) для них даже полезен.

Евгений Панкратьев:

Я, наверное, не буду оригинальным, если скажу, что выступления российских команд в финалах последних олимпиад были очень успешными. К сожалению, результаты команд Московского университета, в том числе команд механико-математического факультета, были ниже, чем нам хотелось бы. Однако следует отметить, что на фоне блестящего выступления первой команды — Петербургского университета — ее отрыв от второй кажется слишком большим. В то же время в прошлом полуфинале три команды МГУ вошли в первую десятку (3-е, 6-е и 8-е места). Я уверен, что и в этом году одна из команд МГУ (к сожалению, только одна, таковы уж правила этих соревнований) пробьется в финал, и даже надеюсь, что в полуфинале она войдет в тройку призеров. Какая это будет команда, предсказать трудно: я уже говорил, что уровень примерно одинаков. Относительно шансов в финале судить не берусь: безоговорочно признаю преимущество прошлогодних победителей.

Как вы считаете, лишила ли себя Россия дополнительных мест в финале, начав проводить четвертьфиналы? (По правилам ACM, определив регион для полуфинала, в котором будет участвовать как минимум 12 университетов, представивших как минимум 24 команды, уже можно претендовать на одно место в финале чемпионата.)

Евгений Панкратьев:

Готов разделить это мнение, однако отмечу, что соревнования в Санкт-Петербурге отличаются по уровню от других региональных соревнований и участие в них позволяет командам приобрести ценный опыт.

Виктор Малышко:

По-моему, это не соответствует действительности. Достаточно заглянуть в статистику на сайте чемпионата, чтобы убедиться, что наш регион вполне официально представляют около 300 команд почти из 150 вузов.

По сравнению с другими регионами у нас число участников больше в разы. При такой массовости четвертьфиналы — это естественный выход из положения (по организационным и техническим причинам провести соревнование сразу 300 команд очень сложно). Даже сейчас полуфинал проходит одновременно в трех городах: Санкт-Петербурге, Барнауле и Тбилиси. И это после предварительного отбора! Посмотрите на список команд, зарегистрированных в Питере, — их около 100, а вузов порядка 40. О потере дополнительных мест не может быть и речи.

Тут в пору подумать о разделении Северо-Восточного региона Восточной Европы на несколько регионов. Не это ли имеется в виду? Подозреваю, что организация нового региона — сложный вопрос. Официальная позиция организаторов ACM ICPC на этот счет мне неизвестна. Неизвестно также, есть ли у центров на Урале и в Сибири силы и желание для организации там отдельных региональных олимпиад.

Александр Чернов:

Наш регион, в общем, даже не самый крупный. Есть, например, Юго-Восточная Азия, где население в 10 раз больше. Учебных заведений тоже... Очень мелкое деление США на регионы обусловлено историческими причинами. По-моему, директорат ICPC действительно неохотно идет на создание других регионов.

Но посмотрим на это с другой стороны. Да, команд в нашем регионе много. Но даже если регион и разделится, скажем, на два или три, что вызовет соответственное уменьшение количества мест для каждого из новых регионов в финале до одного или двух, то кто будет представлять Россию в финале? Те же университеты, которые это делают и сейчас. Кроме того, сегодня в России действительно практически больше никто не сможет провести соревнования уровня полуфинала. Поэтому деление нашей зоны — вопрос, скорее, праздный.

Каковы ваши прогнозы на полуфинал и финал с учетом того, что российские команды-фавориты прошлых лет в этом году не будут участвовать в чемпионате ACM?

Евгений Панкратьев:

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

Но в этом году повторить результат команды Петербургского университета, по всей видимости, не удастся ни одной из российских команд. Надеюсь на более успешное, чем в прошлом году, выступление в финале команды Московского университета.

Виктор Малышко:

В полуфинале есть большие надежды на наших первокурсников («Пофигисты»). Другая команда факультета ВМиК — Prodigy — имеет за спиной большой опыт и может проявить характер (как в 2000 году в Питере, где наши ребята заняли третье место, когда их уже никто не брал в расчет). Коллеги с мехмата МГУ последнее время показывают стабильно высокий результат, поэтому у нас будет жесткая конкуренция за место в финале (от одного вуза может быть послана только одна команда). То, что команда МГУ будет в финале, для меня несомненно. Из московских команд, по-моему, еще есть шансы у команды МИФИ.

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

Прогноз на финал дать трудно. Может ли какая-то российская команда стать чемпионом мира в этом году? Пожалуй, да. Как минимум, россияне будут призерами, а кто именно — покажет время... 

 Предыдущие публикации:

 В продолжение темы:

Обсуждение и комментарии

	observer 29 Nov 2001 6:49 AM
"28 ноября одновременно в трех российских городах — Санкт-Петербурге, Барнауле и Тбилиси ..." - тренеры считают, что в Тбилиси уде наши?-)
	glassy 29 Nov 2001 1:17 PM
Шустрые, однако ;)
	MagiciaN - slon_magicmail.ru 26 Apr 2004 2:35 AM
Как можно поучаствовать в соревнованиях по проагромированию. Любого рода. На каких языках прагромирования они праходят?
	ambien - buyambagotta.kom 5 Aug 2006 8:41 AM
My life's been basically dull these days. Whatever. I haven't gotten much done these days. Today was a complete loss. <a href='http://hometown.aol.de/nehochuvtop/ambien/index.html'> ambien</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/generic-ambi en.html'>generic ambien</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/buy-ambien-o nline.html'>buy abmien online</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/ambien-cr.ht ml'>ambien cr</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/ambien-overd ose.html'>ambien overdose</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/addiction-to -ambien.html'>addiction to ambien</a> <a href='http://hometown.aol.de/nehochuvtop/ambien/order-ambien .html'>order ambien</a> http://hometown.aol.de/nehochuvtop/ambien/index.html http://hometown.aol.de/nehochuvtop/ambien/generic-ambien.ht ml http://hometown.aol.de/nehochuvtop/ambien/buy-ambien-online .html http://hometown.aol.de/nehochuvtop/ambien/ambien-cr.html http://hometown.aol.de/nehochuvtop/ambien/ambien-overdose.h tml http://hometown.aol.de/nehochuvtop/ambien/addiction-to-ambi en.html http://hometown.aol.de/nehochuvtop/ambien/order-ambien.html