Олимпиадное программирование для начинающих

Олимпиадное программирование для начинающих

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

На старте

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

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

С чего начать?

Сперва нужно освоить какой-нибудь язык программирования. Например, раньше учебным языком был Pascal. Сейчас принято начинать с Python, который популярен среди тех, кто хочет быстро научиться писать код. Этот язык очень дружелюбный к начинающим, у него есть подробная и понятная документация и большое количество библиотек. Но чтобы продолжать участвовать в более сложных олимпиадах, надо будет рано или поздно овладеть C++.

Минимум тем, которые нужно изучить: переменные, операторы присваивания, логические и арифметические операции, условные операторы, потом — массивы и циклы, процедуры и функции. Для того, чтобы в них разобраться, можно, например, посмотреть курс Михаила Густокашина по C++ на Stepik. С этой базой можно решать первые олимпиадные задачи.

Как тренироваться?

Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.

Я думаю, есть два основных способа выучить программирование:

1. «Задачное» обучение — изучение конструкции языка через решение абстрактных задач. Например, когда надо прочитать все числа из файла и подсчитать сумму нечетных.
2. Проектное обучение, при котором учащийся получает наглядный результат своей работы, небольшой работающий «продукт».

Олимпиадное программирование хорошо тем, что практиковаться можно и самостоятельно, без помощи преподавателя. Есть платформы, на которых доступно большое количество олимпиадных задач. Решаешь задачу, пишешь код, отправляешь его на проверку и тут же получаешь результат. Мгновенная обратная связь мотивирует продолжать заниматься программированием.

Например, есть сайт «Информатикс», созданный коллективом московских преподавателей олимпиадной информатики. На нём есть и теоретические материалы: например, вводные лекции по Python, к которым прикреплены примеры олимпиадных задач. Прошёл тему — и сразу выполняешь по ней задание.

Самая популярная платформа для решения задач — это codeforces.com, которую создал и активно развивает Михаил Мирзаянов. На ней постоянно проводятся контесты (соревнования), открытые для всех желающих. Они рассчитаны на людей с разным уровнем: от тех, кто только вчера узнал базовые конструкции языка, до настоящих профессионалов, которые выигрывали международные соревнования и занимаются спортивным программированием уже много лет.

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

Когда сталкиваетесь с незнакомым алгоритмом — знакомьтесь с ним, смотрите лекции на эту тему, изучайте статьи, форумы и книги. Например, «Алгоритмы: построение и анализ» Томаса Кормена и соавторов. Так выглядят дни тех, кто занимается олимпиадным программированием уже профессионально.

А ещё решать задачи гораздо приятнее и полезнее в команде. Ребята, которые занимаются в сообществе, как правило, достигают больших успехов.

Продолжение обучения

Когда человек освоил базу и знает конструкции языка, ему пора идти дальше: углубленно изучать теорию и разнообразные алгоритмы, которые позволяют по-новому работать с уже известными комбинаторными объектами. Знать алгоритмы и уметь применять сложные трюки — это хорошо, но задача никогда не состоит только из применения готовых знаний. Надо уметь сопоставлять разные параметры, вспоминать алгоритмы и модифицировать их для дальнейшего применения.

В любой задаче есть своя уникальная идея — даже если ты видел до этого тысячу других идей и задач, то 1001-я всё равно будет новой.

До многих вещей можно дойти самостоятельно, но проще и быстрее будет, если знающие люди расскажут готовые способы решения. Самый действенный путь — общаться с единомышленниками и посещать места, где делятся знаниями и опытом: выездные школы и сборы. Например, есть смена «Алгоритмы и анализ данных» в «Сириусе», где много времени уделяется тому, чтобы помочь ребятам прокачать необходимые навыки для участия в олимпиадах по информатике. Поищите и регулярные занятия, которые можно посещать круглый год: например, кружки олимпиадного программирования, которые работают в вашем городе.

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

Тактическое преимущество

Чтобы эффективно выполнять задачи, надо понимать, решение каких из них принесет наибольшую пользу в будущем.

Я подразделяю задачи на четыре уровня сложности:

