Компьютерра - Журнал Компьютерра N782

А теперь за первые пятнадцать минут с задачей А справилось четыре команды: Университет Ватерлоо (Канада), Стэнфорд, Университет Цинхуа и прошлогодние чемпионы, питерский ИТМО. Показатель довольно важный, поскольку на 1СРС имеет значение не только количество решенных задач, но и время, затраченное на их решение. Причем каждый раз отсчет начинается от начала соревнования. Поэтому сначала участникам необходимо решить метазадачу, а именно приблизительно оценить сложность предложенных заданий, и лишь затем приступить к решению простейшей, постепенно наращивая сложность.' Если обе команды решили равное количество за-

U НАТАЛЬЯ Б ОНДАРЕНКО И ДМИТРИЙ М АТОВ ( КОМАНДА C r V J

П КОМАНДА САНКТ - ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

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

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

- принято или нет - команда получает довольно быстро, однако каждая неудачная попытка добавляет штрафное время (если задача решена)

Схитрить и взять количеством не получится. Уровень соперников таков, что претендент на победу обязан решить сложную задачу. Медалей АСМ не жалеет - на каждом чемпионате разыгрывается как минимум по четыре комплекта золотых, серебряных и бронзовых медалей. Но чемпион будет только один.

И последняя тонкость. Несмотря на то что команда ИТМО считается одним из фаворитов, в ее составе совсем не те люди, что выиграли чемпионат годом раньше. Жесткую ротацию участников обеспечивают два правила. Во-первых, ни один спортсмен не может участвовать в чемпионате больше двух раз. Во-вторых, ни один университет не может послать на всемирный финал больше одной команды. Таким образом, вчерашним чемпионам нужно заново доказывать право на участие в финале, проходя через внутривузовские и региональные соревнования. Это не очень справедливое по отношению к фаворитам правило подчеркивает, что ACM ICPC - соревнование, в первую очередь, межвузовское.

Уровень вуза, как ни странно, не имеет решающего значения. Ничуть не умаляя заслуг ИТМО (в прошлом

- институт точной механики и оптики, теперь - университет ИТ, механики и оптики), можно сказать, что успехи вуза на ниве ACM ICPC - это прежде всего результат усилий энтузиастов, поддерживающих интерес к олимпиадам по программированию и создавших жесткую структуру подготовки и отбора. Точно

I Если у вас есть простая задача А (на которую требуется полчаса) и сложная задача Б (три часа), и вы начали со сложной, то ¦¦ заработаете» шесть с половиной штрафных часов [три часа на задачу Б и плюс те же три часа и еще полчаса на решение задачи А). Обратный порядок дает лишь три с полааиной часа.

ПЕРИФЕРИЯ

рекорды

такая же ситуация в Саратове (СГУ), который, как и СПбГУ ИТМО, не входит в Топ-500 лучших университетов мира по версии ARWU. Собственно, в этот рэн-кинг входят только два российских вуза - МГУ (70-е место) и СПбГУ (где-то в четвертой сотне), - причем СПбГУ выступает на чемпионате гораздо успешнее чем МГУ. Один из главных конкурентов российских команд - китайский университет Цинхуа - в рэн-кинге ARWU занимает скромную позицию в третьей сотне. В прошлогоднем рейтинге THES-QS он же добрался до 56-й ступеньки, заметно опередив МГУ (183). Практического значения на чемпионате эта информация не имеет, Как поставлена система образования в вузе, не очень-то и важно.

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

Тренер у нынешней команды ИТМО тот же, что и у прошлогодних победителей, - Андрей Станкевич. В прошлом он и сам медалист ICPC: в 2000 году в составе команды ИТМО заработал серебро (четвертое место), через год - золото (третье место). А сейчас вместе с Андреем Лопатиным (тренер команды СПбГУ), Владимиром Парфеновым (профессор ИТМО), Иваном Романовым (чемпион 2006 года; теперь работает в исследовательской лаборатории IBM в Цюрихе) и другими российскими болельщиками Станкевич, благодаря интернет-трансляции, наблюдает за происходящим из соседнего здания.

С Д РУГОЙ С ТОРОНЫ

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

Но китайцы и без Стэнфорда очень опасны. И играют с каждым годом лучше и лучше. Один из чле-

‹1 КОМАНДА ИТМО

П КОМАНДА ЦИНХУА

нов российской делегации рассказывает мне, что китайское правительство напрямую поддерживает свои команды. По-моему, ему немного обидно. У нас ICPC тоже поддерживают, но в основном на местах, а такого, чтобы страна требовала рекордов, да не жалела на них денег - такого нет. Если мой собеседник не ошибается насчет правительственной поддержки китайских команд, то мы, конечно, в неравном положении. Но не в худшем, Последние несколько лет на ICPC - это годы российского превосходства, Мы выигрывали на ICPC пять раз. У американцев, правда, семнадцать побед на счету, но все эти победы относятся к тому времени, когда ни нас, ни китайцев на чемпионате, считай, и не было. С 1998 года ни одна американская команда чемпионом не становилась.

Сами американцы объясняют несоответствие места, которое занимает их софтверная индустрия, и мест, которые занимают американские команды на чемпионате, тем, что в России и Китае лучшие мозги идут в программирование, а а США - в бизнес.2 Согласно другой теории, чемпионат по программированию вообще не имеет никакого значения, поскольку задачи, которые приходится решать конкурсантам, не имеют отношения к реальным программистским задачам, да и вообще, для программиста главное - это умение работать в команде, а гении-одиночки давно никому не нужны. И американцы, в отличие от русских и китайцев, это понимают.

Упрек в отрыве от реальности не слишком справедлив. С тем же успехом можно заставлять биатлонистов стрелять по живым мишеням (зрелищность, кстати, повысилась бы). Реальные задачи сопровождаются таким невероятным количеством граничных условий разной степени разумности, что воссоздать их полностью в рамках соревнования невозможно и наверняка не нужно. Впрочем, оргкомитет ACM ICPC, видимо, устал объяснять условность, заложенную в спортивное состязание, и последние несколько лет а списке всегда присутствуют задачи, напоминающие «бизнес-кейсы». В этом году с муравьем Карлом, запутавшимся в ребрах правильного восьмигранника, соседствуют авиадиспетчер, чью работу нужно частично автоматизировать, и работник бюро городского планирования, которому нужно оптимизировать городской трафик. Понятно, что на месте авиадиспетчера легко мог оказаться муравей, и бизнес-упаковка на суть задачи никак не влияет.