Олимпийский код: школьники, которые знают больше любого взрослого

Ранним августовским утром 1982 года я с фанерным чемоданчиком ждал на остановке у аэропорта Толмачево редкий автобус, отходящий в новосибирский Академгородок. Это была завершающая часть моего почти недельного приключения – путешествия из арктического чукотского городка Певек: я преодолевал это немалое расстояние на самолетах Ил-14 и новеньком Ту-154, с ночевкой на полу магаданского аэропорта. Сотовых не было, и в местах своих остановок я давал маме краткие телеграммы: «Порядок», так как платить надо было за каждое слово. Я был не один: из разных отдаленных уголков страны в Академгородок слетались в Летнюю школу победители многочисленных областных и республиканских школьных олимпиад, чтобы пройти последний и самый важный этап – зачисление в физико-математическую школу-интернат.
Олимпийский код: школьники, которые знают больше любого взрослого

Олимпиадники, которые жили в европейской части СССР, летели в Москву в не менее легендарный интернат СУНЦ при Московском университете. Система, запущенная в СССР в 1930-е го­ды, работала безотказно, поставляя стране научные кадры мирового уровня. И, что невероятно, работает до сих пор – достаточно проверить количество золотых медалей, которые привозят наши школьники и студенты с мировых чемпионатов и олимпиад.

История

«Олимпиады для учащейся молодежи» еще в XIX веке проводило Астрономическое общество Российской империи. Первый очный математический конкурс для выпускников лицеев состоялся в Румынии в 1886 году, а первая математическая олимпиада прошла в Венгрии по инициативе Венгерского физико-математического общества в 1894-м, что на два года раньше первых современных Олимпийских игр в Афинах. 

В СССР первая математическая олимпиада состоялась в Ленинграде в 1934-м, а в следующем году уже и в Москве. Физические и химические стартовали в 1938-м. А уже к 1967 году была выстроена четкая система Всесоюзных олимпиад школьников по физике, математике и химии, дающих равные шансы талантливым детям из самых отдаленных уголков страны, – я сам яркий пример этой системы.

Школьные олимпийцы

Мы сидим в офисе Алексея Малеева, проректора по международным программам и цифровым инновациям легендарного МФТИ, обсуждая одно из самых крутых событий лета – финал чемпионата мира по программированию среди студентов ICPC в Москве и вообще олимпиадное школьное и студенческое движение в мире. Первая Всесоюзная олимпиада по информатике прошла в 1988 году в Сверд­ловске. Почему именно там? На тот момент свердловские и областные школы получили персональные компьютеры «Роботрон-1715», а также была разработана программа преподавания информатики. Сейчас компьютеры есть почти везде, и олимпиадное движение в этой области поставлено на поток. Хороший поток.

Спортивное программирование
Новые шахматы
Спортивное программирование не зря называют новыми шахматами. Это спорт с четкими правилами, изнурительными тренировками, спортивными сборами, целыми тренерскими командами и своими чемпионами.

Школьные олимпиады по информатике похожи на физико-математические с той разницей, что решаются другие задачи – по программированию. Требуется написать компилируемый код и отправить его в автоматическую тестирующую систему, которая сильно облегчает работу жюри. Традиционная задача – придумать алгоритм, написать программу, сгенерировать код, загрузить входные данные и получить на выходе результат, который сравнивается с правильными ответами. Все делается в автоматическом режиме, поэтому какие-то манипуляции и подтасовки практически исключены. Что измеряется, помимо правильности результатов? Время выполнения алгоритма, то есть время работы программы. Стандартное ограничение – несколько секунд, ведь современные компьютеры очень мощные, и за несколько секунд можно много чего сделать. Но если алгоритм примитивный, например, простой перебор, то при больших входных данных программа в нужное время не уложится. Поэтому алгоритм должен быть достаточно эффективным. Также бывают ограничения на использование оперативной памяти.

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

Сейчас Всероссийская олимпиада для школьников, преемница Всесоюзной, проходит в четыре этапа. Первый этап – в каждой школе страны. Второй – муниципальный, или районный, третий – региональный, в каждом регионе РФ, и только лучших приглашают на заключительный, четвертый этап. Каждый раз он проходит в новом месте. В этом году Москва будет принимать заключительный этап Всероссийской олимпиады школьников по информатике – МФТИ и фирма «1С», базовая кафедра МФТИ. В прошлом году заключительный этап прошел в Университете Иннополиса. Два года назад это был Ульяновск.

