Олимпийский код: школьники, которые знают больше любого взрослого
Олимпиадники, которые жили в европейской части СССР, летели в Москву в не менее легендарный интернат СУНЦ при Московском университете. Система, запущенная в СССР в 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, в который вошли интенсивная программа с тренерами чемпионов, а потом и чемпионаты, причем не только по спортивному программированию, но и по востребованной сейчас области искусственного интеллекта.
