Спорт для разработчиков: как устроено олимпиадное программирование
Ключевые соревнования, советы по подготовке и работе в команде
Спортивное программирование часто ассоциируется у людей с профессиональными командами, которые занимаются им со средней школы (или даже с начальной, как самый титулованный спортивный программист мира Геннадий Короткевич) и тратят на подготовку большую часть своего времени. Однако в соревнованиях участвует множество разработчиков с разным уровнем подготовки и с разной мотивацией: многие хотят научиться быстро писать рабочий код, углубить знания в области алгоритмов или добавить олимпиадный опыт в своё резюме. Академия Яндекса поговорила с участниками олимпиад и с Сергеем Чернышёвым — руководителем управления по работе с талантами Яндекса, финалистом ICPC 2002 года, о том, как начать заниматься спортивным программированием и зачем это делать.
Как устроены соревнования по программированию
Задача участников соревнований — решить как можно больше предложенных задач за ограниченное время. Соревнования бывают как индивидуальными, так и командными. Они состоят из нескольких этапов (например, отборочный тур, полуфинал и финал) и проводятся отдельно для школьников, студентов и выпускников вузов.
Одна из самых известных таких олимпиад — Международная студенческая олимпиада по программированию (ICPC). Она впервые состоялась в 1977 году в рамках конференции АСМ и с тех пор проводится каждый год. Последние восемь лет подряд выигрывают студенты российских университетов — МГУ, СПбГУ и ИТМО.
В ICPC могут участвовать студенты вузов или аспиранты первого года обучения не старше 24 лет. Это групповое соревнование, в котором участвуют команды из трёх человек.
Тур олимпиады проходит следующим образом: каждой команде выдаётся ноутбук и от восьми до двенадцати задач (их условия написаны на английском языке), которые нужно выполнить за пять часов. Участники пишут решения на языках программирования C, C++, Java, Python или Kotlin, компилируют и посылают их на тестирующий сервер.
При этом частичные решения не учитываются, а побеждает команда, правильно решившая наибольшее число задач.
Зачем участвовать в командных соревнованиях
«Олимпиадное программирование как большой спорт, и для того, чтобы занимать первые места на чемпионатах, нужно уделять подготовке почти всё своё время», — рассказывает Сергей Чернышёв, который сейчас занимается организацией олимпиад. У профессиональных команд есть свои тренеры (бывшие победители и призёры олимпиад и преподаватели университетов), которые отбирают перспективных студентов и готовят их к соревнованиям.
Многие участвуют в олимпиадах не ради победы. Например, студенты начинают заниматься спортивным программированием, потому что им нравится решать задачи или потому что на соревнования ездят их однокурсники. Однако из соревнований можно вынести пользу, даже если подходить к ним по-любительски. Чернышёв говорит о том, что участие в олимпиадах развивает как индивидуальные навыки и знания, так и умение работать в команде.
Команда во время перерыва. Фото: Moscow Programming Contest
«По сути, ICPC — это дополнительное дистанционное обучение, которое позволяет „прокачать“ себя. Благодаря олимпиадам студенты лучше узнают, что такое динамическое программирование, строковые и другие алгоритмы — эти темы не всегда глубоко преподаются в университетах», — объясняет Сергей.
Влад Бидзиля, участник ICPC и других олимпиад по программированию, считает, что у людей, которые хотят стать сильными разработчиками, есть несколько возможных направлений развития. Первое — набираться практического опыта, изучать новые фреймворки и технологии. А второе — развивать интеллект, занимаясь фундаментальными задачами (например, участвуя в олимпиадах). Опыт участия в соревнованиях помогает быстрее осваивать новые области. Этот опыт пригодился и в учёбе на ФКН НИУ ВШЭ и в ШАДе, и в работе в Яндексе: Влад говорит, что он везде замечал похожие паттерны.
Кроме того, олимпиады учат писать код без багов. «В контестах встречаются запутанные логические конструкции, которые редко возникают на практике», — поясняет Бидзиля. — В работе код обычно разделен: есть отдельные компоненты с понятными связями между собой. Поэтому если человек научился работать со сложной логикой, то в промышленной разработке он уже вряд ли допустит ошибки».
Как подготовиться и что делать во время соревнования
«Для того, чтобы начать участвовать в соревнованиях, ничего не нужно — только желание и умение программировать на каком-нибудь языке», — убеждает Сергей Чернышёв. А начать подготовку можно с решения задач на таких сайтах, как Codeforces, Topcoder и CodeChef.
Участник ICPC этого года Саша Минаков говорит: «Чтобы оказаться хотя бы в середине рейтинга участников, нужно знать популярные алгоритмические методы, типичные нелинейные структуры данных и графы». А профессиональные команды отличает знание специфичных алгоритмов, которые появляются в задачах олимпиад раз в несколько лет.
Ресурсы для подготовки:
Для участия в соревнованиях важно собрать грамотную команду и организовать её работу. Нередко в группах появляются «лидеры», которые сильнее всего мотивированы и сдают наибольшее количество задач за тур. «Однако только за счёт этого сложно достичь высоких результатов, потому что за несколько часов работы этот человек выдыхается и начинает совершать ошибки», — отмечает Чернышёв.
Хорошие команды — те, в которых все три участника постоянно сдают задачи и сменяют друг друга: пока один решает задачу, другой сидит за компьютером. Раньше бытовал стереотип, что в команде должны быть математик, программист и специалист по алгоритмам, но сейчас он неактуален, так как изменился формат соревнования и задачи стали более прикладными.
Команда за работой. Фото: Moscow Programming Contest
Во время тура нельзя терять концентрацию: на ICPC нужно решить до двенадцати задач за пять часов, и времени переделывать их нет. При этом на соревнованиях необязательно писать «чистый» код: он используется один раз, а жюри оценивает только итоговый результат. В случае с промышленным программированием, наоборот, важно сделать так, чтобы код было легко читать и поддерживать другим разработчикам.
Как изменялось спортивное программирование и что его ждёт
«За последние годы спортивное программирование стало более прикладным», — убеждён Сергей Чернышёв. Это связано с повышением культуры программирования: раньше в российских школах изучали Pascal, и задачи решали тоже на нём. Со временем у людей в олимпиадном сообществе появился опыт использования библиотек Java и C++ и различных структур данных. На их базе придумывали более сложные структуры для спортивного программирования, и за счёт этого прикладная и олимпиадная разработки сблизились. К тому же компьютеры стали работать быстрее, и ограничения по времени выполнения задач (на ICPC это обычно одна, две или три секунды) отошли на второй план. Ключевую роль в задачах стали играть аспекты реализации.
Чернышёв рассказывает, что олимпиадное движение развилось в России примерно на десятилетие раньше, чем хакатоны, которые набрали популярность после 2010 года. Организатор олимпиад говорит о том, что нынешним студентам будет полезно принять участие как в тех, так и в других соревнованиях. Хакатоны пригодятся тем, кто хочет развить продуктовое мышление или реализовать свою идею: они мало влияют на сам навык разработки. А спортивное программирование подойдёт как раз для того, чтобы углубить знания.
В будущем Сергею хотелось бы повысить престиж участия в олимпиадах по программированию. По его словам, сейчас для этого не хватает чёткой мотивации участвовать, нет, например, денежных призов или привилегий при приёме на работу. Чернышёв сравнивает студенческие олимпиады с Всероссийской олимпиадой школьников, где призёры и победители заключительного этапа гарантированно получают значимый приз — поступление в любой вуз России на соответствующее направление.
Мне кажется, что количество переходит в качество, поэтому если спортивное программирование будет популярным, то в нём автоматически будут очень сильные игроки.
Школьник об олимпиадном программировании
Об обучении
Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.
Задачи
Требования
От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#, Python). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл — тем выше место.
Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.
Риски
Wrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Олимпиады
Как проходит всероссийская олимпиада по информатике?
Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.
Этап среди старшеклассников
Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.
Муниципальный этап
Решить задачу, если объект один достаточно просто. Но когда объектов больше — приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение — я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.
В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.
Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было — записывал в выходной поток номер слова, иначе — добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти здесь.
На дистанционном туре я занял 1 место среди девятиклассников.
Региональный этап
На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.
Подготовка
Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.
Что же дальше?
Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя — выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.
Чем участие в олимпиадах полезно для карьеры разработчика
«Фундаментальные знания, которые даёт опыт спортивного программирования, не устаревают. Они пригодятся в любой сфере деятельности»
Большинство участников олимпиад по программированию заканчивают свою спортивную карьеру после выпуска из университета и начинают заниматься исследовательской деятельностью или промышленной разработкой. Самыми полезными для них оказываются даже не медали, а знания и знакомства, приобретённые на соревнованиях и не устаревающие спустя годы. Руководитель группы диалоговых систем Алисы и бронзовый призёр ACM ICPC 2014 года Слава Алипов рассказал о том, как начал заниматься спортивным программированием, чем отличаются олимпиадная и промышленная разработка и почему опыт спортивного программирования продолжает помогать ему в карьере.
Олимпиадный путь
Я стал участвовать в олимпиадах на первом курсе университета, что довольно поздно по меркам спортивного программирования. Обычно успешные спортивные программисты начинают еще в школе.
У меня же всё началось с олимпиады для студентов первого и второго курсов Томского политехнического университета, в котором я учился на бакалавриате. Я пришёл на соревнование и ничего на нём не решил, зато познакомился с олимпиадниками нашего вуза и начал ходить с ними на кружок по спортивному программированию.
На второй год я уже выиграл в олимпиаде первого и второго курсов, потом — в общеуниверситетской. Тогда же я начал проводить занятия на кружке по подготовке к олимпиадам по программированию и присоединился к первой команде вуза. Нашим лучшим результатом был полуфинал Международной студенческой олимпиады по программированию ICPC, но выйти в финал никак не удавалось. Я думал, что «наигрался» и на этом и закончу свою олимпиадную карьеру.
Я решил поступить в магистратуру в московский вуз и выбрал совместную программу Высшей школы экономики и Школы анализа данных. Эту же магистратуру выбрали два моих будущих сокомандника: они узнали о том, что я поступаю, и позвали дальше участвовать в олимпиадах вместе с ними. В этом составе мы потренировались год, на втором курсе магистратуры прошли на финал чемпионата мира по программированию и завоевали на нём бронзовые медали.
Тренировались всегда сами: формально у нас были тренеры, но в основном мы занимались самостоятельным решением задач и написанием контестов. Одним из самых результативных видов тренировки было участие в сборах, в первую очередь Ижевских и Петрозаводских.
Для успешного выступления на олимпиадах по программированию нужно не только отлично владеть выбранным языком программирования, но и иметь глубокие и обширные знания в области фундаментальных дисциплин: алгоритмы, динамическое программирование, теория вероятностей, комбинаторика, теория графов, геометрия, теория чисел и так далее. В олимпиадах хорошо заметен прогресс: ты можешь найти свои слабые места и пробелы в знаниях, поработать над ними и сразу применить новые навыки в решении задач, а результат увидеть за счёт растущего рейтинга на Codeforces или более высокой позиции на очередном соревновании. Олимпиады — это весело и азартно, а позиции и рейтинги — хорошая мотивация узнать и освоить что-то новое из математики и алгоритмов.
В олимпиадах меня привлекала возможность непрерывно улучшать свою фундаментальную подготовку
Фундаментальные знания не устаревают и пригодятся в любой сфере деятельности: учёбе, исследованиях и промышленной разработке. Технологии изменяются каждый день: появляются и исчезают фреймворки, языки программирования и подходы к проектированию. Знание алгоритмов и математических дисциплин всегда будет актуальным, и на их изучение не жалко тратить усилия, а благодаря олимпиадам это ещё и приятно.
Олимпиадный стиль программирования
Написание кода на соревнованиях и в промышленной разработке имеют принципиальные отличия. В первую очередь, на олимпиадах гораздо сильнее ограничено время на написание кода. За счёт этого формируется так называемый «олимпиадный стиль», который любят критиковать профессиональные разработчики: короткие имена переменных и функций, гораздо меньшая декомпозиция кода на подпрограммы.
В олимпиадной разработке почти не нужно использовать объектно-ориентированное программирование и объявлять классы. Спортивные программисты пишут в процедурном, минималистичном стиле, и их код в первую очередь направлен на то, чтобы решить поставленную задачу.
Несмотря на это при написании олимпиадного кода всё равно нужно задумываться о том, что его придется тестировать, и учитывать то, что с большой вероятностью он не заработает с первого раза. В промышленном программировании принято решать эту проблему тестами, убеждаться в том, что отдельные модули программы можно протестировать, и думать о том, как структурировать программу, чтобы фрагменты можно было редактировать по отдельности. На контестах по программированию на самом деле нужно делать то же самое — только проверять придётся не юнит-тестами, а дебаг-выводом или брейк-пойнтами. Поэтому и в промышленной разработке, и в написании олимпиад важен навык декомпозиции. За счет других правил декомпозиции олимпиадный код выглядит страшнее, чем промышленный, но это не значит, что он нечитаемый или не структурированный.
Написав тысячи программ, ты хорошо убедишься, что программы с первого раза не работают, их нужно уметь тестировать и исправлять
К тому же чем больше ты практикуешься, тем проще будет писать любой код — как олимпиадный, так и промышленный.
Опыт спортивного программирования и промышленная разработка
Я устроился на стажёрскую позицию в Яндекс.Метрике одновременно с поступлением в магистратуру. В эти два года я совмещал три вида деятельности: работу в Яндексе, занятия в ШАДе и Вышке, а также подготовку к олимпиадам по программированию.
В ходе стажировки мне пришлось узнать и освоить много нового: бесполезные на олимпиадах, но часто используемые в промышленном коде библиотеки для работы с памятью и сетью, примитивы для многопоточных вычислений. Для обработки огромных объемов данных сервисов Яндекса пригодились новые структуры данных и алгоритмы для приближенных вычислений. Появилась необходимость в утилитах для отладки и профилирования моих программ.
Плохо ли, что олимпиады к этому не готовят? Да нет: олимпиады не готовили меня и к тому, что у меня больше не будет стипендии, и к тому, что мне самому нужно будет планировать своё развитие и ставить цели.
При переходе от олимпиад к промышленной разработке ты перестраиваешься на другой режим написания кода. В большой компании программы занимают больше нескольких страниц А4, а на написание нового проекта можно потратить сильно больше получаса. Становится важным соблюдение строгих стайлгайдов и принципов организации кода проекта, принятых в команде. Начинаешь тренировать новый для себя навык — умение разбираться в больших объемах чужого кода.
Олимпиадникам придётся свыкнуться с тем, что у задач больше нет точного решения
Часто программу можно улучшать бесконечно, поэтому очень важно научиться находить баланс между красотой решения и затраченным на него временем. При этом твое чувство прекрасного может не совпадать с мнением руководителя, и стажировка — отличное время, чтобы разобраться с новыми критериями работы.
После того как выпускаешься из вуза, доступных олимпиадных активностей (соревнований и сборов) становится меньше, а большинство спортивных программистов сосредотачивается на работе или на своих научных интересах. Кто-то продолжает ездить на сборы с лекциями и составлять для них задачи, но спортивное программирование быстро развивается, и за ним сложно уследить, если не заниматься им постоянно.
Сейчас я работаю в команде Алисы — руковожу группой диалоговых систем, которая занимается созданием моделей и инструментов для ведения диалога с целью решения задачи пользователя. Для этого нужно понимать смысл отдельных запросов пользователя и всего диалога целиком, уметь запрашивать у пользователя необходимую для решения задачи информацию.
Также в нашей группе разрабатывается «болталка» — движок для разговоров на свободные темы. Для этой задачи нет устоявшихся подходов и гарантированно работающих решений, большая роль отведена исследованиям и экспериментам.
В такой молодой и бурно развивающейся области, как диалоговые системы, очень важно следить за научным прогрессом, пробовать на практике подходы из статей, придумывать новые модели и ставить новые задачи машинного обучения. В условиях, когда нужно уметь быстро понимать и придумывать много нового, эрудиция в математических дисциплинах и алгоритмах, приобретенная за годы участия в олимпиадах, оказывается очень кстати.
Олимпиадное программирование: что, как и почему Россия впереди всего мира
Конспект подкаста «Запуск завтра»
По старой традиции публикуем конспект подкаста «Запуск завтра», который (как и мы) выходит при поддержке «Практикума». Если есть время, слушайте весь выпуск, если нет — читайте наш текст.
О герое
Елена Андреева — член жюри Всероссийской олимпиады по программированию, член экспертного совета в «Сириусе», заведует кафедрой в СУНЦ МГУ. Команда Лены два года подряд становилась чемпионом мира по олимпиадному программированию.
Что такое олимпиадное программирование
Олимпиадное программирование — студенческие соревнования. Это значит, что члены одной команды должны быть не из одной страны, как на Олимпийских играх, а из одного вуза. Студенты получают набор задач и решают их с помощью кода и алгоритмов.
Так же как в большом спорте, в программировании нужна одарённость, но здесь это не так важно. В нашей дисциплине количество переходит в качество: главное, много заниматься, и результаты придут.
Чтобы тренироваться, тебе не нужен личный тренер и стадион — в интернете полно ресурсов, где можно решать задачи. А ещё есть форумы, где можно задать вопрос и где тебе помогут найти решение.
Мне запомнилась речь одного американского мальчика, который дважды выигрывал олимпиаду по информатике. В своём выступлении он благодарил родителей и платформу Codeforces. Это такой сайт, где тренируется большинство начинающих программистов и где они могут общаться друг с другом. Так вот, эта платформа сделана у нас в Саратове.
Почему мы всё время выигрываем
На открытии Чемпионата мира каждый год перечисляют всех предыдущих чемпионов. Раньше это всегда были разные вузы, но с 2012-го там были в основном наши ребята.
2018, 2019 год ― МГУ.
Давайте подумаем, как так получается.
Чтобы команде получить статус чемпиона мира, должны родиться талантливые участники. Население страны должно быть не маленьким, чтобы повысить вероятность такого явления. У нас хватает молодых ребят, но в этом плане нет особого преимущества. Китай и Индия сильно нас опережают по этому показателю, а американские студенты, даже если они из России, скорее будут выступать за свой вуз.
Следующий фактор, который влияет на вероятность чемпионства, — система образования. Здесь у нас тоже всё неплохо, но в Америке вузовское образование всё-таки посильнее, чем наше: там сфера обучения гораздо быстрее меняется под влиянием IT. Тем не менее почему же эти гениальные китайцы, которые выигрывали школьные олимпиады, не могут обыграть российские команды, собираясь все вместе в топовом вузе? Ответ прост — тренировки.
В России хорошо развита система подготовки к турнирам по программированию: это и сборы, и различные внутренние соревнования. А главное, нашим ребятам во всём этом интересно участвовать.
Зачем участвовать в олимпиадах по программированию
Если ты одарённый программист, то у тебя есть другие способы себя занять, кроме как заниматься олимпиадами. Например, зарабатывать деньги.
Ещё пять лет назад не было такого, чтобы студенты младших курсов в основном все работали. На втором — единицы шли на стажировки. Сейчас многие талантливые ребята, даже призёры международных олимпиад, могут не окончить вуз. Как они говорят: «Ваша учёба мешает моей работе».
Мне нравится, что раньше на этот счёт говорили в Google: «Мы не любим брать на работу людей, у которых нет высшего образования, хотя бы диплома бакалавра. Если такой сотрудник не осилил квест получить диплом, то точно так же может завалить любой проект».
Для тех, кто только в вузе начал изучать алгоритмы и решать задачи по программированию, олимпиада — отличная возможность подготовиться к собеседованию в IT-компанию. На собеседованиях дают задачи, которые очень похожи на олимпиадные, и просят написать быстро правильный код. То есть условия на собеседовании гораздо больше походят на олимпиаду по программированию, чем на реальную работу.
Задачи на олимпиаде заставляют думать и отметать неэффективные решения
Я одна из тех, кто готовит задачи на соревнования, поэтому прямо могу рассказать, как идёт процесс. Когда я ставлю себе цель придумать задачу, то редко задумываюсь о том, чтобы просить студентов построить какой-то отвлечённый алгоритм. Чаще всего я думаю, как решить какую-то жизненную проблему.
Так, вместе с методической комиссией мы придумали задачу про экономию. Я вспомнила, что не так давно мне спортклуб прислал какие-то скидки. Мы взяли эти данные за основу, немного их видоизменили и предложили студентам задачу, в которой нужно было соотнести цены, акции и специальные предложения. На выходе должен был получиться алгоритм, который рассчитывает оптимальное поведение клиента, чтобы он мог заплатить меньше всего денег.
Другой пример — задача про реновацию на московской олимпиаде. Было много вводных: дома разной этажности, разная эффективность на квадратный метр строительства, стоимость квадратного метра и так далее. Надо было по определённым критериям выбрать, что и как нужно строить, чтобы проект максимально эффективно решал вопрос реновации.
Я хочу, что как можно больше студентов не то чтобы участвовали в олимпиадах, а хотя бы знали об их существовании. Чтобы они понимали, что для многих задач есть более эффективные решения, чем просто в лоб.
Например, если нам нужно найти слово в огромном тексте, то самое простое решение — приложить слово к началу текста и сравнить каждую букву. Потом сдвинуть на одну букву, снова сравнить и так далее. Есть алгоритмы, которые умеют это делать, но это очень долго. Алгоритмы, которые применяют на олимпиадах, могут делать это гораздо быстрее.
Как Елена тренировала чемпионов
Когда мы готовились к соревнованиям, ребята были довольно самостоятельными: они сами организовывали тренировки и участвовали в сборах.
Моя фактическая роль была в том, чтобы решать психологические проблемы участников команды и разрешать конфликты. В этом плане я выступала больше как спортивный психолог.
Ребята были настроены серьёзно и задолго до турнира «входили в форму». Они заранее скачали систему, на которой проводится олимпиада, и тренировались исключительно в ней. У команды была выстроенная последовательность действий, кто и что делает буквально по минутам. Каждой мелочи уделялось внимание.
Я думаю, что именно такого внимания к мелочам не хватает американским и китайским командам, чтобы победить. Они думают, что можно собрать трёх топовых участников, каждый из которых отлично решает, и этого достаточно. Практика показывает, что нет.
Когда мы готовились к китайской олимпиаде, то старались вставать в 6 утра. Олимпиада проводилась в китайском часовом поясе, и мы писали код в условиях, которые были максимально приближены к реальным соревнованиям. Тренировки были серьёзными: утром ребята решали одни задачи, потом отдыхали и шли дорешивать те, что сразу не получилось. Ещё решали задачи с прошлых чемпионатов мира, прямо как в шахматах.
Почему сложно подготовиться к олимпиаде
по программированию
Даже на уровень регионального этапа Всероссийской олимпиады по информатике средний школьный учитель подготовить не может. Он может это сделать, если несколько лет будет глубоко заниматься предметом и изучит олимпиадное программирование как сферу. Для подготовки важно знать, как соревнования устроены изнутри.
То, что школьный учитель не может подготовить к олимпиадному программированию, — не страшно. Беда в том, что люди, которые хорошо разбираются в программировании и могут этому научить, не будут работать в школе или вузе. Востребованным специалистам сложно найти время, даже если им нравится учить детей решать задачи. Многие из них начинают обучать и работать параллельно, а потом всё-таки уходят, потому что становится сложно выкраивать время на преподавание.
В полной версии подкаста
7:00 Как Лена нашла ребят, которые потом стали мировыми чемпионами
11:30 Проблема кадров. Как студенческая олимпиада конкурирует с IT-компаниями за специалистов
19:40 Мир устал от российских побед. Когда это изменится?
26:00 Как Лена тренировала свою сборную на даче
32:30 Как выбирают страну и город для чемпионата
36:10 Как придумывают олимпиадные задачи
43:00 Как Лена меняет школьную программу по информатике
