рекорды

Стокгольмский синдрог м инимальны й л икбез

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

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

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

UНАТАЛЬЯБОНДАРЕНКО ИДМИТРИЙМАТОВ (КОМАНДАCrVJ

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

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

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

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

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

И последняя тонкость. Несмотря на то что команда ИТМО считается одним из фаворитов, в ее составе совсем не те люди, что выиграли чемпионат годом раньше. Жесткую ротацию участников обеспечивают два правила. Во-первых, ни один спортсмен не может участвовать в чемпионате больше двух раз. Во-вторых, ни один университет не может послать на всемирный финал больше одной команды. Таким образом, вчерашним чемпионам нужно заново доказывать право на участие в финале, проходя через внутривузовские и региональные соревнования. Это не очень справедливое по отношению к фаворитам правило подчеркивает, что 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, видимо, устал объяснять условность, заложенную в спортивное состязание, и последние несколько лет а списке всегда присутствуют задачи, напоминающие «бизнес-кейсы». В этом году с муравьем Карлом, запутавшимся в ребрах правильного восьмигранника, соседствуют авиадиспетчер, чью работу нужно частично автоматизировать, и работник бюро городского планирования, которому нужно оптимизировать городской трафик. Понятно, что на месте авиадиспетчера легко мог оказаться муравей, и бизнес-упаковка на суть задачи никак не влияет.

Что касается навыков командной работы, то они для успешного выступления на чемпионате являются ключевыми. Успех команды во многом зиждется на -зсколько хорошо участники исполняют свои юли. Компьютер на троих один, и для экономии времени важно максимально эффективно распределить связанности. Как правило, "Центровой» у команды - один. Именно он придумывает, как решать задачу, и пока двое остальных участников программируют решение, ломает голову над следующей. Теоретически роли могут меняться в ходе соревнования, но на практике такое происходит редко.

Разумеется, хорошие программисты здесь на вес золота: если поинтересоваться индивидуальными достижениями участников, то окажется, что в самых успешных командах многие могут похвастать ведущими позициями в индивидуальном рейтинге TopCoder. Но это всего лишь необходимое условие. Московскому программисту Петру Митричеву (второе место в TopCoder Algorithm) и китайцу ACRush (первое место в том же рейтинге плюс победа в прошлогоднем Google Code Jam) ни разу не удавалось подняться в чемпионате ACM ICPC выше второго места.

- Даже «звездный» игрок победы не гарантирует. - говорит Роман Елизаров. - Нужна уникальная команда. И немного везения.

Петр свои попытки уже использовал и теперь наблюдает за происходящим из зрительного зала, пристроившись на стульчике чуть в стороне от остальных. ACRush находится с другой стороны баррикад. Он второй раз играет за команду университета Цинхуа, и эта команда успела за пять часов сдать десять задач из одиннадцати. Против девяти у нашего ИТМО,

Мы окончательных данных о решенных задачах еще не знаем. У нас перед глазами оживает замороженная за час до окончания таблица, и университет Цинхуа взлетает на первое место. Тренер ИТМО Андрей Станкевич смешно вскидывает руки, сидящий за ним Владимир Парфенов - декан факультета ИТ и программирования в том же СПбГУ ИТМО - напряженно подается вперед.

ЗАЧЕМЭТОIBM?

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

в IBM, но большинство - находит работу где-то еще, благо предложений хватает.

- Предложения, связаные с переездом, интересны, в первую очередь, ребятам из регионов, - объясняет Роман Елизаров, участник первой команды ИТМО, добравшейся до финала в 1995 году. - А если ты живешь в Москве или в Питере, то легко можешь найти себе интересную работу на месте, Хоть в российской фирме, хоть в Sun, Intel или Google.

Первые российские чемпионы мира (СПбГУ, 2000 год) устроились не так уж плохо. Олег Етеревский работает в питерском Google, Андрей Лопатин тренирует нынешнюю команду СПбГУ, а Николай Дуров в свободное от сайта «ВКонтакте" время занимается наукой.

Сам Роман Елизаров тоже остался в Питере, организовав с другими выпускниками ИТМО компанию, разрабатывающую торговые платформы для

U.'ЖЕНЩИНА, ДУМАЙ, ЧТОГОВОРИШЬ, ДА?»

фондового рынка. Как и сотни других волонтеров, он участвует в организации ACM ICPC на добровольных началах, освобождая рабочий график, чтобы поучаствовать в финале и отборочных соревнованиях. Впрочем, в Стокгольме он, скорее, отдыхает и болеет за «своих». А еще участвует в конференции региональных координаторов, И, наверное, обмывает награду - в этом году Роман Елизаров, профессор Владимир Парфенов и ректор Владимир Васильев как представители ИТМО получили DeBlasi Award, которая вручается за выдающийся вклад (outstanding contribution) в развитие ICPC.

Кроме того, Васильев, Парфенов и Елизаров представляют Санкт-Петербургский ИТМО как вуз, в котором будут соревноваться программисты в 2013 году.

РУССКИЙИПИТЕР

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

- Я тут подумал, - сказал он, - и вспомнил, что нет такого правила, чтобы чемпионат проводился именно в университете.

Действительно, мет. И Королевский технологический, вообще говоря, не лучшая площадка для такого мероприятия, что повлекло за собой незначительные изменения регламента (зоне болельщиков отвели другое здание).

Следующий финал внесет свои изменения. Чемпионат 2010 года будет проводиться в Харбине, в феврале, чтобы конкурсанты могли полюбоваться на проводящийся ежегодно фестиваль ледяных скульптур. Сам фестиваль, если верить фотографиям, представляет собой неописуемой красоты зрелище,

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

В 2011 году финал, вероятно, будет проходить в Малайзии. Следующий, возможно, в Варшаве, а финал 2013 года, если все сложится, пройдет в Питере.

Интересно, что Санкт-Петербург не был первым российским кандидатом на проведение ACM ICPC. Поначалу была идея собрать программистов на острове Русский, где в 2012 году планируется провести саммит АТЭС. В настоящее время остров, на котором проживает чуть больше пята тысяч человек, для проведения международных конференций не слишком приспособлен. Формально являясь одним из районов Владивостока, остров на самом деле представляет собой независимое и слегка заброшенное образование. В планах принимающей стороны - выстроить к двенадцатому году деловой центр, гостиницы, океанариум, а главное, мост, который свяжет Русский с материком (сейчас добраться от острова до Владивостока можно только на пароме). Однако все эти планы были одобрены еще до всемирного экономического кризиса, и хотя строительство моста идет в прежнем темпе, а правительство неоднократно напоминало, что все запланированные объекты будут возведены в срок, организаторы ICPC с нашей стороны решили подстраховаться и использовать инфраструктуру, которую построили в срок триста лет назад. Это как-то вернее.

Так ACM ICPC 2013, не успев обосноваться на Дальнем Востоке, переехал в Питер.

ТАКЗАЧЕМЭТОIBM?

Возвращаясь к вопросу, зачем все это IBM, несправедливо будет не привести официальное объяснение, Поддержка корпорацией ICPC прекрасно укладывается в рамки концепции Smarter Planet. Дескать, если компания помогает создавать более умные транспортные системы (см, прошлый Recycle), или более умные медицинские системы, или более умные электросети, то помогать индустрии с умными людьми ей сам Томас Уотсон велел.

С другой стороны, в интересах IBM не просто умные люди, а умные люди, которые предпочитают технологии от IBM. Им вовсе не обязательно работать в самой компании. Даже лучше, если они организуют собственные фирмы или расскажут о технологиях IBM своим удачливым нанимателям. Поэтому в программе пребывания участников есть такие пункты, как экскурсия IBM Tech Trek и просмотр маленькой передвижной выставки IBM Technology Showcase (Иван Романов прибыл в Стокгольм как I раз для того, чтобы рассказать о нескольких проектах лаборатории в Цюрихе). Конечно, сами по себе I такие намеки не слишком эффективны, но как до-| полнительное усилие в рамках академической программы IBM (компания сотрудничает с вузами, которые, далее цитата, «поддерживают открытые стандарты и стремятся использовать в учебном процессе технологии с открытым исходным кодом, а также программные продукты и решения IBM») наверняка оправданы. Сегодня ты поучаствовал в чемпионате,

который существует благодаря IBM, завтра получил бесплатный и полезный продукт от IBM, послезавтра - грант, А потом ты закончил вуз, и на рынке труда появился человек, который превосходно владеет технологиями от IBM и при прочих равных предпочтет использовать их, чем что-либо другое. Тот факт, что в качестве машин для соревнования используются IBM-Lenovo ThinkPad T61 с предустановленным CentOS Linux 5.2, вряд ли имеет значение, это обычный здравый смысл, но, как гласит старинная шведская поговорка, it helps3.

Я, впрочем, далек от мысли, что сотрудники IBM, занятые организацией чемпионата, склонны думать о нем в бухгалтерских терминах. Мне, наоборот, показалось, что они, как и сотрудники АСМ, не говоря уже о волонтерах, занимаются чемпионатом, потому что им это нравится. Но в корпоративном мире слова «мне это нравится» плохо влияют на выделение средств, и, возможно, рационализация трат выглядит примерно так, как я описал, Дополнительным фактором «за» является то, что чемпионат при поддержке IBM растет как на дрожжах. В 1997 году за титул чемпиона мира боролось восемьсот команд. Сегодня в отборе принимают участие больше семи тысяч «троек», представляющих почти две тысячи университетов.

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

она лишь добавила китайцам штрафное время. Таблица меняется еще раз. На первое место выходит ИТМО, У наших тоже девять задач, но штрафных минут меньше. В окончательном варианте таблицы на первом месте ИТМО. Золотые медали получают также Цинхуа, СПбГУ и Саратов. На восьмом месте (серебряная медаль) - Алтайский государственный университет. На одиннадцатом (бронза) - тоже почти наши люди, Тбилисский университет имени И. Джавахиш-вили, входящий, как и другие вузы постсоветского пространства, в NEERC. Чуть позже, когда победителям будут вручать медали в здании стокгольмского концерт-холла*, выяснится, что ТГУ - самый проблемный для организаторов победитель, так как выговорить фамилию Джавахишвили для ведущего церемонии почти непосильная задача. Каждый раз он слегка запинается на этом месте и потом очень осторожно и с каким-то недоверием продолжает. Но если так пойдет и дальше, привыкнут. ¦

P.S. ЧтокасаетсякомандыизСтэнфорда, тоэтническийкитаецвнейвсегоодин- ДжерриВон. Его товарищиЭндиНгуениЧжеХьюнПаксоответственновьетнамецикореец. Такчтоне такстрашенСтэн-форд. Двадцатоеместовобщемзачете.

3 Я интереса ради решил проверить, поставлялся ли Т61 когда-нибудь с этим дистрибутивом. Оказалось, что нет Lenovo продавала Linux-версию Т61. на ис-попьзонала Novell SLED Сегодня на сайте Lenovo нет ни одного ThinkPad. который можно было бы купить с предустановленным Linux - потребитель может лишь отказаться от Windows Vista (хотя я бы не стал, так как на цену лэптопа такой аскетизм никак не влияет). Впрочем, Т61 там тоже больше нет, устарел. Однако самые упорные могут найти таблицу соаместимости ThinkPad'ов с разными дистрибутивами Linux - вней есть и Т61. и более актуальные ТДОО и Т500.

4 Там же вручаются Нобелевские премии, между прочим