«За время, которое обычный программист тратит на понимание задачи, спортивный ее уже решает»

В сентябре российские школьники привезли две золотые и две серебряные медали с Международной олимпиады по информатике IOI 2018 (International Olympiad in Informatics). Результат неплохой, и это неудивительно: нашим командам это не впервой. Россия держится в пятерке самых успешных команд по числу и достоинству медалей. IOI – вершина олимпиадной цепочки, которая начинается со школьного этапа Всероссийской олимпиады. Как она устроена, кто и как пробивается к вершинам и как России удалось занять вторую строчку в общем количестве золотых медалей после Китая, читайте в материале Indicator.Ru.

Что такое спортивное программирование

Олимпиады по информатике для школьников — первый шаг в мир спортивного программирования. Главное его отличие от обычного состоит в том, что здесь нужно найти алгоритм, полностью или наиболее эффективно решающий задачу, за ограниченное время. И, разумеется, сделать это лучше соперников.

«За время, которое обычный программист тратит на понимание задачи, спортивный программист ее уже решает», — комментирует технический координатор сборов перед IOI 2018 года, главный судья сборов по программированию Moscow Workshops ICPC Олег Христенко.

В обычном программировании эффективность кода не настолько критична, а задачи часто нечетко сформулированы и предполагают то самое «приближенное» решение. В спортивном программировании задачи, напротив, формулируются математически точно, у них есть строгие рамки и множество переменных.

Как устроен мир спортивного программирования

Путь школьника в спортивное программирование начинается с этапов Всероссийской олимпиады школьников: школьного, муниципального, областного и заключительного. По результатам Всероса и с учетом других заслуг Центральная предметно-методическая комиссия Министерства просвещения отбирает около 20 человек в национальную сборную для поездки на Международную олимпиаду — IOI. Кроме того, школьники участвуют во Всероссийской командной олимпиаде по программированию (ВКОШП) и в ряде перечневых олимпиад таких, как олимпиада «Ломоносов», Открытая олимпиада школьников по программированию, «Когнитивные технологии», «Технокубок» и другие. Перечневые олимпиады бывают трех уровней. Из них только первый обеспечивает поступление в определенные вузы без экзаменов или 100 баллов по информатике за ЕГЭ. Олимпиады второго уровня дают 100 баллов по ЕГЭ, но только в определенных вузах. Льготы по результатам олимпиад третьего уровня каждый вуз определяет сам.

Многие продолжают занятия спортивным программированием и в студенчестве. В самом масштабном соревновании по олимпиадному программированию для студентов — чемпионате мира International Collegiate Programming Contest (ICPC) — за год на отборочных этапах участвует 50 тысяч студентов со всего мира. В отличие от Всероссийской олимпиады и IOI, здесь ребята соревнуются не индивидуально, а в составе команд из трех человек. По правилам ICPC проходят и локальные соревнования при университетах всего мира.

Помимо вузовских олимпиад, существуют популярные онлайн-сообщества с регулярными соревнованиями, в которых участники в личном зачете борются за место в рейтинге. Например, TopCoder или российская платформа Cofeforces.

Свои чемпионаты устраивают и крупные IT-компании. Чаще всего в них предлагается решить «приближенные» задачи. Как правило, у них нет конкретного решения. Участники этих соревнований должны разработать некий продукт, который ближе всего подошел бы к идеальному решению этой проблемы. Обычно такие соревнования проходят в несколько отборочных туров в режиме онлайн, а в финале лучших собирают на очной площадке.

Экскурс в историю

Первые соревнования по спортивному программированию проходили среди студентов. Чемпионат ICPC в первый раз был органиован в 1977 году в Атланте (США). Он начинался как соревнование между четырьмя американскими университетами при поддержке ассоциации вычислительной техники ACM и только в 1990 году вышел на международный уровень.

Идею организовать соревнование среди школьников на двадцать четвертой Генеральной конференции ЮНЕСКО предложил болгарский профессор Благовест Сендов. В болгарском городе Правец, и состоялась первая олимпиада. В ней приняли участие 46 участников из 13 стран. Лучший результат и в индивидуальном, и в командном зачете показала принимающая страна.

