Что такое олимпиадное программирование?
В России олимпиадным программированием занимаются уже достаточно давно. Школьные олимпиады проводятся с конца 80-х, студенческие с середины 90-х годов XX века. Так что это такое олимпиады по программированию нужны ли они или нет и если да то кому?
Давайте разберемся, что такое олимпиада по программированию?
Как устроена олимпиада?
Студенческая олимпиада организованна следующим образом:
Трое участников команды сидят перед одним компьютером. Им дается набор задач, которые они должны решить. Что значит решить задачу? Это значит написать программу, которая пройдет заранее заготовленный жюри набор тестов. Таким образом, задача решена, если она прошла весь набор, то есть полностью правильна с точки зрения жюри. Для любой программы есть ограничения по ресурсам, она не должна требовать слишком много памяти и работать слишком долго. Продолжительность олимпиады обычно 5 часов. Команды соревнуются между собой. Это значит, что в турнирной таблице выше находится та команда, которая решила больше задач. А из тех, которые решили одинаковое количество задач та, которая это сделала быстрее.
Школьные олимпиады обычно имеют свою особенность:
Чаще всего они не командные, а личные, и ребята не должны на 100% решить задачу, а могут решить только часть задачи и получить за это соответствующие баллы.
Какие задачи дают на олимпиадах?
Обычно это задачи из области программирования, информатики (Computer Science), различных разделов математики. Очень популярны задачи по поиску и обработке текста, задачи по криптографии, геолокации, теории игр, методов оптимизации, оптимального хранения и обработки данных, быстрого доступа к данным и другие.
На самом деле, каждый из нас встречается с решениями олимпиадных задач очень часто. Рассмотрим несколько примеров:
Поиск Маршрутов. Многие из нас пользуются различными приложениями по поиску маршрутов: 2GIS, Яндекс Карты, Google Maps и другие. Эти приложения подбирают для нас кратчайший маршрут с учетом разных факторов: транспорт, пробки, направление движения на дорогах, наличие пешеходного перехода и другие. Так вот, построить такой маршрут – это одна из классических олимпиадных задач: найти кратчайший путь в графе. Для этой ззадачи существуют различные подходы и алгоритмы. В частности, в создании сервиса Яндекс. Пробки активно принимали участие олимпиадники.
Другой пример: поиск сроки в тексте, вы часто пользуетесь поиском? Так вот поиск – тоже олимпиадная задача.
Третий пример уже более специализированный: во многих организациях возникает поток заказов, задач или заданий Есть несколько исполнителей, каждый может выполнять какие-то заказы, но стоимость выполнения разная. Как быстро и с минимальными затратами выполнить все заказы?
И так далее. Ззадач много из разных областей, причем даются они участникам не в сухой математической формулировке, а так как они приходят из жизни, правда, иногда с долей юмора.
Какие навыки развиваются у олимпиадника?
Во-первых, ребята учатся решать не тривиальные задачи, часто из разных областей математики и программирования. Это позволяет с одной стороны иметь большой математический кругозор, с другой стороны видеть, что эти абстрактные математические задачи имеют привязку к жизни. Во вторых, оценивать свои решения в зависимости от имеющихся ресурсов (обычно это время и память, которые используют программы). Вряд ли кому-то нужна программа, которая работает сотни лет или требует все имеющиеся жесткие диски в мире. В-третьих, работать качественно и в короткие сроки, в олимпиадах время ограничено и принимается решение только 100% верное. В-четвертых, работать в команде: у участников есть только один компьютер, поэтому они вынуждены обсуждать, распределять роли в команде, писать код по очереди, помогать сокоманднику, если у него что-то пошло не так. В-пятых, ребята учатся искать потенциальные проблемы своих решений, готовить контрольные примеры, тестировать свои решения. В-шестых, это соревнование – ребята учатся какого это обходить других и когда обходят тебя, как взаимодействовать с другими и видят насколько много людей участвуют в этом движении.
Кому это все нужно?
Это нужно науке.
Ребята принимающие участие в олимпиадах имеют чаще всего уровень знаний математики намного выше среднего студента, умеет решать нестандартные задачи, имеет большой кругозор из разных областей математики и информатики, чего часто не хватает другим студентам. Да, другие студенты часто знают многое, но олимпиадники умеют применять свои знания при решении задач.
Отличие олимпиад от классической науки в том, что олимпиадники обычно решают задачи в короткие сроки, а ученые проводят за исследованиями много дней, и только тогда находят решения. Однако, олимпиадники также проводят много времен, раздумывая над задачами не во время самой олимпиады, а при подготовке. При этом на самой олимпиаде чаще всего применятся уже наработанные знания и навыки, всплывающие из глубин памяти и интеллекта. Те, которые были выработаны в процессе долгих размышлений.
Есть много примеров, когда олимпиадники становятся учеными: многие олимпиадники КФУ защитили свои кандидатские или сейчас в процессе, в Москве и Петербурга вы можете встретить ученых, которые в своем прошлом участвовали в олимпиадах. Известные ученые в области квантовой информатики – победители олимпиад.
Это нужно промышленности.
Навыки создания оптимальных, надежных программ в короткие сроки, работы в команде, умение решать нетривиальные задачи – это то, что требуется любой IT-компании.
Многие компании, такие как Facebook, Google, Яндекс, Mail.ru, VK, Huaweii и друге организовывают собственные олимпиады и приглашают к себе сотрудников по их результатам. Многие компании принимают олимпиадников без собеседования или на льготных условиях. Третьи компании, к примеру Google, и другие проводят собеседование на олимпиадных задачах.
Потому что они понимают, что люди, которые могу решить сложную задачу, написать эффективный код и работать в команде – это те кто смогут обеспечить им обработку не 100 тысяч пользователей, а миллиона или 100 миллионов с той же скоростью, это те кто потом помогут написать распознавание лиц в их программах или построение оптимального маршрута. Это те, кто для компаний помогут заработать новые деньги, а пользователи из-за них будут считать, что внутри программ скрыта “магия”.
Да и просто люди, которые в студенческие годы написали сотни тысяч программ на много лучше будут работать, чем те, которые писали 100-200 программ в рамках своих домашних заданий в университете.
Небольшая социально-культурная составляющая.
Олимпиады позволяют познакомиться ребятам с будущей элитой IT-сообщества, попутешествовать по разным городам, Принять участие в соревнованиях, померяться силами с лучшими программистами мира.
В заключении.
Некоторые люди ругают олимпиады, другие их восхваляют. Нельзя сказать что олимпиады – полная замена каким-то предметам в университете, как некоторые пытаются это представить, но олимпиады это очень хорошее подспорье для будущих ученых, программистов, аналитиков.
Это интеллектуальный спорт, в котором спортсмены после окончания своей карьеры могут приносить реальную пользу обществу. Скажите, много ли видов спорта могут похвастаться этим? Это тот спорт, в котором участвуют большинство ведущих университетов мира. Победители в котором, известны IT и научному сообществу.
Бывших не бывает. Как опыт спортивного программирования влияет на работу с реальным кодом
Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – 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:
Чек-лист: олимпиадное программирование — с чего начать школьнику?
Ведущий разработчик «Яндекса» и руководитель службы поисковых подсказок
Глеб Евстропов, ведущий разработчик «Яндекса» и руководитель службы поисковых подсказок, член жюри Всероссийской олимпиады школьников по информатике, рассказал, как начать заниматься спортивным программированием, за какие задачи браться в первую очередь и какие преимущества даёт участие в олимпиадах.
Олимпиадное или спортивное программирование — это участие в соревнованиях по решению нетривиальных алгоритмических задач. Оно позволяет получить фундаментальные знания, научиться эффективнее писать код и подготовиться к дальнейшей карьере — победителей и призеров олимпиад охотно нанимают ведущие IT-компании.
На старте
Программирование — это умение превращать объекты из реальных задач в абстрактные сущности и выражать их взаимодействие на языке программного кода. Поэтому главное условие для изучения программирования — абстрактное мышление, на которое сильно влияет уровень преподавания школьной математики.
Если вам интересно программирование, и у вас уже начало формироваться абстрактное мышление, с поддержкой увлечённого педагога довольно быстро освоите базовые знания, достаточные для участия в олимпиадах. Однако подготовиться к соревнованиям можно и самостоятельно, главное — сопровождать каждую пройденную тему, даже самую простую, усиленной практикой.
С чего начать?
Сперва нужно освоить какой-нибудь язык программирования. Например, раньше учебным языком был Pascal. Сейчас принято начинать с Python, который популярен среди тех, кто хочет быстро научиться писать код. Этот язык очень дружелюбный к начинающим, у него есть подробная и понятная документация и большое количество библиотек. Но чтобы продолжать участвовать в более сложных олимпиадах, надо будет рано или поздно овладеть C++.
Минимум тем, которые нужно изучить: переменные, операторы присваивания, логические и арифметические операции, условные операторы, потом — массивы и циклы, процедуры и функции. Для того, чтобы в них разобраться, можно, например, посмотреть курс Михаила Густокашина по C++ на Stepik. С этой базой можно решать первые олимпиадные задачи.
Как тренироваться?
Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.
Расскажи, как цифровая трансформация изменила твой бизнес
Я думаю, есть два основных способа выучить программирование:
Олимпиадное программирование хорошо тем, что практиковаться можно и самостоятельно, без помощи преподавателя. Есть платформы, на которых доступно большое количество олимпиадных задач. Решаешь задачу, пишешь код, отправляешь его на проверку и тут же получаешь результат. Мгновенная обратная связь мотивирует продолжать заниматься программированием.
Например, есть сайт «Информатикс», созданный коллективом московских преподавателей олимпиадной информатики. На нём есть и теоретические материалы: например, вводные лекции по Python, к которым прикреплены примеры олимпиадных задач. Прошёл тему — и сразу выполняешь по ней задание.
Самая популярная платформа для решения задач — это codeforces.com, которую создал и активно развивает Михаил Мирзаянов. На ней постоянно проводятся контесты (соревнования), открытые для всех желающих. Они рассчитаны на людей с разным уровнем: от тех, кто только вчера узнал базовые конструкции языка, до настоящих профессионалов, которые выигрывали международные соревнования и занимаются спортивным программированием уже много лет.
Путь к успеху — решать, решать, а потом ещё немного решать. Регулярно писать контесты — хотя бы один раз в неделю, а лучше два. Если решение задачи после долгих раздумий так и не нашлось, читайте её разбор.
Когда сталкиваетесь с незнакомым алгоритмом — знакомьтесь с ним, смотрите лекции на эту тему, изучайте статьи, форумы и книги. Например, «Алгоритмы: построение и анализ» Томаса Кормена и соавторов. Так выглядят дни тех, кто занимается олимпиадным программированием уже профессионально.
А ещё решать задачи гораздо приятнее и полезнее в команде. Ребята, которые занимаются в сообществе, как правило, достигают больших успехов.
Продолжение обучения
Когда человек освоил базу и знает конструкции языка, ему пора идти дальше: углубленно изучать теорию и разнообразные алгоритмы, которые позволяют по-новому работать с уже известными комбинаторными объектами. Знать алгоритмы и уметь применять сложные трюки — это хорошо, но задача никогда не состоит только из применения готовых знаний. Надо уметь сопоставлять разные параметры, вспоминать алгоритмы и модифицировать их для дальнейшего применения.
В любой задаче есть своя уникальная идея — даже если ты видел до этого тысячу других идей и задач, то 1001-я всё равно будет новой.
До многих вещей можно дойти самостоятельно, но проще и быстрее будет, если знающие люди расскажут готовые способы решения. Самый действенный путь — общаться с единомышленниками и посещать места, где делятся знаниями и опытом: выездные школы и сборы. Например, есть смена «Алгоритмы и анализ данных» в «Сириусе», где много времени уделяется тому, чтобы помочь ребятам прокачать необходимые навыки для участия в олимпиадах по информатике. Поищите и регулярные занятия, которые можно посещать круглый год: например, кружки олимпиадного программирования, которые работают в вашем городе.
Самостоятельное обучение по книгам и материалам из интернета — это длинный и сложный путь, хотя поиск самой информации и не составит труда. В частности, на сайте MAXimal собраны 145 алгоритмов для решения разных задач, а также в открытом доступе опубликованы книги по алгоритмам, оптимизации, С++ и Java.
Тактическое преимущество
Чтобы эффективно выполнять задачи, надо понимать, решение каких из них принесет наибольшую пользу в будущем.
Я подразделяю задачи на четыре уровня сложности:
На смене в «Сириусе» ребята, например, решали такие задачи:
Ошибки при подготовке к олимпиаде
Ударяться в крайности. «Я всегда дохожу до решения сам и никогда никуда не подсматриваю. Если мне нужно будет потратить три недели, чтобы решить задачу, то я потрачу три недели». До всего доходить самостоятельно — это круто, но неэффективно. К тому же, этот путь потребует слишком много силы воли, которая редко у кого встречается, а также может привести к выгоранию и утрате мотивации.
Тут же сдаваться. «Если я не понял, как решать задачу за 15 минут, то я узнаю, как она решается, прочитав её разбор». При помощи ресурса Codeforces, про который я говорил выше, можно узнать, как автор видел решение этой задачи, и как эту задачу решили бы другие люди. Но ты не дал себе шанса подумать как следует, упустил возможность найти решение самостоятельно, а это плохо для опыта и развития интуиции.
Решать только те задачи, которые нравятся. В олимпиадном программировании существуют разные типы задач: некоторые требуют в первую очередь развитого математического аппарата (например, знания теории чисел), в других идёт упор на написание кода, в-третьих — на математику (системы уравнений, теория чисел), а иногда — комбинаторику (графы). Углубляться всегда надо в те области, где возникло сопротивление. Для успеха на соревнованиях полезнее решить пять задач на нелюбимую тему, чем на ту, которая легко даётся.
Не уделять достаточно внимания коду. В процессе написания программы наброски решения переводятся на формальный язык. Иногда ты за пять минут находишь решение и потом пару часов пишешь код, а бывает и наоборот. Писать код так, чтобы в нём было меньше ошибок, способность эти ошибки находить и исправлять — навык, который можно и нужно нарабатывать. Чем больше пишешь код, тем лучше начинаешь это делать. Также полезно обсуждать с другими людьми, как писать программы с меньшим количеством ошибок и читать чужой код.