Чемпионат по спортивному программированию. Российские программисты стали чемпионами мира, обойдя Гарвард и MIT
ВАШИНГТОН, 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 году в Пекине (КНР).
В Рапид-Сити (США) 24 мая состоялся финал чемпионата мира по программированию ACM-ICPC 2017 . Абсолютными чемпионами стала команда Санкт-Петербургского научно-исследовательского университета информационных технологий, механики и оптики (СПбНИУ ИТМО), решившая 10 задач из 12 быстрее соперников. Петербургский вуз установил новый рекорд в истории соревнования: сборные Университета ИТМО в седьмой раз стали его победителями, что еще не удавалось ни одному вузу в мире.
И кто наши герои?
Команда победителей состояла из трёх студентов кафедры компьютерных технологий , Владимира Смыкалова, Ивана Белоногова и Ильи Збаня. Главным тренером команды выступил доцент кафедры компьютерных технологий, кандидат технических наук Андрей Станкевич , который в прошлом году получил награду ACM ICPC Senior Coach Award за то, что в течение 15 лет его подопечные проходили в финал конкурса.
В число золотых призёров ACM-ICPC 2017 вошли СПбГУ (прошлогодний победитель), Варшавский и Сеульский университеты. Серебряные медали ACM-ICPC 2017 получили команды Фуданьского университета, Пекинского университета, Университета Синьхуа и МФТИ. «Бронзу» взяли представители Токийского университета, шведского Королевского технологического института, Уральского федерального университета и Корейского института передовых технологий.
Всего в этом году в финале ACM-ICPC 2017 участвовали 133 команды из всех регионов мира. Само состязание проходило уже в 41 раз.
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 2017 года. Это уже седьмая победа ИТМО в самом престижном интеллектуальном турнире молодых программистов.
Битва сильнейших
Соревнование лучших студентов-программистов из более ста стран мира началось 20 мая в Рапид-сити, что в Южной Дакоте, США . В нем участвовали 128 команд, 13 из них представляли Россию , три - Санкт-Петербург . Финал ждали не только команды, но и болельщики, которые следили за прямой трансляцией. Чтобы стать чемпионами мира, молодые программисты должны были правильно решить как можно больше из 12 поставленных перед ними задач.
Битва выдалась непростой. Команды буквально наступали друг другу на пятки. Спустя 40 минут соревнований будущие чемпионы решили только три задачи и были лишь на девятом месте в турнирной таблице. Но они верили. Нет. Они знали, что могут лучше и быстрее. Еще через 20 минут команда ИТМО решила уже пять задач и обогнала всех соперников. После восьми задач лидер сменился. Но девятая снова вернула питерцев на первое место. После десяти решенных задач команды замерли в ожидании результатов.
В ожидании результатов. Фото: Кафедра КТ Университета ИТМО "ВКонтакте"
Семикратные чемпионы
Только что стали известны результаты студенческого чемпионата по спортивному программированию ACM ACPC-2017. Первое место заняла команда Университета ИТМО, добавив к шести победам еще одну, - огласили радостную новость на официальной страничеке вуза в соцсети в 01:36 по Москве .
Программисты из Университета ИТМО подтвердили свой мировой рекорд, и победный кубок самого престижного студенческого турнира среди программистов снова едет в Петербург.
Сборная вуза смогла правильно решить 10 из 12 задач, потратив на это наименьшее количество времени. Именно время решения задач и меньшее число неудачных попыток их сдачи обеспечило команде седьмой кубок ACM ICPC, - сообщает пресс-служба ИТМО.
Вот они, герои!
Седьмую победу Университету ИТМО на ACM ICPC, решив 10 из 12 задач быстрее и грамотнее всех сопреников, принесли студенты кафедры компьютерных технологий Иван Белоногов, Илья Збань и Владимир Смыкалов. Главный тренер команды победителей - доцент кафедры компьютерных технологий, кандидат технических наук Андрей Станкевич .
Российские студенты выиграли чемпионат мира по программированию April 20th, 2018
Никто не будет спорить с тем, что в России самая сильная школа программистов. Не даром наши хакеры даже Президента США выбрали и наши программисты написали мессенджер, который весь Роскомнадзор до сих пор заблокировать не может.
Ну и вот вам закономерная новость. В Пекине завершился финал чемпионата мира по программированию ACM ICPC. Российские вузы традиционно показали высокие результаты: команда МФТИ взяла золото и заняла второе место, команда МГУ — первое. Команды Университета ИТМО и Уральского федерального университета получили бронзовые медали.
Все российские команды завоевали 4 медали из 13 — это больше, чем у других стран. У США и Китая — по 3. По одной у Японии, Кореи и Литвы.
ACM ICPC — один из главных всемирных студенческих чемпионатов по программированию. Российские программисты лидируют на мировом первенстве уже много лет. С 2000 года команды из нашей страны побеждают в ICPC уже в 13 раз.
«Российские участники завоевали кубок мира и четыре медали из 13 — больше, чем остальные страны-участники: команды из Китая и США получили по три медали, по одной — у Японии, Южной Кореи и Литвы. Первое место и кубок чемпионов завоевал МГУ. „Золото“, помимо МГУ, получили МФТИ, Пекинский университет и Токийский университет. „Серебро“ досталось Сеульскому университету, Университету Южного Уэльса, Университету Синьхуа и Шанхайскому университету Джао-тонг. „Бронзу“ завоевали Университет ИТМО, Университет Центральной Флориды, Массачусетский университет технологий, Вильнюсский университет и УрФУ», — отметили в пресс-службе МФТИ.
Чемпионат уходит своими корнями в соревнование, проводившееся в Техасском университете в 1970-х годах. Ныне чемпионат проводится ежегодно под эгидой ассоциации вычислительной техники (ACM). В разное время спонсорами соревнований становились такие компании, как Apple, AT&T, Microsoft и IBM.
Каждая команда состоит из трёх человек. К участию допускаются студенты высших учебных заведений, а также аспиранты первого года обучения. Студенты, дважды участвовавшие в финальной стадии олимпиады или пятикратно принимавшие участие в региональном отборе, не допускаются к участию. Существует и ограничение по возрасту: участники старше 24 лет не допускаются.
Тур олимпиады происходит следующим образом: каждой команде на пять часов выдаётся компьютер и от восьми до двенадцати задач, условия которых написаны на английском языке. Интересно, что команды пишут решения не просто текстом, а на языках программирования C, C++ или Java и посылают их на тестирующий сервер.
Команды из РФ участвуют в ICPC с 1993 года. Шесть лет, с 2012 по 2017 год, кубок мира передавали друг другу две петербургские команды — СПбГУ и Университет ИТМО, обладающий мировым рекордом по количеству чемпионских титулов: на счету у него семь кубков. У ближайших зарубежных соперников, американского Стэнфорда и китайского Университета Джао Тонг — всего по три победы.
Все призеры ICPC получают денежную премию: команда чемпионов — $15 тыс.; команды, завоевавшие золотые медали — по $7,5 тыс.; серебряные призеры — по $6 тыс., а команды, взявшие бронзу, — по $3 тыс.
источники