Алексей Малеев
«Оказалось, что чемпионат – удачный критерий измерения и для университетов, и для компаний. Для первых – показатель эффективности их работы, для вторых – идеальный подбор высококвалифицированных кадров. Несмотря на то что часто на пьедестал выходят команды топовых мировых университетов, если очень захотеть, можно попасть в мировую элиту из любой точки земного шара: онлайн-контента хоть отбавляй. А опыт живого общения вполне заменяют короткие очные программы, на которые съезжаются спортсмены-программисты со всего мира». Алексей Малеев, проректор по международным программам и цифровым инновациям МФТИ.

Новые шахматы

На международном уровне спортивное программирование – спорт высоких достижений, сравнимый, наверное, с шахматами. Это огромная ответственность, ведь школьники представляют страну, и их медали ценятся не меньше олимпийских.

Главное требование к участникам – дети должны учиться в школах. И тут получается несоответствие – если в наших и китайских школах дети учатся до 17 лет, то в США и некоторых странах Западной Европы этот возраст может доходить до 21 года. Но если на олимпиадах, например, по физике и математике это дает некоторое преимущество (которое, кстати, не особо помогает нашим конкурентам), то в программировании это не совсем так. Дело в том, что в информатике пока нет привязки к школьной программе, обучение ей больше похоже на творчество – есть привязка к математике, но она не такая сильная, но очень много логики и самого навыка программирования. Нужно чтобы преподаватель мог зажечь, замотивировать, довести ученика до какого-то уровня, когда бы он уже смог сам. Тут должно повезти с преподавателем. Хотя современные дети много чего уже узнают сами. Ездят по летним школам и там набираются друг у друга опыта.

У нас есть Егор Лифарь – уникальный ученик. Москвич, учится в школе «Интеллектуал», его школьная учительница и олимпиадный тренер – Елена Владимировна Андреева. Он первую медаль привез семиклассником. Закончил седьмой класс, прошел в российскую сборную и привез медаль. А потом и в восьмом, и в девятом классе привез медаль. Три медали в копилке и еще два года впереди.

Кубок

Олимпийские игры

Но главными все же считаются соревнования среди студенческих команд. В индустрии IT огромный дефицит кадров, и почти каждый информационный гигант устраивает свои соревнования. Но главными играми негласно считается Международный командный студенческий чемпионат по программированию (ICPC), который начинался как соревнования в Техасском университете США в 1970-е годы. Сперва он был очень локальным: сначала проходил в одном университете, потом в штате и в 1989 году стал международным. Сегодня это самый престижный и популярный конкурс: за всю его историю в нем участвовали студенты из 3233 университетов из 110 стран мира.

В отличие от школьных олимпиад это командный вид спорта – от каждого университета по три человека в команде. Тур длится пять часов, дают чуть больше задач – от 10 до 12, точно такая же, как в школьных олимпиадах, тестирующая система. Но более строго подходят к оценке. Если в школьных соревнованиях есть баллы, то в студенческом задача либо решена, либо не решена. Выше оказывается тот, кто решил большее количество задач, а среди одинакового количества задач выше тот, кто быстрее сделал. Есть ограничение по скорости выполнения кода, уложился – все нормально, нет – переделывай задание.

Штрафные баллы

Помимо зачтенных задач командам начисляются штрафные баллы. Например, если команда решила задачу за 35 минут от начала тура, она получает плюсик по этой задаче и плюс 35 очков к своему штрафному счетчику. Если еще одна задача решается, то добавляется плюс к количеству минут от начала соревнования. Например, если команда справляется с задачей на 144-й минуте, то плюс 144 балла. Чем меньше значение на счетчике команды, тем выше она в рейтинге. Это очень важно. Основная борьба идет среди тех, у кого одинаковое количество решенных задач. 

Спортивное программирование

Команды

Еще одно отличие от школьных олимпиад – команда привязана не к стране, а к университету, который ее выставляет. В финал выходит только одна команда от одного университета. От одной страны может быть сколь угодно много команд. От России в этом году в финале будет десять команд. Отбор в финал идет на зональных конкурсах – мир поделен на восемь больших зон, и у каждого зонального турнира есть своя квота в финале. Россия относится к большому региональному полуфиналу, который называется Northern Eurasia Programming Contest (это весь бывший СССР, кроме Молдавии, Украины и Эстонии). Штаб нашего зонального полуфинала исторически вот уже 20 лет расположен при университете ИТМО в Санкт-Петербурге. Когда российские студенты первый раз поехали на чемпионат в сезоне 1993/1994, то они сразу попали в Европу: никаких отборочных соревнований в нашей стране вообще не было. А сейчас только в Москве 433 команды участвовали в квалификационном туре Moscow Programming Contest, в России проходят и полуфиналы, и уже четвертьфиналы.