• Первый уровень: даже не замечаешь, как решил задачу. Решение приходит в голову сразу же, как только прочитал условие. Это бесполезные с точки зрения опыта задачи, хотя их и можно встретить на олимпиаде. Если есть возможность их не решать — не решайте.
• Второй уровень: задание вызывает небольшое напряжение. Сходу его не решить, хотя и примерно ясно, в каком направлении нужно двигаться. На такие задания уходит минут 5-15. Подумал, попробовал наиболее очевидный вариант решения или два — и решил.
• Третий уровень: трудные, но подъёмные задачи. Для выполнения придётся опробовать или с нуля придумать новую идею. Не просто собрать решение из готовых кирпичиков, а распутать головоломку. Пока выполняешь такие задачи, осознаёшь то, с чем раньше не сталкивался, возможно, пробуешь малознакомые алгоритмы. На обдумывание может уйти час, а на написание кода — ещё пару часов. Это тяжело и требует волевых усилий, но очень полезно.
• Четвёртый уровень: не для тебя (пока). Например, ты семиклассник, а для решения задачи нужны знания университетских математических формул и громоздких алгоритмов. Прочитал разбор и всё равно вообще ничего не понял. Ты можешь попытаться разобраться и в итоге выполнить это задание, потратив колоссальное время, но получится неэффективно для общего результата.

На смене в «Сириусе» ребята, например, решали такие задачи:

Ошибки при подготовке к олимпиаде

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

Тут же сдаваться. «Если я не понял, как решать задачу за 15 минут, то я узнаю, как она решается, прочитав её разбор». При помощи ресурса Codeforces, про который я говорил выше, можно узнать, как автор видел решение этой задачи, и как эту задачу решили бы другие люди. Но ты не дал себе шанса подумать как следует, упустил возможность найти решение самостоятельно, а это плохо для опыта и развития интуиции.

Решать только те задачи, которые нравятся. В олимпиадном программировании существуют разные типы задач: некоторые требуют в первую очередь развитого математического аппарата (например, знания теории чисел), в других идёт упор на написание кода, в-третьих — на математику (системы уравнений, теория чисел), а иногда — комбинаторику (графы). Углубляться всегда надо в те области, где возникло сопротивление. Для успеха на соревнованиях полезнее решить пять задач на нелюбимую тему, чем на ту, которая легко даётся.

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

Что дают олимпиады?

1. Льготы при поступлении. Есть линейка всероссийских предметных олимпиад, диплом которых — билет в вуз на бюджетное место.
2. Олимпиадный опыт помогает проходить собеседования в крупные компании, так как на них очень часто дают олимпиадные задачи.
3. Призовое место — это весомое дополнение к любому портфолио и резюме. Перспектива повышать уровень олимпиадного программирования и дальше, поехать на международные соревнования. Например, на международный чемпионат по алгоритмическому программированию ICPC, который считается самым престижным соревнованием в мире.
4. Возможность попасть в специальные летние или зимние школы, на сборы, в проекты вроде «Сириуса», и стать частью сплоченного сообщества.
5. Даже если вы не будете занимать призовые места на олимпиадах, участие в них позволит набраться фундаментальных знаний и опыта разработки, разовьёт умение размышлять.

Источник

6 бесплатных ресурсов для подготовки к олимпиадам по программированию

Олимпиады по программированию полезны не только школьникам и студентам, но и вообще всем начинающим ИТ-специалистам. Они помогут прокачать навыки написания кода, выиграть денежные призы, попасть на бюджет в бакалавриат или магистратуру, пройти на стажировку в крупной компании.

Мы собрали несколько бесплатных ресурсов для тех, кто хочет попробовать себя в спортивном программировании, но не знает, с чего начать.

Быстрый старт в спортивное программирование

Онлайн-курс от МФТИ, где за четыре недели расскажут о базовых алгоритмах, теории чисел, динамическом программировании и теории графов

Codeforces

На платформе можно принять участие в онлайн-состязаниях — в том числе с денежными призами. Также доступен архив с заданиями прошедших соревнований и разборами решений

LeetCode

Задачи по программированию. Подбирать их можно по темам и уровню сложности. Есть подсказки, автоматическая проверка решений и обсуждение. Доступны почти все популярные языки — от С++ до Ruby

Timus Online Judge

Студенты и выпускники УрФУ публикуют задачи с уральских чемпионатов и олимпиад по программированию. Архив охватывает задания 1999—2020 годов, а решение можно проверить прямо на сайте

Aлгоритмика

Конспекты курсов Tinkoff Generation по олимпиадной математике, алгоритмам и машинному обучению. Тем много — от сортировки пузырьком до дискретного метода Лагранжа

Maximal

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

Больше об олимпиадах и льготах при поступлении

В нашем потоке «Образование». Рассказываем про продуктивную учебу, поступление в вуз, стипендии и стажировки

Еще полезные статьи про олимпиады и ИТ:

Новости из мира образования, советы по карьере и учебе, вдохновляющие истории — в нашем телеграм-канале: @t_obrazovanie.

Источник