Российские программисты заняли первое место. Чемпионы мира — о спортивном программировании
ВАШИНГТОН, 25 мая — РИА Новости. Команда Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (ИТМО) одержала победу в чемпионате мира по спортивному программированию ACM ICPC (International Collegiate Programming Contest), сообщили организаторы по итогам прошедшего в среду в городе Рапид-Сити (Южная Дакота, США) финала.
За победу боролись Иван Белоногов, Владимир Смыкалов и Илья Збань. Ребятам удалось решить 10 из 12 задач быстрее и грамотнее соперников. Готовил команду тренер Андрей Станкевич. В прошлом году он получил престижную награду ACM ICPC Senior Coach Award, которую вручают тренерам, чьи подопечные 15 и более лет выходят в финал конкурса.
© Ruptly
Как рассказала РИА Новости представитель ИТМО Лидия Перовская, "с каждым годом задачи чемпионата становятся сложнее, происходит непрерывная гонка знаний и задается очень высокая планка". Она призналась, что "хотя победа (команды) была вероятной, она все равно стала неожиданной" и "совершенно невероятной".
Второе место заняла команда Варшавского университета, третьими стали ребята из Сеульского национального университета, четвертое место завоевали чемпионы прошлого года — команда Санкт-Петербургского университета (СПбГУ). Команды еще двух российских вузов — МФТИ и Уральского федерального университета — вышли в финал и также стали призерами чемпионата.
В ежегодном чемпионате принимали участие более 130 команд со всего мира, 13 из них — российские. Последние годы Кубок мира передают друг другу две российские команды — СПбГУ и Университет ИТМО. На счету последнего семь чемпионских титулов — это абсолютный рекорд ACM ICPC. На втором месте находится СПбГУ с четырьмя кубками, а у ближайших зарубежных соперников — американского Стэнфорда и китайского университета Джао Тонг — по три победы.
Чемпионат ACM ICPC под эгидой компании IBM проводится ежегодно с 1977 года, за это время его золотая медаль и кубок победителя стали одним из "самых уважаемых компьютерных наград в мире". На счету российских вузов 12 чемпионских званий.
В ACM ICPC участвуют команды по три человека, в их распоряжении всего один компьютер. Финальный поединок длится пять часов. Побеждает команда, которая правильно решит наибольшее количество задач за наименьшее время. Каждое задание включает описание некой выдуманной ситуации (легенду), примеры тестов и формальные ограничения. Чтобы решить задачу, участникам нужно "перевести" условия на язык математики, затем разработать алгоритм решения и написать код.
Размер премии для победителей ACM ICPC 2017 составил 15 тысяч долларов США.
Следующий финал чемпионата мира пройдет в 2018 году в Пекине (КНР).
DataArt давно дружит с командой ИТМО по спортивному программированию и помогает ей. Этим летом в гости в наш петербургский центр разработки пришли Илья Збань, Иван Белоногов и Владимир Смыкалов. Чемпионы мира 2017 года рассказали о том, как именно программисты соревнуются между собой, о тренировочных сборах, любимых задачах и сильнейших соперниках.
Олимпиада по программированию
Главное соревнование программистов - международная студенческая олимпиада под эгидой ACM (ACM-ICPC, или просто ICPC) - проходит с 1970-х, а в виде, близком к сегодняшнему, оформилась в 1989 году. Олимпиада предназначена для студентов и аспирантов, за редким исключением к соревнованиям не допускают программистов старше 24-х лет. К тому же, испытывать силы в финале можно только дважды, а в региональных отборах разрешается участвовать всего пять раз. На ранних этапах, проходящих по всему миру, соревнуются тысячи команд. Около сотни лучших доходят до финала.Основные правила
Команды состоят из трех человек, при этом в распоряжении каждой команды - только один компьютер. Перед началом соревнования всем выдаются конверты с задачами алгоритмического или математического характера - от восьми до 13 штук - которые нужно решить за пять часов. Решение задачи - программа, считывающая текстовый запрос и выдающая текстовый ответ. Для проверки решение прогоняется примерно на сотне тестов, заранее подготовленных жюри, - верным оно признается, только если ответ получается правильным в каждом из тестов.Правила ICPC очень доходчиво изложены в ролике , выпущенном к чемпионату Урала по программированию - одному из первичных этапов отбора на Олимпиаду. Они едины для всех регионов и с 2013 года остались без изменений.
Языки и среда
В финале 2017 года можно было использовать языки Java, C++ и Python. Впрочем, понятно, что Python в принципе не очень быстрый - жюри не гарантировало, что на нем можно будет сдать задачу. Однако оно давало гарантии, что у них есть решения, написанные на этих языках, которые проходят все тесты.На разных соревнованиях набор языков может быть различным. Например, на онлайн-платформе Codeforces допускается около 20 языков: от C++ и Java до Haskell и Perl.
Большинство команд в финалах пишет на C++ , поскольку на первый план выходит скорость. В качестве среды разработки многие команды используют VIM (в нем, например, работали Иван и Илья) или Gina (в ней работал Владимир). Те, кто все же пишет на Java, как правило пользуются средой вроде Eclipse, поскольку писать на Java без автокомплита гораздо сложнее.
В ближайшее время можно ждать изменений, поскольку финалы теперь будет спонсировать JetBrains (20 лет до конца мая 2017 года спонсором ICPC был IBM). Это значит, что на них появится и продукция спонсора: IDEA для Java и CLion для С++. Возможно, после этого команды начнут широко пользоваться отладчиками, хотя пока чаще справляются без них.
Эволюция задач
В начале 2000-х преобладали задачи на перебор с небольшими ограничениями, сейчас стало больше задач на структуры данных. При этом в мире есть несколько достаточно обособленных школ спортивного программирования: если в Польше любят идейные, часто математические, задачи, в Китае предпочитают сложные технические, где приходится писать много кода, - например, считать комбинаторику.Цель всегда - придумать и реализовать решение, которое работает быстро. Любую задачу можно хоть как-то решить, например, написав программу, которая просто переберет все возможные варианты. Но в последние годы задачи, предполагающие написание переборов, практически не встречаются.
Существуют ограничения по времени и памяти, однако на практике проблемы с тем, что решение использует слишком много памяти, возникают нечасто. Ограничение по времени на каждый тест обычно от одной до трех секунд в зависимости от задачи - это тоже указывается в условии.
Примеры задач
Задачи бывают разными: на графы, строки, геометрию и т. д. Допустим, рассчитать кратчайший путь между городами на карте. Или построить максимально длинную взлетно-посадочную полосу на острове, представленном в виде невыпуклого многоугольника. Задачей может быть сравнение текстов - поиск наибольшей общей подстроки для пары строк.
Еще один формат - интерактивные задачи, где вам предлагают поиграть в какую-нибудь игру с системой, написанной жюри. В одном из полуфиналов нужно было написать программу, способную в 90 % случаев выигрывать у предложенного алгоритма в крестики-нолики. Задачи с прошлых финалов, включая последний, можно посмотреть .
Процесс решения
В основном участники команд разбирают листы с условиями в зависимости от личных предпочтений: кто-то больше любит задачи на строки, кто-то - на геометрию. В целом индивидуальная работа здесь преобладает над командной.Первым делом нужно придумать алгоритм решения одной из задач. Иногда автор решения обсуждает его с командой, чтобы убедиться - решение получается математически правильным. После этого автор садится писать код - двое других участников в это время продолжают думать над решениями остальных задач. Когда код написан, его можно проверить на тестовых примерах, которые обычно прилагаются к условию, и отправлять в систему для оценки. Поскольку компьютерное время ограничено (напомним, что компьютер у участников всего один), на соревнованиях всегда присутствует принтер: если решение не работает, кто-то - обычно его автор - ищет ошибки, распечатав код на бумаге.
Особенности кода
С одной стороны, люди, занимающиеся спортивным программированием, умеют писать код быстро и четко, причем в стрессовых условиях. С другой стороны, их нередко критикуют за то, что этот код содержит непонятные переменные и трудно читается. В коде, который пишется на соревнованиях, действительно нет длинных понятных названий переменных - ведь его не придется поддерживать через год. Впрочем, на высоком уровне эта проблема так остро не стоит, поскольку код все же должен быть понятен товарищам по команде.Еще одна особенность спортивного программирования в том, что тестовой системой никак не оценивается освобождение памяти - решение работает всего несколько секунд.
Алгоритмы
Мы знаем довольно много алгоритмов, используем разные структуры данных: дерево отрезков, дерево Фенвика, декартово дерево и т. д. Иногда сбалансированное дерево поиска приходится писать самостоятельно, параллельно модифицировав его так, чтобы оно считало информацию, определенную условием задачи. Например, в языке С++ есть структура множества, которая умеет поддерживать множество чисел и, например, находить следующее. Задача же может требовать найти не следующее число, а сумму всех чисел, меньших или равных заданному. Стандартными структурами реализовать это не получится.Приносить какие-то фрагменты коды с собой нельзя, но на чемпионате мира разрешается пользоваться так называемым team reference - распечатанным на бумаге набором алгоритмов. Хотя многое мы умеем писать с ходу, в этом году немало времени потратили на его подготовку - тестировали более сложные алгоритмы. Но в итоге записями не воспользовались вообще.
Объем кода напрямую не влияет на итоговую оценку, другое дело, что 1000 строк написать за отведенное время сложно. А придумав красивое лаконичное решение, можно уложиться всего в 10–15 минут. Именно под поиск таких изящных путей и заточены большинство условий: средний объем решения - 100-200 строк кода, хотя в некоторых случаях он может доходить до 300. В обычной жизни 300 строк не так уж много, но здесь у тебя есть всего пять часов на решение всех задач. Писать нужно быстро, а если в трех сотнях строк будет допущена ошибка - задача не пройдет, значит, все время на ее решение будет попросту потеряно. К тому же, чем длиннее код, тем труднее найти ошибку в распечатанной версии.
Другие турниры и тренировки
Денежные призы далеко не основная мотивация участников турниров. На фото: Иван Белоногов и Илья Збань - призеры VK Cup 2015 (источник - страница Ивана Белоногова). В 2017-м призером VK Cup стал третий участник чемпионской команды ИТМО Владимир Смыкалов.
Мы постоянно участвуем в индивидуальных турнирах - их проводится очень много. Например, соревнования на российском сайте Codeforces регулярно собирают по несколько тысяч человек, из которых россиян обычно около 20 %. Стандартный тур здесь состоит из пяти алгоритмических задач, которые нужно решить за два часа. Самое главное в сложившемся вокруг этого ресурса сообществе - личный рейтинг, рассчитанный по системе Эло, как в шахматах. Успешно выступая на турнирах, программисты получают очки - их определенное количество автоматически меняет цвет ника. Те, у кого ники красные, получают не только просьбы о помощи, но и предложения от работодателей. А главное, как любые спортсмены-чемпионы, пользуются всеобщим уважением - для многих участников «красный ник» сам по себе служит достаточным стимулом для борьбы.
Круче красных ников, только красные ники с первой черной буквой. 13 июля в двадцатке лучших на Codeforces было восемь россиян, по двое украинцев, поляков и китайцев и по одному представителю Швейцарии, Австралии, Кореи, США, Тайваня и Беларуси. При этом белорусский программист сейчас возглавляет рейтинг, хотя в принципе перестановки в таблице происходят постоянно.
Крупные соревнования проводят Mail.ru , Яндекс , Facebook , Google и другие компании. Например, в первом раунде текущего турнира Google Code Jam участвовало 20 тысяч человек. Тысяча лучших получили фирменные футболки, 25 - поедут на финал, который в этом году пройдет в Дублине.
Помимо Google Code Jam, Google проводил еще один турнир - Hash Code , финал которого в проходил в головном офисе компании. Участникам, в частности, выдавались планы зданий , которые нужно было максимально покрыть сетью Wi-Fi-точек, используя как можно меньше роутеров и проводов. Оптимального решения у такой задачи не существует, но решить ее лучше других, конечно, возможно.
Одним из зданий, в котором организаторы Google Hash Code предлагали расставить роутеры, была парижская Гранд-Опера.
Отдельный вид соревнований представляет AI Cup , где нужно написать программу искусственного интеллекта, способную играть против оригинальной программы, предоставленной организаторами в виде библиотеки. Игры создают специально для турниров, т. е. поиграть в них руками в принципе нельзя. Но сценарии подбирают так, чтобы писать для них стратегии было интересно.
В этом году игра была похожа на современные MOBA: решение должно было управлять командой из пяти волшебников, обеспечив между ними обмен командами с помощью кодовых слов.
Подобные соревнования постоянно проходят на французском сайте CodinGame . И приятно, что в турнирах AI мы добиваемся неплохих результатов, занимая места в первых двух двадцатках при полном отсутствии тренировок. Все-таки в спортивном программировании главный навык - сесть, подумать и написать код.
Школьная сборная США сезона 2017/18. Успеха в спортивном программировании в Америке в основном достигают молодые люди с азиатскими корнями.
Самыми загадочными соперникам кажутся программисты из Северной Кореи, которые в условиях ограниченного доступа к интернету все-таки тренируются и часто выступают довольно прилично. Правда, в этом году на финал в США они не приехали, а на Codeforces у них сложилась репутация читеров. В частности, северо-корейских участников онлайн-турниров обвиняли, что с одного аккаунта код пишут явно разные люди. А это строго запрещено правилами.
В этом году в десятку лучших на международной Олимпиаде вошла всего одна команда из Западной Европы - студенты Королевского технологического института из Стокгольма.
Успехи России выглядят вполне объяснимыми, поскольку здесь - и очень сильная математическая школа, и сложившаяся тусовка олимпиадников, готовая помочь начинающим. В России, помимо ИТМО, очень сильные команды представляют СПбГУ (чемпионы прошлого года), МГУ, московский Физтех, вузы Екатеринбурга и Саратова, хотя время от времени хорошие составы удается собрать и другим университетам.
На фото еще одна команда ИТМО: Артем Васильев и Бориса Минаев и Геннадий Короткевич - чемпионы мира 2015 года. Кубки Международной олимпиады по программированию не переходящие - теперь в ИТМО хранится уже семь.
Добавить метки
Российские студенты в седьмой раз подряд стали победителями чемпионата мира по программированию ACM ICPC в Пекине. С 2000 года это уже 13-я победа участников из РФ. Первое место заняла команда из Московского государственного университета (МГУ). На втором - Московский физико-технический институт (МФТИ), на третьем - Пекинский университет. Команда победителей получит денежное вознаграждение в $15 тыс. Ранее первые места на этих соревнованиях занимали команды Санкт-Петербургского госуниверситета (СПбГУ), Санкт-Петербургского университета информационных технологий, механики и оптики (ИТМО) и Саратовского государственного университета. Впрочем, в экспертном сообществе не склонны переоценивать успехи российских программистов, напоминая о проблемах в общем уровне подготовки учащихся.
В Пекине завершился финал чемпионата мира по программированию ACM ICPC - крупнейшей студенческой олимпиады в этой дисциплине. В финале первенства в этом году приняли участие 140 команд из 51 страны. От России выступали 11 команд, представляющих Московский физико-технический университет, Московский государственный университет, Университет ИТМО (Санкт-Петербург), Санкт-Петербургский государственный университет, Высшую школу экономики, Московский авиационный институт, Новосибирский государственный университет, Пермский государственный университет, Саратовский государственный университет, Академический университет (Санкт-Петербург) и Уральский федеральный университет (Екатеринбург).
Российские участники завоевали кубок мира и четыре медали из 13 - больше, чем любая другая страна.
Команды из Китая и США получили по три медали, по одной - у Японии, Кореи и Литвы.
Кубок мира впервые выиграла команда МГУ Red Panda, решив 9 задач из 12 предложенных. «Наши ребята - лучшие! Гордимся»,- говорится в сообщении пресс-службы МГУ. «Это первая абсолютная победа МГУ в ICPC»,- сообщили “Ъ” в университете. В состав команды (традиционно она состоит из трех человек) входят Михаил Ипатов (студент мехмата), Владислав Макеев и Григорий Резников (факультет вычислительной математики и кибернетики). Тренером команды является завкафедрой информатики специализированного учебно-научного центра (СУНЦ) имени А. Н. Колмогорова МГУ Елена Андреева.
«Команды МГУ участвуют в студенческом командном чемпионате мира по программированию более 20 лет,- заявила госпожа Андреева после подведения итогов первенства.- Многие из них завоевывали медали чемпионата, несколько раз останавливались в шаге от победы, занимая второе место. В этом году впервые наша команда завоевала титул чемпиона мира, опередив как сильнейшие российские команды МФТИ и ИТМО, так и лучшие зарубежные - команды университетов Пекина, Сеула и Токио».
Чемпионат по программированию проводится с 1970-х годов, с 2000 года в нем начали побеждать команды российских вузов: первыми тогда стали студенты СПбГУ.
С 2012 года в этой олимпиаде побеждают только российские команды.
Рекордсмен по количеству побед среди российских команд - Университет ИТМО (занимал первое место семь раз, в том числе в 2017 году). В этом году команда Университета ИТМО опустилась на девятую позицию, решив 7 задач из 12. При этом ИТМО остался третьим среди российских вузов-участников олимпиады. «Программирование становится настоящим интеллектуальным спортом будущего, не менее интересным, чем, например, шахматы, и в данной дисциплине ребятам из России нет равных»,- прокомментировал успехи российских студентов вице-президент Российского союза ректоров, ректор Университета ИТМО Владимир Васильев.
Кроме команды МГУ среди самых лучших оказались команды МФТИ (второе место) и университетов Пекина и Токио, решившие 8 из 12 задач и удостоенные золотых медалей.
С результатом 7 из 12 соревнования завершили Сеульский национальный университет, университет Нового Южного Уэльса, университет Цинхуа, Шанхайский университет, ИТМО, Массачусетский технологический институт, университет Вильнюса и Уральский федеральный университет.
«Команда физтеха показала высокий результат, они уверенно шли к победе весь год, показали лучший результат за всю историю участия МФТИ в соревнованиях, с чем можно поздравить команду Cryptozoology! Мы гордимся нашими студентами»,- сообщил Алексей Малеев, руководитель команды, директор Центра ИТ-образования МФТИ. «Москва имеет самое большое представительство среди всех городов мира - сразу четыре университета (среди 13 лучших.- “Ъ” ) отстаивают честь страны,- отметил господин Малеев.- Более того, 10 из 13 прошли школу Moscow Workshops ICPC на базе МФТИ». «Это доказывает, что программистское образование у нас в стране - одно из лучших в мире. Поздравляем команду МФТИ и всех российских программистов!» - подчеркнул ректор МФТИ Николай Кудрявцев.
В ICPC соревнуются команды из трех студентов не старше 25 лет. К участию в чемпионате не допускаются студенты, дважды участвовавшие в мировом финале. В распоряжении команды - всего один компьютер, поэтому помимо логики и умения работать в жестких временных рамках конкурсанты должны проявить навыки взаимодействия в команде и грамотно распределить роли. Побеждает команда, которая правильно решила наибольшее количество задач и при этом показала наилучшее время; также учитывается количество сделанных попыток, или «посылок» (так называют решение задачи, отправленное на проверку на тестирующий сервер).
Все призеры ICPC получают денежную премию: команда чемпионов - $15 тыс.; команды, завоевавшие золотые медали,- по $7,5 тыс.; серебряные призеры - по $6 тыс., а команды, взявшие бронзу,- по $3 тыс.
Победу российских студентов не стоит переоценивать, считает главный научный сотрудник Института проблем информатики РАН Константин Колин. «Выиграли и выиграли, речь идет о единичном успехе: это элита, которую готовят в ведущих вузах, а нужно посмотреть на общий уровень подготовки школьников и студентов»,- сказал эксперт в беседе с “Ъ”. По его словам, социологические опросы, проведенные среди московских школьников в прошлом и нынешнем годах, показали, что «34% школьников считают, что солнце вращается вокруг Земли». «Маразм крепчал, а правительством принята программа ""Цифровая экономика"", которая требует высококвалифицированных специалистов. Для того чтобы их подготовить, необходима революция в образовании, и начинать нужно с педагогов. Мы много об этом говорим, но пока, к сожалению, в Министерстве образования нас не слышат»,- заключил эксперт. В Минобрнауки победу российских студентов на международной олимпиаде “Ъ” оперативно прокомментировать не смогли.
Анна Макеева, Валерия Мишина
Много побед не бывает! Каждая следующая еще слаще предыдущей. Команда петербургского университета информационных технологий, механики и оптики завоевала главный кубок чемпионата мира по программированию ACM ICPC 2017 года. Это уже седьмая победа ИТМО в самом престижном интеллектуальном турнире молодых программистов.
Битва сильнейших
Соревнование лучших студентов-программистов из более ста стран мира началось 20 мая в Рапид-сити, что в Южной Дакоте, США . В нем участвовали 128 команд, 13 из них представляли Россию , три - Санкт-Петербург . Финал ждали не только команды, но и болельщики, которые следили за прямой трансляцией. Чтобы стать чемпионами мира, молодые программисты должны были правильно решить как можно больше из 12 поставленных перед ними задач.
Битва выдалась непростой. Команды буквально наступали друг другу на пятки. Спустя 40 минут соревнований будущие чемпионы решили только три задачи и были лишь на девятом месте в турнирной таблице. Но они верили. Нет. Они знали, что могут лучше и быстрее. Еще через 20 минут команда ИТМО решила уже пять задач и обогнала всех соперников. После восьми задач лидер сменился. Но девятая снова вернула питерцев на первое место. После десяти решенных задач команды замерли в ожидании результатов.
В ожидании результатов. Фото: Кафедра КТ Университета ИТМО "ВКонтакте"
Семикратные чемпионы
Только что стали известны результаты студенческого чемпионата по спортивному программированию ACM ACPC-2017. Первое место заняла команда Университета ИТМО, добавив к шести победам еще одну, - огласили радостную новость на официальной страничеке вуза в соцсети в 01:36 по Москве .
Программисты из Университета ИТМО подтвердили свой мировой рекорд, и победный кубок самого престижного студенческого турнира среди программистов снова едет в Петербург.
Сборная вуза смогла правильно решить 10 из 12 задач, потратив на это наименьшее количество времени. Именно время решения задач и меньшее число неудачных попыток их сдачи обеспечило команде седьмой кубок ACM ICPC, - сообщает пресс-служба ИТМО.
Вот они, герои!
Седьмую победу Университету ИТМО на ACM ICPC, решив 10 из 12 задач быстрее и грамотнее всех сопреников, принесли студенты кафедры компьютерных технологий Иван Белоногов, Илья Збань и Владимир Смыкалов. Главный тренер команды победителей - доцент кафедры компьютерных технологий, кандидат технических наук Андрей Станкевич .