Московский регион координирует МФТИ, и это отдельный четвертьфинал, а всего по стране сейчас проводится 15 четвертьфиналов, и некоторые из них охватывают по несколько федеральных округов страны. Москва организует самые большие российские соревнования по информатике: уже два года подряд они попадают в Книгу рекордов России и Реестр рекордов России. Только в одной Москве этой осенью в один день было суммарно 2284 студента и школьника в одной тестирующей системе: студенты из 36 вузов на площадках 18 университетов и московские школьники из 37 школ, которые писали отборочный тур Московской командной олимпиады школьников по программированию на тех же задачах. Потом лучшие из студентов вышли в финал Moscow Programming Contest и уже оттуда лучшие поехали на полуфинал. Из России на чемпионат мира отобрали 10 университетов: три из Санкт-Петербурга – СПбГУ, Университет ИТМО, филиал ВШЭ; московские – МФТИ, ВШЭ, МГУ; Нижегородский ГУ, Саратовский ГУ, два из Татарстана – Казанский федеральный университет и Университет Иннополис. Больше, чем от нас, только команд из Китая и США, но у США особые условия, так как чемпионат родился в Америке, но это никак не сказывается на конечном результате – последние восемь лет подряд абсолютными чемпионами становятся русские студенты. 

Спортивное программирование
Кубок
Главная награда в спортивном программировании – чемпионский кубок ICPC, аналог кубка Стенли в хоккее. На нем выгравированы все победители, но, в отличие от кубка Стенли, каждый раз он остается в команде-победителе, а для следующего чемпионата делают новый. В Россию кубок уезжал восемь последних лет: шесть раз в Санкт-Петербург и два – в Москву.

Награждение

На школьных и студенческих чемпионатах разная система награждений. У школьников есть правило: медали получает половина от участников финала. И внутри этих 50% 1/6 часть получает золотые медали, 2/6 – серебряные и 3/6 – бронзовые. В этом году наша команда по информатике показала необычайный результат: все четыре участника приехали из Баку с золотыми медалями. Ни одной другой стране не удалось это повторить. Команды Китая и США наступали на пятки, но у них были три золотые медали и одна серебряная.

У студентов все жестче: награждаются 12 лучших команд – четыре золота, четыре серебра и четыре бронзы. И из первой четверки есть абсолютный чемпион, который и получает кубок – самый главный приз. Такая система работает с 2000 года, и за это время команды США завоевали 11 золотых медалей, вся Европа – 9, Китай – 14, а русские команды привезли 33 золотые медали. Это о качестве образования.

Распределение ролей

Компьютер один, за ним самый лучший кодер, хотя все могут друг друга легко подменять: все участники лучшие в мире. Кодер важен на старте, он способен очень быстро написать простые задачи. Второй участник, как правило, самый сильный в математике. Он может вообще за пять часов не сесть за клавиатуру, но он придумывает решения для сложных задач. Есть задачи простые – читаешь условия, и сразу понятно, каким алгоритмом надо воспользоваться; есть такие, которые и за все время сложно решить. 

Третий, как правило, совмещает эти две специализации и является капитаном, который должен принимать важные стратегические и тактические решения. Например, самое сложное: задача, кажется, почти решена, а все не получается. Что значит не получается? Команда отправляет код на сервер и мгновенно получает ответ: правильно/неправильно. Капитан должен выбрать правильную стратегию: продолжать искать верное решение или пропустить задачу и перейти к следующей. Редко кто решает все задачи: жюри их подбирает таким образом, чтобы одну-две задачи не решили бы и чемпионы. Высший пилотаж – когда чемпионы решили не все задачи, а другие команды набрали суммарно меньше задач, но вот эти конкретно решили. Но такое бывает редко. Одна-две задачи так и остаются никем не открытыми. 

Спортивное программирование

Соревнования

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

Если с комментариями, например, в футболе все понятно, то комментирование ICPC – высший интеллектуальный пилотаж. Чтобы просто выводить для зрителей код команд, требуется очень большой порог входа для понимания, ведь это даже не шахматы. Поэтому аналитический штаб, человек 20–25, просматривает код, который пишут студенты, и обработанную информацию выдает комментаторам. Например, вот ребята решили использовать такой алгоритм. А здесь они сделали ошибку. Если в этой строчке значок «больше» на «больше или равно» исправить, то все у них бы заработало. А дальше уже на первый план выходит искусство самого комментатора. 

Финал

В преддверии финала физтех организовал открытый онлайн-курс «Быстрый старт в спортивное программирование», который собрал более 6 тысяч участников. Это стало частью всероссийского проекта RuCode, в который вошли интенсивная программа с тренерами чемпионов, а потом и чемпионаты, причем не только по спортивному программированию, но и по востребованной сейчас области искусственного интеллекта.