С 1989 года Международная олимпиада по информатике IOI проходит ежегодно. В 1991 году соревнования состоялись в СССР, в Минске, и после этого Россия принимала IOI единственный раз – в 2016 году. Делегатов со всего мира встречали в Татарстане, в Казанском федеральном университете. Тогда России, как принимающей стороне, разрешалось выставить на соревнования не одну, а сразу две команды – одна соревновалась «в зачет», вторая – «не в зачет». Наши школьники выиграли три золотые, четыре серебряные и одну бронзовую медали и в итоге заняли второе место после Китая.

Шансов на то, что Россия снова примет IOI немного, но такие случаи были — дважды проводилась олимпиада в Болгарии и Греции. Всего принимали у себя олимпиаду 28 стран.

Как устроена IOI

От каждой страны на IOI отправляется команда из четырех школьников, которых каждая страна выбирает сама. В России — по результатам заключительного этапа Всероссийской олимпиады и решению специальной комиссии Министерства просвещения. Соревнования проводятся в два дня. В каждый из них ребятам дается пять часов на решение трех алгоритмических задач. Чтобы участники освоились и познакомились с правилами, за день до начала олимпиады они решают двухчасовой пробный тур по задачам, которые известны заранее.

Олимпиада проходит на английском языке, но по заявке участников им могут положить в конверт с английским заданием еще и версию на их родном языке. Решать задачи олимпиады можно на любом из трех языков программирования: C++, Pascal или Java. Каждую задачу можно «сабмитить», то есть посылать ее решение в систему, максимум 50 раз. В системе ребята сразу видят статус своего сабмита — прошло решение или нет. Программа выдает им короткий автоматический ответ о наличии ошибок, и участники могут их исправить. На количество полученных баллов влияет способ решения задачи и количество потраченного на это времени. Из нововведений этого года – новые рекомендации по подаче уточняющих вопросов к задачам. Во время соревнования участник может попросить пояснения задачи от организаторов и получить ответ в формате «да», «нет», «без комментариев», «ответ есть в условии задачи» или «invalid question». Это значит, что вопрос надо переформулировать.

Кроме школьников на IOI едут руководитель команды, заместители руководителя (обычно это тренеры) и гости. Для всех участников делегации, кроме участников сборной, объявляется «карантин» с вечера перед первым туром и до его окончания, и с вечера перед вторым туром до его завершения. В это время они не могут контактировать со школьниками, потому что делегатам накануне двух туров показывают задачи олимпиады для перевода на родной язык участников. Переводом, который выполнила российская делегация, в этом году пользовались десять команд других стран. Кстати, переводы задач на разные языки можно посмотреть на сайте организатора.

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

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

Руководитель национальной сборной на IOI 2018, проректор МФТИ Алексей Малеев поясняет, что соотношение медалей помогает оценить распределение сил между странами год от года. А сравнение количества баллов картину не проясняет: «По баллам результаты сравнивать сложно, каждый раз новые задачи. Если дать легкие задачи, значит будет в среднем больше набрано баллов, если сложные – меньше».

О задачах олимпиады

Задачи для олимпиады специальному международному жюри предлагают программисты из разных стран. Лучшие из них отбираются для олимпиады. Оргкомитет, как правило, не говорит заранее, сколько он будет платить за такие задачи и будет ли вообще, все это решается в частном порядке.

Одну из задач первого тура подготовил россиянин Михаил Пядеркин, который сам был медалистом IOI и двукратным вице-чемпионом мира в командных студенческих соревнованиях по программированию ICPC. В его задаче школьникам нужно было написать программу, которая бы рассаживала гостей в помещении в определенном порядке.

В каждой задаче на IOI выделены подзадачи, за решение которых можно набрать баллы, даже если школьник не справился с задачей целиком. Об этом рассказывает Олег Христенко: «На IOI решение задачи оценивается в баллах от 0 до 100. Баллы выставляются системой по результатам запуска программы участника на тестах. В обычных задачах оценка за каждый тест — "верно" или "неверно". Полный балл выставляется за прохождение всех тестов. За прохождение определенных групп тестов, обычно соответствующих более простым подзадачам, выставляются частичные баллы».

При этом так называемые оптимизационные задачи оцениваются по-другому: «Там результат проверки задачи на каждом отдельном тесте приносит какие-то баллы, например, от 1 до 100, а итоговый балл за задачу вычисляется по разным схемам: например, в каких-то задачах он равен среднему баллу за все тесты, в каких-то — наименьшему из всех. Могут быть и другие схемы — это все зависит от изобретательности авторов».

