Стокгольмский синдром
Спортивному программированию не светят лавры футбола или хоккея, но с менее зрелищными и динамичными видами спорта он вполне может потягаться. Хотя наблюдателю почти статичная картинка скорее всего напомнит университетскую библиотеку.
Автор: Владимир Гуриев
| Раздел: Статьи |
Дата: 29 мая 2009 года
Студенческими олимпиадами, чемпионатами по программированию и прочими образовательными мероприятиями, которые интересны главным образом самим участникам и их мамам, у нас долгие годы занимался другой редактор. И, отправляясь в конце апреля на чемпионат мира по командному программированию в Стокгольм, я не ожидал ничего хорошего. Холодно, ветрено, а тут ещё и программисты... Через пять дней я вернулся в Москву с уверенностью, что за следующим чемпионатом буду следить как минимум в онлайн-трансляции, а если повезет, то увижу и живьём. Сомневаюсь, что смогу это объяснить, но убежден в том, что устроители чемпионата делают полезное, нужное, а главное, очень интересное дело.
Самая большая имиджевая проблема чемпионата заключается в том, что программисты - приличные и спокойные люди. Трудно представить, что один программист отгрызет сопернику из другой команды ухо, накричит на судью или хотя бы разорвет футболку. Программистам не хватает темперамента. Наблюдателю, забравшемуся на балкон над залом, в котором проходит соревнование, почти статичная картинка скорее всего напомнит университетскую библиотеку. Шепот, шелест, сопение. Резкий звук передвигаемых стульев. Затылки, затылки, затылки. Программирование - не самый зрелищный вид спорта, его трудно полюбить с первого взгляда. И в любом описании оно выглядит ещё более унылым, чем есть на самом деле.
В действительности всё не так плохо. Стоит приложить незначительное усилие, хотя бы немного разобраться в том, что и с кем, собственно, происходит там, внизу, - и чемпионат сразу покажется интересным и даже напряженным. Природу, конечно, не обманешь. Спортивному программированию не светят лавры футбола или хоккея, но с менее зрелищными и динамичными видами спорта он вполне может потягаться. В конце концов, у техасского покера, который по внешней динамике находится примерно там же, где и программирование, то есть в районе абсолютного нуля, это получилось. Грамотный комментарий, правильная режиссура, минимальный ликбез - и миллионы телезрителей, волнуясь, следят за перипетиями мирового чемпионата мира по программированию.
Тем более что первый шаг к визуализации организаторы давно сделали. К столу команды, решившей очередную задачу, прикрепляется воздушный шарик. Выглядит трогательно.
Минимальный ликбез
Сто студенческих команд приехало в Стокгольм, чтобы во время пятичасового финала мирового чемпионата по командному программированию (ACM ICPC) решить как можно больше задач из предложенного набора. Порядки довольно строгие. Компьютер на каждую "тройку" всего один. В подмогу, впрочем, дают калькулятор, если кому-то от этого легче. Выходить из зала во время соревнования нельзя. Пользоваться другими электронными устройствами тоже нельзя. Собственно, никаких запрещенных устройств у участников уже нет, у команд изымают все внушающие подозрение предметы (и шансов на то, что нарушителям изъятое вернут, немного). Разрешается иметь при себе лишь бумажный словарь и бумажный же блокнот.
На столиках в сторонке стоят пластиковые упаковки с едой и бутылки воды, но пока почти никто не ест, не до того. Чтобы победить в этом соревновании, нужно решить максимальное количество задач как можно быстрее. Все задачи за пять часов решить невозможно. По крайней мере, ни одной команде в истории ACM ICPC этого не удалось. Не последнюю роль в этом сыграли устроители соревнования. С каждым годом количество заданий увеличивается (в нынешнем году - одиннадцать), а сами задачи усложняются (организаторы пытаются бороться с тем, что команды решают всё быстрее и быстрее). "Когда-то мы и подумать не могли, что на задачу можно потратить меньше получаса, - говорит Билл Паучер, в прошлом тренер, потом судья, а теперь исполнительный директор ACM ICPC, - а теперь..."
А теперь за первые пятнадцать минут с задачей А справилось четыре команды: Университет Ватерлоо (Канада), Стэнфорд, Университет Цинхуа и прошлогодние чемпионы, питерский ИТМО. Показатель довольно важный, поскольку на ICPC имеет значение не только количество решённых задач, но и время, затраченное на их решение. Причем каждый раз отсчет начинается от начала соревнования. Поэтому сначала участникам необходимо решить метазадачу, а именно приблизительно оценить сложность предложенных заданий, и лишь затем приступить к решению простейшей, постепенно наращивая сложность.1 Если обе команды решили равное количество задач, побеждает та, которая затратила на это меньше времени (сложность решенных заданий - величина субъективная, и она не учитывается). И хотя регламентом это не предписывается, но самые сложные, почти нерешаемые задачи, как правило, идут ближе к концу списка, тогда как простенькие помещаются в начале.
Дополнительные штрафные минуты можно заработать, отправив судьям неправильное решение. Тексты программ оценивает автоматическая система под присмотром вполне живых судей, поэтому отклик - принято или нет - команда получает довольно быстро, однако каждая неудачная попытка добавляет штрафное время (если задача решена).
Схитрить и взять количеством не получится. Уровень соперников таков, что претендент на победу обязан решить сложную задачу. Медалей ACM не жалеет - на каждом чемпионате разыгрывается как минимум по четыре комплекта золотых, серебряных и бронзовых медалей. Но чемпион будет только один.
И последняя тонкость. Несмотря на то что команда ИТМО считается одним из фаворитов, в её составе совсем не те люди, что выиграли чемпионат годом раньше. Жесткую ротацию участников обеспечивают два правила. Во-первых, ни один спортсмен не может участвовать в чемпионате больше двух раз. Во-вторых, ни один университет не может послать на всемирный финал больше одной команды. Таким образом, вчерашним чемпионам нужно заново доказывать право на участие в финале, проходя через внутривузовские и региональные соревнования. Это не очень справедливое по отношению к фаворитам правило подчеркивает, что ACM ICPC - соревнование, в первую очередь, межвузовское.
Уровень вуза, как ни странно, не имеет решающего значения. Ничуть не умаляя заслуг ИТМО (в прошлом - институт точной механики и оптики, теперь - университет ИТ, механики и оптики), можно сказать, что успехи вуза на ниве ACM ICPC - это, прежде всего, результат усилий энтузиастов, поддерживающих интерес к олимпиадам по программированию и создавших жесткую структуру подготовки и отбора. Точно такая же ситуация в Саратове (СГУ), который, как и СПбГУ ИТМО, не входит в Топ-500 лучших университетов мира по версии ARWU. Собственно, в этот рэнкинг входят только два российских вуза - МГУ (70-е место) и СПбГУ (где-то в четвертой сотне), - причем СПбГУ выступает на чемпионате гораздо успешнее, чем МГУ. Один из главных конкурентов российских команд - китайский университет Цинхуа - в рэнкинге ARWU занимает скромную позицию в третьей сотне. В прошлогоднем рейтинге THES-QS он же добрался до 56-й ступеньки, заметно опередив МГУ (183). Практического значения на чемпионате эта информация не имеет. Как поставлена система образования в вузе, не очень-то и важно.
- Подготовить хорошую команду, - говорит Роман Елизаров, председатель жюри Северо-восточного европейского региона (NEERC), - может и небольшая группа преподавателей.
Тренер у нынешней команды ИТМО тот же, что и у прошлогодних победителей, - Андрей Станкевич. В прошлом он и сам медалист ICPC: в 2000 году в составе команды ИТМО заработал серебро (четвертое место), через год - золото (третье место). А сейчас вместе с Андреем Лопатиным (тренер команды СПбГУ), Владимиром Парфеновым (профессор ИТМО), Иваном Романовым (чемпион 2006 года; теперь работает в исследовательской лаборатории IBM в Цюрихе) и другими российскими болельщиками Станкевич, благодаря интернет-трансляции, наблюдает за происходящим из соседнего здания.
С другой стороны
Выглядит зона для болельщиков довольно странно. Москва, обе питерские команды и Саратов конкурируют между собой ничуть не меньше, чем с китайцами, однако конкуренция не мешает радоваться чужим победам, если эти чужие хотя бы немного, но свои. К китайцам отношение осторожное. Они, во-первых, очень сильны, а во-вторых, их довольно много. Кто-то вскользь упоминает команду из Стэнфорда, в которой, мол, тоже все китайцы.
Но китайцы и без Стэнфорда очень опасны. И играют с каждым годом лучше и лучше. Один из членов российской делегации рассказывает мне, что китайское правительство напрямую поддерживает свои команды. По-моему, ему немного обидно. У нас 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, Андрей Лопатин тренирует нынешнюю команду СПбГУ, а Николай Дуров в свободное от сайта "ВКонтакте" время занимается наукой.
Сам Роман Елизаров тоже остался в Питере, организовав с другими выпускниками ИТМО компанию, разрабатывающую торговые платформы для фондового рынка. Как и сотни других волонтеров, он участвует в организации ACM ICPC на добровольных началах, освобождая рабочий график, чтобы поучаствовать в финале и отборочных соревнованиях. Впрочем, в Стокгольме он, скорее, отдыхает и болеет за "своих". А еще участвует в конференции региональных координаторов. И, наверное, обмывает награду - в этом году Роман Елизаров, профессор Владимир Парфенов и ректор Владимир Васильев как представители ИТМО получили DeBlasi Award, которая вручается за выдающийся вклад (outstanding contribution) в развитие ICPC.
Кроме того, Васильев, Парфенов и Елизаров представляют Санкт-Петербургский ИТМО как вуз, в котором будут соревноваться программисты в 2013 году.
Русский и Питер
Принципы, по которым ACM (и, очень вероятно, 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 (Иван Романов прибыл в Стокгольм как раз для того, чтобы рассказать о нескольких проектах лаборатории в Цюрихе). Конечно, сами по себе такие намеки не слишком эффективны, но как дополнительное усилие в рамках академической программы IBM (компания сотрудничает с вузами, которые, далее цитата, "поддерживают открытые стандарты и стремятся использовать в учебном процессе технологии с открытым исходным кодом, а также программные продукты и решения IBM") наверняка оправданы. Сегодня ты поучаствовал в чемпионате, который существует благодаря IBM, завтра получил бесплатный и полезный продукт от IBM, послезавтра - грант. А потом ты закончил вуз, и на рынке труда появился человек, который превосходно владеет технологиями от IBM и при прочих равных предпочтет использовать их, чем что-либо другое. Тот факт, что в качестве машин для соревнования используются IBM-Lenovo ThinkPad T61 с предустановленным CentOS Linux 5.2, вряд ли имеет значение, это обычный здравый смысл, но, как гласит старинная шведская поговорка, it helps3.
Я, впрочем, далек от мысли, что сотрудники IBM, занятые организацией чемпионата, склонны думать о нём в бухгалтерских терминах. Мне, наоборот, показалось, что они, как и сотрудники ACM, не говоря уже о волонтерах, занимаются чемпионатом, потому что им это нравится. Но в корпоративном мире слова "мне это нравится" плохо влияют на выделение средств, и, возможно, рационализация трат выглядит примерно так, как я описал. Дополнительным фактором "за" является то, что чемпионат при поддержке IBM растет как на дрожжах. В 1997 году за титул чемпиона мира боролось восемьсот команд. Сегодня в отборе принимают участие больше семи тысяч "троек", представляющих почти две тысячи университетов.
Меня, впрочем, в данный момент интересует одна-единственная тройка, которая лидировала после четырех часов соревнования, а теперь спустилась на второе место. Я ещё плохо ориентируюсь в таблице результатов и не вижу того, что уже увидел Станкевич. Команде Цинхуа зачтено девять задач. Десятую судьи не приняли, она лишь добавила китайцам штрафное время. Таблица меняется ещё раз. На первое место выходит ИТМО. У наших тоже девять задач, но штрафных минут меньше. В окончательном варианте таблицы на первом месте ИТМО. Золотые медали получают также Цинхуа, СПбГУ и Саратов. На восьмом месте (серебряная медаль) - Алтайский государственный университет. На одиннадцатом (бронза) - тоже почти наши люди, Тбилисский университет имени И. Джавахишвили, входящий, как и другие вузы постсоветского пространства, в NEERC. Чуть позже, когда победителям будут вручать медали в здании стокгольмского концерт-холла4, выяснится, что ТГУ - самый проблемный для организаторов победитель, так как выговорить фамилию Джавахишвили для ведущего церемонии почти непосильная задача. Каждый раз он слегка запинается на этом месте и потом очень осторожно и с каким-то недоверием продолжает.
Но если так пойдет и дальше, привыкнут.
P.S. Что касается команды из Стэнфорда, то этнический китаец в ней всего один - Джерри Вон. Его товарищи Энди Нгуен и Чже Хьюн Пак, соответственно, вьетнамец и кореец. Так что не так страшен Стэнфорд. Двадцатое место в общем зачете.
Из еженедельника "Компьютерра" № 18 (782)
1. Если у вас есть простая задача А (на которую требуется полчаса) и сложная задача Б (три часа), и вы начали со сложной, то "заработаете" шесть с половиной штрафных часов (три часа на задачу Б и плюс те же три часа и еще полчаса на решение задачи А). Обратный порядок дает лишь три с половиной часа. [назад]
2. Схожую аргументацию, рассказывая о "легендарных российских программистах", использовал и Степан Пачиков (см. "КТ" #779). [назад]
3. Я интереса ради решил проверить, поставлялся ли T61 когда-нибудь с этим дистрибутивом. Оказалось, что нет. Lenovo продавала Linux-версию T61, но использовала Novell SLED. Сегодня на сайте Lenovo нет ни одного ThinkPad, который можно было бы купить с предустановленным Linux - потребитель может лишь отказаться от Windows Vista (хотя я бы не стал, так как на цену лэптопа такой аскетизм никак не влияет). Впрочем, T61 там тоже больше нет, устарел. Однако самые упорные могут найти таблицу совместимости ThinkPad’ов с разными дистрибутивами Linux - в ней есть и T61, и более актуальные T400 и T500. [назад]
4. Там же вручаются Нобелевские премии, между прочим. [назад]
Vova
