Олимпиадное программирование что это такое
Олимпиадное программирование: что, как и почему Россия впереди всего мира
Конспект подкаста «Запуск завтра»
По старой традиции публикуем конспект подкаста «Запуск завтра», который (как и мы) выходит при поддержке «Практикума». Если есть время, слушайте весь выпуск, если нет — читайте наш текст.
О герое
Елена Андреева — член жюри Всероссийской олимпиады по программированию, член экспертного совета в «Сириусе», заведует кафедрой в СУНЦ МГУ. Команда Лены два года подряд становилась чемпионом мира по олимпиадному программированию.
Что такое олимпиадное программирование
Олимпиадное программирование — студенческие соревнования. Это значит, что члены одной команды должны быть не из одной страны, как на Олимпийских играх, а из одного вуза. Студенты получают набор задач и решают их с помощью кода и алгоритмов.
Так же как в большом спорте, в программировании нужна одарённость, но здесь это не так важно. В нашей дисциплине количество переходит в качество: главное, много заниматься, и результаты придут.
Чтобы тренироваться, тебе не нужен личный тренер и стадион — в интернете полно ресурсов, где можно решать задачи. А ещё есть форумы, где можно задать вопрос и где тебе помогут найти решение.
Мне запомнилась речь одного американского мальчика, который дважды выигрывал олимпиаду по информатике. В своём выступлении он благодарил родителей и платформу Codeforces. Это такой сайт, где тренируется большинство начинающих программистов и где они могут общаться друг с другом. Так вот, эта платформа сделана у нас в Саратове.
Почему мы всё время выигрываем
На открытии Чемпионата мира каждый год перечисляют всех предыдущих чемпионов. Раньше это всегда были разные вузы, но с 2012-го там были в основном наши ребята.
2018, 2019 год ― МГУ.
Давайте подумаем, как так получается.
Чтобы команде получить статус чемпиона мира, должны родиться талантливые участники. Население страны должно быть не маленьким, чтобы повысить вероятность такого явления. У нас хватает молодых ребят, но в этом плане нет особого преимущества. Китай и Индия сильно нас опережают по этому показателю, а американские студенты, даже если они из России, скорее будут выступать за свой вуз.
Следующий фактор, который влияет на вероятность чемпионства, — система образования. Здесь у нас тоже всё неплохо, но в Америке вузовское образование всё-таки посильнее, чем наше: там сфера обучения гораздо быстрее меняется под влиянием IT. Тем не менее почему же эти гениальные китайцы, которые выигрывали школьные олимпиады, не могут обыграть российские команды, собираясь все вместе в топовом вузе? Ответ прост — тренировки.
В России хорошо развита система подготовки к турнирам по программированию: это и сборы, и различные внутренние соревнования. А главное, нашим ребятам во всём этом интересно участвовать.
Зачем участвовать в олимпиадах по программированию
Если ты одарённый программист, то у тебя есть другие способы себя занять, кроме как заниматься олимпиадами. Например, зарабатывать деньги.
Ещё пять лет назад не было такого, чтобы студенты младших курсов в основном все работали. На втором — единицы шли на стажировки. Сейчас многие талантливые ребята, даже призёры международных олимпиад, могут не окончить вуз. Как они говорят: «Ваша учёба мешает моей работе».
Мне нравится, что раньше на этот счёт говорили в Google: «Мы не любим брать на работу людей, у которых нет высшего образования, хотя бы диплома бакалавра. Если такой сотрудник не осилил квест получить диплом, то точно так же может завалить любой проект».
Для тех, кто только в вузе начал изучать алгоритмы и решать задачи по программированию, олимпиада — отличная возможность подготовиться к собеседованию в IT-компанию. На собеседованиях дают задачи, которые очень похожи на олимпиадные, и просят написать быстро правильный код. То есть условия на собеседовании гораздо больше походят на олимпиаду по программированию, чем на реальную работу.
Задачи на олимпиаде заставляют думать и отметать неэффективные решения
Я одна из тех, кто готовит задачи на соревнования, поэтому прямо могу рассказать, как идёт процесс. Когда я ставлю себе цель придумать задачу, то редко задумываюсь о том, чтобы просить студентов построить какой-то отвлечённый алгоритм. Чаще всего я думаю, как решить какую-то жизненную проблему.
Так, вместе с методической комиссией мы придумали задачу про экономию. Я вспомнила, что не так давно мне спортклуб прислал какие-то скидки. Мы взяли эти данные за основу, немного их видоизменили и предложили студентам задачу, в которой нужно было соотнести цены, акции и специальные предложения. На выходе должен был получиться алгоритм, который рассчитывает оптимальное поведение клиента, чтобы он мог заплатить меньше всего денег.
Другой пример — задача про реновацию на московской олимпиаде. Было много вводных: дома разной этажности, разная эффективность на квадратный метр строительства, стоимость квадратного метра и так далее. Надо было по определённым критериям выбрать, что и как нужно строить, чтобы проект максимально эффективно решал вопрос реновации.
Я хочу, что как можно больше студентов не то чтобы участвовали в олимпиадах, а хотя бы знали об их существовании. Чтобы они понимали, что для многих задач есть более эффективные решения, чем просто в лоб.
Например, если нам нужно найти слово в огромном тексте, то самое простое решение — приложить слово к началу текста и сравнить каждую букву. Потом сдвинуть на одну букву, снова сравнить и так далее. Есть алгоритмы, которые умеют это делать, но это очень долго. Алгоритмы, которые применяют на олимпиадах, могут делать это гораздо быстрее.
Как Елена тренировала чемпионов
Когда мы готовились к соревнованиям, ребята были довольно самостоятельными: они сами организовывали тренировки и участвовали в сборах.
Моя фактическая роль была в том, чтобы решать психологические проблемы участников команды и разрешать конфликты. В этом плане я выступала больше как спортивный психолог.
Ребята были настроены серьёзно и задолго до турнира «входили в форму». Они заранее скачали систему, на которой проводится олимпиада, и тренировались исключительно в ней. У команды была выстроенная последовательность действий, кто и что делает буквально по минутам. Каждой мелочи уделялось внимание.
Я думаю, что именно такого внимания к мелочам не хватает американским и китайским командам, чтобы победить. Они думают, что можно собрать трёх топовых участников, каждый из которых отлично решает, и этого достаточно. Практика показывает, что нет.
Когда мы готовились к китайской олимпиаде, то старались вставать в 6 утра. Олимпиада проводилась в китайском часовом поясе, и мы писали код в условиях, которые были максимально приближены к реальным соревнованиям. Тренировки были серьёзными: утром ребята решали одни задачи, потом отдыхали и шли дорешивать те, что сразу не получилось. Ещё решали задачи с прошлых чемпионатов мира, прямо как в шахматах.
Почему сложно подготовиться к олимпиаде
по программированию
Даже на уровень регионального этапа Всероссийской олимпиады по информатике средний школьный учитель подготовить не может. Он может это сделать, если несколько лет будет глубоко заниматься предметом и изучит олимпиадное программирование как сферу. Для подготовки важно знать, как соревнования устроены изнутри.
То, что школьный учитель не может подготовить к олимпиадному программированию, — не страшно. Беда в том, что люди, которые хорошо разбираются в программировании и могут этому научить, не будут работать в школе или вузе. Востребованным специалистам сложно найти время, даже если им нравится учить детей решать задачи. Многие из них начинают обучать и работать параллельно, а потом всё-таки уходят, потому что становится сложно выкраивать время на преподавание.
В полной версии подкаста
7:00 Как Лена нашла ребят, которые потом стали мировыми чемпионами
11:30 Проблема кадров. Как студенческая олимпиада конкурирует с IT-компаниями за специалистов
19:40 Мир устал от российских побед. Когда это изменится?
26:00 Как Лена тренировала свою сборную на даче
32:30 Как выбирают страну и город для чемпионата
36:10 Как придумывают олимпиадные задачи
43:00 Как Лена меняет школьную программу по информатике
Бывших не бывает. Как опыт спортивного программирования влияет на работу с реальным кодом
Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – Codeforces Rounds, VK Cup Engine, ACM ICPC. Мы поговорим о том, как они устроены, какие плюсы и минусы есть у разработчиков с «олимпиадным» бэкграундом и как этот опыт влияет на работу с коммерческими задачами в мобильной разработке.
Принципы олимпиадного программирования
Олимпиадное программирование — участие в соревнованиях по решению нетривиальных алгоритмических задач. Программисту важно быстро решить задачу, не сделав багов. Но, как вы знаете, багов нет только в том коде, который не написан.
Принцип всех таких олимпиад один – жюри готовит описание задачи, формат входных и выходных данных программы, эталонное решение и тесты для задачи. Есть и ограничения на используемую память и время исполнения.
Участники пишут программу, которая получает на вход данные по формату задачи и выводит решение. Затем исходный код отправляется на тестирование: его компилирует площадка контеста, на заготовленных тест-кейсах проверяет используемую память и время исполнения. После чего выдается вердикт о правильности решения задачи – всё просто!
Как вы понимаете, в таких условиях самые важные показатели в решении задачи – это затраченные память и время. И нужно из бесконечного количества способов решения найти самый эффективный. Для этого используется понятие алгоритмической сложности, которое можно показать на примерах разных сортировок.
Сортировка пузырьком (в олимпиадном стиле):
Сортировка слиянием (в продакшн-стиле):
Оба кода приводят к одинаковому результату, но есть разница. Первый выполняет два вложенных цикла, каждый из которых не более чем на N итераций. А второй сливает отсортированные массивы, что выполняется не более чем за N log(N) итераций. Это значит, что верхняя оценка первого алгоритма – N^2 действий, а второго – N log(N). Это принято записывать в нотации O большое, O(N^2) и O(N log N) соответственно.
N – это размерность массива, и зависит она от входных данных. Таких данных может быть несколько, а оценка записывается с использованием всех входных параметров, влияющих на количество действий алгоритма.
Есть еще несколько правил оценки – например, сокращение членов с более низкими порядками и объединение одинаковых членов без множителей. Например, O(N^2 + N) превратится в O(N^2), а O(N + N) превратится в O(N). Подробнее об этом можно почитать на Википедии.
Плюсы
Рассмотрим плюсы такого подхода.
Ускоряем работу приложения
С опытом спортивного программирования приходит умение ускорять алгоритм, не меняя его асимптотики. Для этого вернемся к сортировке пузырьком
Мы немного модифицировали алгоритм. Из доработок – теперь мы не проверяем правую часть массива, потому что понятно, что она уже отсортирована, так как самый большой элемент перешел в правую часть. И если мы за весь проход не сделали ни одного свапа, значит, массив уже отсортирован, и дальнейшее выполнение алгоритма никаких действий не сделает.
Если применять глубокие навыки спортивного программирования, можно заметно ускорить работу приложения. Допустим, вы используете у себя в приложении какой-то сложный алгоритм обработки словаря с тремя вложенными циклами. Немного разобравшись в новом для себя виде дерева, вы поменяли словарь на самописное дерево и ускорили алгоритм обработки с O(N^3) до O(N log^2 N). Это и правда довольно ощутимый прирост производительности, что можно считать неплохим плюсом и поставить новую ачивку в свое резюме.
Уменьшаем потребляемую память
Олимпиадные программисты за счет грамотного выделения памяти и работы с ней могут не только ускорить работу приложения, но еще и сократить время его запуска и отображения экранов. Там, где обычный разработчик просто накидает lazy property, олимпиадный программист сэкономит пару сотен килобайт оперативной памяти на использовании самописных структур данных.
Увеличиваем скорость написания кода
В спортивном программировании все участники сильно ограничены во времени и пишут код очень быстро. Иметь разработчика, который решает задач на 20 сторипоинтов, когда все остальные закрывают только 10-15, очень классно.
Минусы
Но минусы олимпиадного бэкграунда тоже есть – давайте подробнее рассмотрим некоторые примеры.
Сложно читать ваш код
Вспомним пример про дерево, когда вам удалось ускорить работу приложения. Это было одним из наших плюсов, но теперь превратилось в минус – только вы умеете обращаться со своим деревом.
Схожая ситуация может получиться, когда вы используете много функций высшего порядка в одной строчке (10 фильтров, 5 редьюсов). Все же хочется, чтобы ваш код оставался поддерживаемым.
Требуются доказательства
Иногда для внедрения кода требуется доказать его работоспособность. Не всегда понятно, как это сделать. Даже техлиды не всегда разбираются в сложных алгоритмах и структурах данных.
Есть много полезных структур данных и алгоритмов, легких в освоении и простых в написании. Например, генерация сочетаний из N элементов. Их можно легко использовать, но если вы вдруг решите реализовать в своем приложении АВЛ-дерево (еще ссылка), то новоиспеченный джун на вашем проекте может наложить на вас пару проклятий.
Падает качество кода
Ускоряя написание кода, спортсмены пренебрегают его качеством и тестируемостью. Хоть решение и реализуется достаточно быстро, общая скорость разработки может упасть из-за частых реджектов PR и дополнительных ревью.
Чем программист отличается от разработчика
Тестирование кода
«Олимпиадники» тоже тестируют код, но их тесты довольно специфичны. В спортивном программировании распространены стресс-тесты – они используются, когда придумано два алгоритма: рабочий и быстрый. Рабочим может быть простое, но асимптотически сложное решение, а быстрым – любое придуманное решение, доказывать которое сложно или долго. В таком случае пишется генератор входных данных и поочередно запускаются оба алгоритма, после чего сравниваются результаты и ищутся расхождения.
Так мы быстро находим кейсы, при которых наш оптимальный алгоритм отрабатывает неправильно, и можем на построчном выполнении найти ошибки и исправить их, либо кардинально доработать алгоритм. Но, на самом деле, это не точно, потому что входные данные генерируются рандомно, и такие кейсы стресс-тесты могут просто не отследить.
Выбор решения
Попробуйте разобраться, что делает тело данной функции:
Каждая из этих функций проверяет, выбран ли айтем в данной ячейке:
Только в первом варианте разработчик придумал первое попавшееся решение, а во втором – написал свой поиск, который по факту стал более читаем и понятен. При этом он не проходит по оставшимся элементам, если уже нашел нужный. Поэтому использование уже написанных методов в стандартной библиотеке – не всегда самое верное и простое решение. Стоит иногда анализировать задачу и искать пути ускорения и повышения читаемости.
Архитектурные ценности
В разработке, помимо скорости, важны расширяемость, читаемость и переиспользуемость кода. Программист, в отличие от разработчика, пишет одноразовый код, в одном файле и зачастую в одном классе. На олимпиаде иногда можно пренебречь повторяемостью кода: проще скопировать один и тот же код в два разных места, нежели выносить его в функцию. Также для экономии времени код может быть нагорожен в одну большую кучу, без разделения на переменные и понятного нейминга.
Как я упоминал выше, использовать много функционального кода в одном блоке тоже не самая лучшая идея:
Хотя такой код пишется очень быстро и сходу понятен автору, коллегам по проекту придется тратить дополнительное время для его понимания.
Еще одна проблема fast coding’а в том, что количество ветвлений никак не мешает работе программы, но сильно портит общую картину и читаемость. Например, такой код на Objective-C:
можно заменить следующим аналогом:
А в случае со Swift нам открывается более крутая возможность – можно использовать guard, оставив неизменными наши условия:
Пока в функции одно такое ветвление, кажется, что все в порядке и никаких проблем нет, но, когда в конце функции 5-10 закрывающих скобок от if’ов без else, это выглядит грязно и крипово.
Немного про джунов
Программисты-спортсмены обычно очень умело используют структуры данных. Там, где обычный джун-разработчик напишет что-то подобное для добавления объекта в массив:
И будет удалять из него объекты примерно так:
Разработчик с олимпиадным бэкграундом или опытный разработчик поймет, что в данном случае поддерживается инвариант единственности значения. В таком случае он будет просто использовать Set, упростив тем самым код. А заодно обезопасив проект от возможных багов, которые могли возникнуть при расширении функционала. Например, в случае, когда разработчик просто не знает, что в данном массиве должна поддерживаться уникальность элементов.
Финишируем
Олимпиадное прошлое, безусловно, полезно. Но в большинстве случаев код разработчиков-олимпиадников мне кажется не самым читаемым и понятным, если они не перестроились на режим коммерческой разработки. У олимпиадников мозг работает немного иначе, они генерируют сотни крутых идей в минуту, только успевай записывать. Качество и чистота при такой быстрой записи порой хромают, и код требует рефакторинга.
Если программист научился писать читаемый код и разобрался с архитектурой, он быстро станет очень крутым и перспективным разработчиком. Но, скорее всего, столкнется с одной единственной проблемой: такие разработчики живут алгоритмами, и им не так просто в текущих реалиях найти интересный проект, где можно полностью раскрыться и показать себя. К счастью, такие проекты все же есть (пишите в личку).
Где потренироваться
Подборка площадок от золотого медалиста ACM ICPC:
Школьник об олимпиадном программировании
Об обучении
Меня всегда привлекало программирование (что это такое я понял аж в 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 и информатику, мечта моя — выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.