Христенко отметил, что на школьной международной олимпиаде по информатике задачи более разнообразные, чем на студенческой: «Бывают интересные задачи с открытыми тестами, задачи на encoder-decoder, когда одна и та же программа участника должна работать в двух режимах».

Как это было в 2018 году

Нынешняя олимпиада в Японии стала тридцатой. Она проходила в Цукубе, научном городке вблизи Токио, с 1 по 8 сентября 2018. В ней приняли участие 335 участников из 87 стран. Абсолютный победитель IOI этого года, член сборной США Бенджамин Ци был единственным среди участников олимпиады, кто носит титул «Легендарный гроссмейстер» в одном из самых популярных сообществ олимпиадных программистов Codeforces. Это означает, что он входит в число 19 программистов, которые набрали на Codeforces более 3000 баллов в регулярных соревнованиях. Сейчас Бенджамин Ци — восьмой в этом рейтинге.

В российскую сборную вошли выпускник Общеобразовательной школы-интерната «Лицей имени Н.И. Лобачевского» КФУ Рамазан Рахматуллин, 11-классник московской школы-интерната имени А.Н. Колмогорова МГУ имени М.В. Ломоносова Владимир Романов, выпускник питерского «Президентского физико-математического лицея № 239» Михаил Анопренко, а также самый юный участник команды – девятиклассник из московской Школы «Интеллектуал» Егор Лифарь.

«Для решения задачи требуется изобрести верный алгоритм, а также правильно и аккуратно реализовать его в программе. Оба этапа важны: не зная алгоритм, нельзя написать программу, но без навыков программирования даже гениальная идея сама по себе не принесет баллов. В некоторых задачах придумать решение сложнее, чем потом написать программу, а в некоторых наоборот: идея решения на поверхности, но кода нужно очень много. В задачах олимпиады прошлого года гораздо сложнее было изобрести правильную идею, чем писать код. В этом году баланс чуть сместился в сторону реализации, написания больших программ, но и дойти до идеи решения тоже было непросто. С отборочными мы хорошо угадали. На отборах было несколько задач, похожих на те, что были в итоге на Межнаре», – рассказал один из тренеров команды, финалист престижных индивидуальных соревнований по спортивному программированию Topcoder Open и Russian Code Cup, тренер Moscow Workshops ICPC и команд-чемпионов ICPC Михаил Тихомиров. Кроме него команду готовил и медалист ICPC, тренер шестикратных чемпионов ICPC, судья Всероссийской олимпиады по информатике Андрей Станкевич. Ранее в течение многих лет команду тренировал Владимир Кирюхин, он совсем недавно передал ее новому поколению.

Как ребята готовились

До того, как попасть на сборы перед IOI, школьники проходят четыре этапа Всероссийской олимпиады школьников: школьный, муниципальный, два тура областного и два тура заключительного. Кроме того, они участвуют в двух профильных сменах образовательного центра «Сириус»: в марте там готовили призеров регионального этапа Всероса к заключительному этапу, в июне —призеров и победителей заключительного этапа к Международной олимпиаде. Дальше 20 участников, отобранных ЦПМК, приезжают на сборы, которые в этом году впервые организовал Физтех.

«Я много участвовал в отборах в сборную, где-то четыре раза, это больше, чем у остальных, – рассказал Рамазан Рахматуллин. – Я очень хотел победить, но, в первую очередь, хотел пройти в сборную, победить уже потом».

Для подготовки школьников к IOI в МФТИ также организовывают лагерь Moscow Workshops Juniors (Зимняя компьютерная школа), в котором школьники из разных стран могут учиться информатике и готовиться к олимпиаде. Трое из четырех участников российской сборной этого года, вся сборная Белоруссии и Казахстана, а также участник сборной Греции тренировались в этом лагере.

Школьники готовились, решая задания десяти соревновательных этапов, четыре из которых были отборочными, а остальные шесть состояли из задач прошлых лет.

Результаты олимпиады: мы и они

В этом году были награждены 167 участников из 335. 29 золотых медалей вручили тем, кто набрал 336 баллов и больше, 55 серебряных – тем, чей результат перевалил за 272 балла, и 83 бронзовые медали – тем, кто преодолел границу в 187 баллов.

