Что такое спортивное программирование
Мастера Мария и Жуан открывают маленький магазин керамики в Порту. Они хотят сделать привлекательную витрину, но из-за тесноты их магазина вынуждены выкладывать образцы плиток в два ряда на одной полке. Каждая из плиток Жуана имеет одну из плиток Марии перед собой, а каждая из плиток Марии имеет плитку Жуана позади себя. Плитки ручной работы разного размера, поэтому необходимо, чтобы плитка позади всегда была выше плитки в первом ряду, чтобы прохожие могли разглядеть обе. Для удобства покупателей плитки в каждом ряду располагаются в порядке убывания цены слева направо. Плитки одинаковой цены могут быть расположены в любом порядке в зависимости от условий видимости, указанных выше.
Ваша задача — найти порядок плиток в каждом ряду, который удовлетворяет эти ограничения, или определить, что такого порядка не существует.
Баги мнит себя Гаем Юлием Цезарем и любит громогласно его цитировать при каждом удобном случае, выдавая мысли Цезаря за свои. Проги пошутил над Багги и зашифровал в стиле Цезаря список цитат, которыми пользуется Багги. Багги в панике. Если хотите, помогите ему расшифровать известную цитату:
Напишите программу, которая для вышеприведенного шифртекста выводит соответствующий открытый текст.
Помимо студенческой олимпиады, есть и одиночные онлайн-первенства. Так, например, самая известная платформа Codeforces не только проводит регулярные турниры, но и подсчитывает индивидуальный рейтинг спортсменов по шахматной системе Эло — и его лидеры становятся авторитетом не только в рамках этих соревнований, но и за пределами мира спортивного программирования.
Свои крупные турниры проводят и техногиганты. Самые известные из них: Google Code Jam и Facebook Hacker Cup. Такие события помогают компаниям завязывать контакты с перспективными специалистами, а сами программисты не только соревнуются за ценные призы, но и становятся частью активного сообщества. С каких-то пор задачи, подобные тем, что решают участники на турнирах, стали частью устройства на работу — так, например, Google India предоставляет кандидатам возможность продемонстрировать свои умения в решениях алгоритмических задач как один из промежуточных этапов перед интервью.
Спортивное программирование и 5 ресурсов для решения задач
Виталий Подоба – программист Python, поделился своим опытом решения задач, и в этом поможет спортивное программирование c соответствующими онлайн-ресурсами.
Чтобы пользоваться ресурсами, приведенными в статье, необходимо знание английского языка.
Раньше на собеседованиях в IT-компаниях вроде Microsoft, IBM, Google кандидатам было принято давать тест-пазлы. Считалось, что если ты способен решать задачи на сообразительность, логику и эрудицию, ты будешь хорошим работником.
Когда перед автором встала задача собрать свою команду, он тоже пытался придерживаться этого правила. Однако после череды неудачных попыток ему стало понятно, что претенденту лучше давать задачи, которые он будет решать в течение рабочего дня. Ведь, как выяснилось на практике, хороший работник и хорошо решающий IT-задачки – это не одно и то же. Поэтому важность головоломок на собеседовании стала значительно меньше.
Но стоит отметить, что IT-задачи все-таки полезны. И вот несколько причин:
Решать такие задачи особенно полезно, когда вам не хватает задач и проектов, которые бы способствовали поиску свежих идей и новых инструментов, подходов для их решения. Это будет своего рода тренинг, не дающий “засохнуть” вашему мозгу.
Такие задачи принято называть спортивным программированием. Часто в основе ресурсов, на которых они размещены, лежит принцип соревнования: решить задачу нужно быстрее и лучше.
Спортивное программирование: 5 онлайн-ресурсов с задачами
Разобравшись с тем, что такое спортивное программирование, и чем оно полезно, можно приступить к решению. Ниже представлены 5 онлайн-ресурсов, где можно попрактиковаться в решении задач. Автор поделился собственным опытом работы с каждым из них.
Project Euler
Top Coder
Преимущество TopCoder заключается еще и в том, что крупнейшие IT компании обращают внимание на данный ресурс при поиске новых сотрудников. У сайта огромное сообщество, в его базе миллионы пользователей.
Соревнования проходят ежедневно и еженедельно. И, хотя задачи действительно сложные, время, потраченное на их решение, обязательно окупится. По крайней мере ознакомиться с заданиями, которые решает мировое сообщество программистов и математиков, обязательно стоит.
Hacker Earth
HackerEarth оснащен богатым инструментарием, способным проверить ваше решение. Их программное обеспечение может проверить не только технические, но и логические навыки решающего. Также платформа используется IT-компаниями для поиска талантливых разработчиков. Уровень сложности заданий выше среднего, поэтому новичкам здесь делать нечего.
CoderByte
На форуме CoderByte каждый может задать вопросы по поводу решения той или иной задачи, а активное сообщество поможет найти правильный ответ. Благодаря такой поддержке любой начинающий разработчик сможет получить богатый опыт решения непростых заданий.
Проект получил необходимую поддержку на Kickstarter и с тех пор только набирает обороты. Ресурс идеально подойдет как начинающим разработчикам, так и тем, у кого имеется некоторый опыт.
Daily Programmer
Daily Programmer обычная группа на Reddit. В ней регулярно публикуют и обсуждают различные задачи. В неделю появляются 3 новые задачи, а в архиве их уже несколько сотен. Участники группы читают каждый комментарий и делятся собственным мнением по поводу вашего решения. В целом, это очень неплохой ресурс, чтобы пообщаться с хорошими программистами и научиться новому.
Чек-лист: олимпиадное программирование — с чего начать школьнику?
Ведущий разработчик «Яндекса» и руководитель службы поисковых подсказок
Глеб Евстропов, ведущий разработчик «Яндекса» и руководитель службы поисковых подсказок, член жюри Всероссийской олимпиады школьников по информатике, рассказал, как начать заниматься спортивным программированием, за какие задачи браться в первую очередь и какие преимущества даёт участие в олимпиадах.
Олимпиадное или спортивное программирование — это участие в соревнованиях по решению нетривиальных алгоритмических задач. Оно позволяет получить фундаментальные знания, научиться эффективнее писать код и подготовиться к дальнейшей карьере — победителей и призеров олимпиад охотно нанимают ведущие IT-компании.
На старте
Программирование — это умение превращать объекты из реальных задач в абстрактные сущности и выражать их взаимодействие на языке программного кода. Поэтому главное условие для изучения программирования — абстрактное мышление, на которое сильно влияет уровень преподавания школьной математики.
Если вам интересно программирование, и у вас уже начало формироваться абстрактное мышление, с поддержкой увлечённого педагога довольно быстро освоите базовые знания, достаточные для участия в олимпиадах. Однако подготовиться к соревнованиям можно и самостоятельно, главное — сопровождать каждую пройденную тему, даже самую простую, усиленной практикой.
С чего начать?
Сперва нужно освоить какой-нибудь язык программирования. Например, раньше учебным языком был Pascal. Сейчас принято начинать с Python, который популярен среди тех, кто хочет быстро научиться писать код. Этот язык очень дружелюбный к начинающим, у него есть подробная и понятная документация и большое количество библиотек. Но чтобы продолжать участвовать в более сложных олимпиадах, надо будет рано или поздно овладеть C++.
Минимум тем, которые нужно изучить: переменные, операторы присваивания, логические и арифметические операции, условные операторы, потом — массивы и циклы, процедуры и функции. Для того, чтобы в них разобраться, можно, например, посмотреть курс Михаила Густокашина по C++ на Stepik. С этой базой можно решать первые олимпиадные задачи.
Как тренироваться?
Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.
Я думаю, есть два основных способа выучить программирование:
Олимпиадное программирование хорошо тем, что практиковаться можно и самостоятельно, без помощи преподавателя. Есть платформы, на которых доступно большое количество олимпиадных задач. Решаешь задачу, пишешь код, отправляешь его на проверку и тут же получаешь результат. Мгновенная обратная связь мотивирует продолжать заниматься программированием.
Например, есть сайт «Информатикс», созданный коллективом московских преподавателей олимпиадной информатики. На нём есть и теоретические материалы: например, вводные лекции по Python, к которым прикреплены примеры олимпиадных задач. Прошёл тему — и сразу выполняешь по ней задание.
Самая популярная платформа для решения задач — это codeforces.com, которую создал и активно развивает Михаил Мирзаянов. На ней постоянно проводятся контесты (соревнования), открытые для всех желающих. Они рассчитаны на людей с разным уровнем: от тех, кто только вчера узнал базовые конструкции языка, до настоящих профессионалов, которые выигрывали международные соревнования и занимаются спортивным программированием уже много лет.
Путь к успеху — решать, решать, а потом ещё немного решать. Регулярно писать контесты — хотя бы один раз в неделю, а лучше два. Если решение задачи после долгих раздумий так и не нашлось, читайте её разбор.
Когда сталкиваетесь с незнакомым алгоритмом — знакомьтесь с ним, смотрите лекции на эту тему, изучайте статьи, форумы и книги. Например, «Алгоритмы: построение и анализ» Томаса Кормена и соавторов. Так выглядят дни тех, кто занимается олимпиадным программированием уже профессионально.
А ещё решать задачи гораздо приятнее и полезнее в команде. Ребята, которые занимаются в сообществе, как правило, достигают больших успехов.
Продолжение обучения
Когда человек освоил базу и знает конструкции языка, ему пора идти дальше: углубленно изучать теорию и разнообразные алгоритмы, которые позволяют по-новому работать с уже известными комбинаторными объектами. Знать алгоритмы и уметь применять сложные трюки — это хорошо, но задача никогда не состоит только из применения готовых знаний. Надо уметь сопоставлять разные параметры, вспоминать алгоритмы и модифицировать их для дальнейшего применения.
В любой задаче есть своя уникальная идея — даже если ты видел до этого тысячу других идей и задач, то 1001-я всё равно будет новой.
До многих вещей можно дойти самостоятельно, но проще и быстрее будет, если знающие люди расскажут готовые способы решения. Самый действенный путь — общаться с единомышленниками и посещать места, где делятся знаниями и опытом: выездные школы и сборы. Например, есть смена «Алгоритмы и анализ данных» в «Сириусе», где много времени уделяется тому, чтобы помочь ребятам прокачать необходимые навыки для участия в олимпиадах по информатике. Поищите и регулярные занятия, которые можно посещать круглый год: например, кружки олимпиадного программирования, которые работают в вашем городе.
Самостоятельное обучение по книгам и материалам из интернета — это длинный и сложный путь, хотя поиск самой информации и не составит труда. В частности, на сайте MAXimal собраны 145 алгоритмов для решения разных задач, а также в открытом доступе опубликованы книги по алгоритмам, оптимизации, С++ и Java.
Тактическое преимущество
Чтобы эффективно выполнять задачи, надо понимать, решение каких из них принесет наибольшую пользу в будущем.
Я подразделяю задачи на четыре уровня сложности:
На смене в «Сириусе» ребята, например, решали такие задачи:
Ошибки при подготовке к олимпиаде
Ударяться в крайности. «Я всегда дохожу до решения сам и никогда никуда не подсматриваю. Если мне нужно будет потратить три недели, чтобы решить задачу, то я потрачу три недели». До всего доходить самостоятельно — это круто, но неэффективно. К тому же, этот путь потребует слишком много силы воли, которая редко у кого встречается, а также может привести к выгоранию и утрате мотивации.
Тут же сдаваться. «Если я не понял, как решать задачу за 15 минут, то я узнаю, как она решается, прочитав её разбор». При помощи ресурса Codeforces, про который я говорил выше, можно узнать, как автор видел решение этой задачи, и как эту задачу решили бы другие люди. Но ты не дал себе шанса подумать как следует, упустил возможность найти решение самостоятельно, а это плохо для опыта и развития интуиции.
Решать только те задачи, которые нравятся. В олимпиадном программировании существуют разные типы задач: некоторые требуют в первую очередь развитого математического аппарата (например, знания теории чисел), в других идёт упор на написание кода, в-третьих — на математику (системы уравнений, теория чисел), а иногда — комбинаторику (графы). Углубляться всегда надо в те области, где возникло сопротивление. Для успеха на соревнованиях полезнее решить пять задач на нелюбимую тему, чем на ту, которая легко даётся.
Не уделять достаточно внимания коду. В процессе написания программы наброски решения переводятся на формальный язык. Иногда ты за пять минут находишь решение и потом пару часов пишешь код, а бывает и наоборот. Писать код так, чтобы в нём было меньше ошибок, способность эти ошибки находить и исправлять — навык, который можно и нужно нарабатывать. Чем больше пишешь код, тем лучше начинаешь это делать. Также полезно обсуждать с другими людьми, как писать программы с меньшим количеством ошибок и читать чужой код.
Бывших не бывает. Как опыт спортивного программирования влияет на работу с реальным кодом
Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – 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: