Программирование на скорость, или Как получить золото на Международной олимпиаде по информатике

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

Теперь медаль высшей пробы на соревнованиях, организованных Сингапуром, завоевал Семен Савкин — выпускник школы № 57 и уже студент Национального университета «Высшая школа экономики». В День интернета, который в России отмечают 30 сентября, он рассказал mos.ru, как научиться решать сложнейшие задачи по спортивному программированию и завоевать золото одного из самых крупных научных соревнований.

— Как ты попал в сборную страны?

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

Весной из-за пандемии заключительного этапа всероссийской олимпиады не было, ее заменил дополнительный этап сборов, на который пригласили около 100 участников. На этом этапе выбрали 29 человек, которые прошли дальше, а на втором этапе из них отобрали четверых в команду.

Испытания были идентичны тем, что бывают на международной олимпиаде. Участникам в каждом туре давали по три задачи и пять часов на их решение. Каждая задача максимум оценивалась в 100 баллов.

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

— Соревнование по спортивному программированию состоит из нескольких задач, их нужно решить за определенное время. Вот пример классической задачи по спортивному программированию: дан текст и некоторая строка, нужно проверить, встречается ли эта строка в тексте. Такую задачу решают все текстовые редакторы при использовании функции поиска или замены. Участники пишут программу, которая получает данные (текст и строку) и выводит ответ на задачу.

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

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

Насколько сложно получить золотую медаль на международной олимпиаде?

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

— Из каких стран были самые серьезные соперники?

— Мне кажется, самые сильные участники из Китая, США, Ирана, Кореи. Команды этих стран завоевали больше всего медалей.

М. Денисов. Mos.ru

— Какое конкурсное задание запомнилось больше всего?

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

— А на практике такую задачу можно применить?

— Те задачи, которые есть на олимпиаде, вряд ли непосредственно можно применить на практике, это, скорее, алгоритмические головоломки. Но все из сферы информатики применяется на практике, есть разные алгоритмы, которые действительно используют в ИТ-индустрии.

— Можно ли угадать правильный ответ?

— Нет. Решением задачи является программа, там нет вариантов ответа. Наугад написать случайную программу, чтобы она прошла тесты, не получится.

— Есть ли какой-то секрет подготовки? Что посоветуешь тем, кто хочет заниматься спортивным программированием?

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

— Почему именно информатика?

— Раньше я интересовался олимпиадами по математике и физике, но потом подумал, что стоит выбрать один предмет, поскольку достаточно трудно участвовать в нескольких чемпионатах. Олимпиады по информатике мне нравились больше всего, поэтому я выбрал ее. Я много раз участвовал во всероссийских соревнованиях, в открытой олимпиаде школьников, олимпиадах в Болгарии и Румынии, где тоже получал золото.

— Чем бы ты хотел заниматься в будущем?

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

— Может, ты уже знаешь, какую программу хотел бы создать?

— Пока у меня нет конкретных идей для написания новой программы. Я попробую попасть на стажировку в крупную компанию и определиться с областью деятельности.

— Можешь ли ты сегодня представить мир без интернета?

— Наверное, если бы интернет внезапно пропал, было бы плохо и неудобно всем. Сейчас без него очень многое уже не работает— те же банки, например. При таком повороте событий очень много информации будет утеряно.

— Расскажи про жизнь с гаджетами. Много времени проводишь за ними?

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

— А чем занимаешься, кроме учебы и компьютера?

— Я люблю кататься на горных лыжах. Делаю это в основном в Подмосковье, но один раз ездил кататься в Альпы.