Были среди участников и те, кто не решил ни одну задачу. А вот победитель IOI, Бенджамин Ци, решил четыре задачи из шести на максимальные 100 баллов и в сумме набрал 499 баллов из максимальных 600. В этом году впервые удалось завоевать два золота Грузии, пока это лучший результат страны за всю историю выступлений. В медальном зачете хорошо выступила Белоруссия, завоевав две золотые и две серебряные медали. Благодаря этому в общекомандном зачете они поделила с Россией 4-5 место. За Беларусь с 2006 по 2012 год выступал легендарный олимпиадник Геннадий Короткевич из Гомеля, что много лет выводило страну в лидеры IOI. Короткевич был абсолютным победителем IOI трижды — с 2009 по 2011 годы, еще три раза брал золото и один раз серебро.

Любопытно, что впервые за историю IOI вторая команда принимающей олимпиаду страны (в этом году — Японии), которую стране можно выставлять для соревнования вне конкурса, выступила лучше первой — как по баллам, так и по медалям: одно золото, два серебра и одна бронза против одного золота, одного серебра и двух бронз.

В нашей сборной места и медали распределились таким образом:

Рамазан Рахматуллин — 11 место (золото),

Владимир Романов — 20-21 место (золото),

Михаил Анопренко — 33-36 место (серебро),

Егор Лифарь — 60-64 место (серебро).

«Ребята хорошо выступили. Но есть и что доработать, — отметил Михаил Тихомиров. — У кого-то было хорошо с придумыванием идей, но плохо с аккуратным написанием кода. А у кого-то наоборот. Надо, чтобы все было хорошо. У двоих из ребят есть еще несколько лет для участия в IOI, и мы теперь еще лучше понимаем, что с ними делать».

Бонусы

Призеры заключительного этапа Всероссийской олимпиады школьников без экзаменов поступают в вузы и могут получать стипендию по президентскому гранту — 20 тысяч рублей в месяц на все время учебы в вузе, при условии, что после выпуска они три года отработают в России. Университеты, как правило, тоже поощряют медалистов именными стипендиями.

За победу на олимпиадах власти каждого региона по-своему поощряют своих школьников. Правда, тут есть перекос: москвичам за золотую медаль дают по миллиону рублей, другие регионы этого себе позволить не могут. Но каждый из них пытается поддерживать своих сильнейших ребят.

Итоги разных стран на IOI

Среди лидеров Международной олимпиаде из года в год остаются Китай, США, Республика Корея, Иран и Россия.

Таблица с результатами российских сборных за последние 5 лет и сравнение с другими странами

По числу золотых медалей IOI Россия находится на втором месте после Китая, опережая США, Польшу и Республику Корея.

На студенческих соревнованиях по спортивному программированию ICPC список стран-лидеров похожий, но Россия уже сильно опережает другие страны. С 2000 года российские студенты на ICPC завоевали 32 золотые медали. Для сравнения: студенты из Китая всего 13 раз удостаивались золота за этот период, европейские участники без учета России — 11, США — всего 6.

Казалось бы, странно: на студенческих олимпиадах наши ребята выступают намного лучше, в чем же дело на школьных соревнованиях? Алексей Малеев считает, что все дело в разнице системы подготовки и дефиците кадров в учительской среде. «Разрыв в уровне преподавания информатики в российских школах огромный. Москва выставляет иногда по 70 человек на заключительный этап Всероса, а есть регионы, от которых и одного человека не могут отправить. Но даже московские школьники порой не добираются до такого учителя, который мог бы вытащить их на абсолютное чемпионство в мире», — объясняет он.

Он также пояснил, что в России очень сильное университетское сообщество, и многие студенческие тренировки проводятся совместными усилиями. Есть международные сборы по спортивному программированию Moscow Workshops ICPC. Сильные тренеры из разных вузов, имена которых у всех на слуху, ездят по сборах в разные города и тренируют студентов. А у школьников такого практически нет. Они большую часть времени готовятся локально в своем городе, в своей школе. И тут уже все упирается в то, повезет или нет с учителем.

«Надо дать возможность школьникам из любого уголка России учиться у сильнейших педагогов. И параллельно готовить сильных тренеров, переманивать лучших специалистов из индустрии в преподавание. Это не только даст возможность стать абсолютными лидерами IOI, но и в перспективе поможет развитию IT-отрасли в нашей стране», — заключил Малеев.

Автор: Мария Мильшина

Понравился материал? Добавьте Indicator.Ru в «Мои источники» Яндекс.Новостей и читайте нас чаще.

Подписывайтесь на Indicator.Ru в соцсетях: Facebook, ВКонтакте, Twitter, Telegram, Одноклассники.