Программирование, тригонометрия, рекурсивный перебор: как готовиться к олимпиадам по информатике
Олимпиады — отличный способ не только продемонстрировать свои знания, но и шанс поступить без экзаменов в хороший вуз. Наш блогер Алексей Малеев рассказывает всё, что нужно знать об олимпиадах по информатике, и объясняет, как к ним готовиться.
Прежде всего, надо понять, где вы хотите участвовать и какую цель ставите перед собой. Из наиболее авторитетных олимпиад по информатике можно выделить:
- IOI — ежегодная международная олимпиада по информатике среди школьников (Межнар).
- ВсОШ по информатике — индивидуальная всероссийская олимпиада школьников по информатике (Всерос).
- ВКОШП — всероссийская командная олимпиада школьников по программированию.
- Технокубок — ежегодная олимпиада по программированию для учащихся 8–11 классов, организованная МФТИ, МГТУ им. Н. Э. Баумана и компанией Mail.ru Group.
- Всесибирская открытая олимпиада школьников по информатике
- Московская олимпиада школьников
- Олимпиада школьников «Ломоносов»
- Открытая Олимпиада Университета Иннополис для школьников
- Открытая олимпиада школьников по программированию
- Межрегиональная олимпиада школьников «Высшая проба»
- Олимпиада школьников СПбГУ
- Открытая олимпиада школьников по программированию «Когнитивные технологии»
Если ваша цель — поступить в топовый профильный вуз, для этого нужно либо стать призёром олимпиады первого уровня, либо призёром Всероссийской олимпиады. Конечно, чем раньше вы начнёте заниматься, тем лучше. Мало кто становится призером Всероса с первой попытки. Начинать готовиться лучше не позже 9 класса.
Если перед вами задача — попасть в сборную на Международную олимпиаду в 9-10 классе, то надо начинать заниматься еще раньше — с 6-7 класса.
С чего начать
Подготовку надо начинать с выбора языка программирования. Популярностью сейчас пользуются C++, Python, Java, Pascal, но для олимпиад по информатике мы рекомендуем именно C++. Pascal на олимпиадах по программированию не пригодится, потому что его отменили. А Python, хотя и многих школьников учат ему, мы не рекомендуем, потому что он медленный и по сути является интерпретатором и на нём нельзя решить все задачи. Но если вы уже знакомы с Python, вам это пригодится в решении нескольких простых задач, например, задач с длинной арифметикой или написать какой-то скрипт для тестирования.
В дальнейшем мы будем говорить про C++. Здесь надо знать базовый синтаксис, владеть функциями, классами, уметь работать со стандартными алгоритмами и структурами данных библиотеки STL (sort, vector, set, map, pair и т. п.) и т. д. Освоение языка начинаем с изучения базовых вещей и задач, таких как: ввод-вывод, преобразование данных, операторы цикла, перебор. Начинающие могут брать задачи с онлайн-архивных ресурсов — например, acm.timus.ru или с informatics.mccme.ru. Начинать лучше с тех задач, которые на платформе решили больше всего пользователей. Потом переходить к базовым алгоритмам, например, начать с алгоритмов сортировки, двоичного поиска, простейших понятий о динамическом программировании.
При подготовке важно уделять внимание самым разным темам и быть готовым ко всему. Например, если на олимпиаде дают восемь задач, то скорее всего все восемь задач будут на разные темы. Но главное — это понимать, что в информатике без серьёзной математической подготовки вероятность успеха невелика.
Что нужно знать, кроме языков программирования?
Математику и тригонометрию
По математике нужно знать: делимость, свойства делимости, представление целых чисел, геометрические задачи. Геометрия в информатике немного другая, не такая, как в школе. 90% задач по геометрии в информатике решаются через векторы. В векторном представлении формулы выглядят совсем не страшными. Можно решать задачи на e-maxx.ru, acm.mipt.ru или codeforces.com и потом участвовать в онлайн-соревнованиях.
Требуется понимание, как устроен компьютер, что такое точность вычислений, нужно знать типы данных, сколько бит занимает целое число, уметь проводить вычисления с плавающей точкой, потому что на это часто бывают задачи.
С формулами типа Герона с корнями, которые даются в школе, никакие задачи по информатике не решишь. А вот тригонометрию знать очень желательно, хотя бы для того, чтобы лучше понять векторы. Тригонометрия используется в любых геометрических задачах, таких как поиск расстояния между двумя отрезками, проверка факта пересечения отрезков, поиск расстояния от точки до прямой, определение взаимного расположение окружностей и т. п.
Рассмотрим для примера задачу, в которой нужно найти расстояние от заданной точки С до отрезка AB. Сначала нужно понять, является ли один из углов CAB и CBA тупым; это легко сделать с помощью скалярного произведения. Если, скажем, угол САВ тупой, то ответ — это расстояние от С до А; аналогично с СВА. Если же оба угла тупые, то ответ — это высота треугольника ABC, равная удвоенной площади, деленной на длину отрезка АВ; площадь можно найти через косое (векторное) произведение. Таким образом, получилось простое решение, не использующее ничего, кроме школьной тригонометрии и векторов.
Динамическое программирование
Также для участия в олимпиадах надо знать динамическое программирование. Задачи на динамику будут практически в каждой олимпиаде, включая региональные. Это очень важная тема. Уметь оценивать скорость работы программы, асимптотику, растет ли скорость как O(n), O(n^2) («n квадрат») или как логарифм.
Классический пример задачи: черепашка движется из верхнего левого угла в правый нижний, в клетках поля написаны отрицательные числа. Она может двигаться только вниз или вправо. Нужно пройти и собрать наибольшую сумму. Это задача на двумерную динамику. Бывают задачи вида «найдите количества последовательностей длины N из нулей и единиц, в которых нет двух единиц подряд», решаемые с помощью чисел Фибоначчи, и многие другие. Это нужно решать через числа Фибоначчи.
В чём ещё надо разобраться?
Хотя в стандартной библиотеке языка C сортировка есть, но все равно необходимо уметь написать алгоритмы сортировки лучше, чем за N2. Например, знать сортировку слияния (Merge sort).
Нужно уметь решать уравнения методом двоичного поиска. Задача может звучать так: «найти корень уравнения, если известно, что в одной точке величина отрицательная, в другой — положительная». Для решения всякий раз берем середину отрезка и смотрим, поменялся ли знак в этой середине.
На олимпиаде надо знать вещи типа алгоритма Евклида для простых чисел. Надо уметь находить взаимную простоту чисел, уметь работать с остатками от деления по модулю
Если сложение, умножение, вычитание — это довольно простые вещи, то для деления будет нужен нетривиальный алгоритм быстрого возведения в степень. В очень многих олимпиадах ответ требуется вывести в виде остатка от деления на какое-то большое простое число.
Из того, что не проходят в школе надо также знать темы, касающиеся теории графов: что такое ориентированный и неориентированный граф, представление графа в виде списка, в виде матрицы и в виде списка вершин, базовые алгоритмы, обход в ширину, обход в глубину, компоненты связности, топологическая сортировка остовные деревья и т. п.
Надо научиться решать задачи на рекурсивный перебор, типа задачи обхода доски ходом коня. Лучше найти какой-нибудь продвинутый учебник по информатике. На начальном этапе стоит ознакомиться с книгами «Программирование: теоремы и задачи» А. Х. Шеня и «Программирование в алгоритмах» С. М. Окулова. Хорошим помощником также будет книга Е. В. Андреевой «Программирование — это так просто, программирование — это так сложно». Недавно вышла неплохая книга Антти Лааксонена «Олимпиадное программирование». Она для студентов, но первые главы пригодятся школьникам. Помимо различных приемов проектирования алгоритмов в ней подробно описано, как готовиться к олимпиадам, какими качествами нужно обладать, чтобы добиться высоких результатов.
От теории к практике
После освоения базы надо начинать решать задачи по той тематике, которую вы уже освоили. Обязательно не просто «придумывать» алгоритм, но писать программу на одном из языков программирования и сдавать в тестирующую систему. Если задача не проходит, нужно искать ошибки в коде; для этого необходимо проанализировать правильность алгоритма, тестировать программу и т. д.
Если решить задачу продолжительное время не удается, то необходимо изучить разбор задачи; но после этого желательно написать предлагаемый в разборе алгоритм и сдать задачу, чтобы удостовериться, что вы освоили этот алгоритм. Для этого на олимпиадных школах и на международных сборах всегда есть «дорешка». На ней можно задать дополнительные вопросы преподавателям. На выездных школах дети много общаются с преподавателями, там отработана система подготовки, потому занятия проходят очень эффективно.
В качестве примера разбора возьмем классическую олимпиадную задачу.
Задача «Рыцари и лжецы»
- Имя входного файла: standard input
- Имя выходного файла: standard output
- Ограничение по времени: 1 секунда
- Ограничение по памяти: 64 мебибайта
На острове Буяне жили N человек, каждый из которых был либо рыцарем, либо лжецом. Все они встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?». При этом каждый человек сказал, что он — рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: ответ «он рыцарь» обозначался за 1, ответ «он лжец» — за 0.
Все ответы были записаны в строку через пробел в порядке опроса (совпадающем с порядком обхода). Последний спрошенный человек отвечал на вопрос о первом.
Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.
Формат входных данных:
Первая строка входного файла содержит число N (1 <= N <= 255) — количество жителей острова Буян. Во второй строке заданы N целых чисел a_i (0 <= a_i <= 1), где a_i — ответ i-го в порядке обхода жителя на вопрос о его соседе слева. Гарантируется, что входные данные непротиворечивы, то есть что как минимум одно решение всегда существует.
Формат выходных данных:
Выведите одно число — наименьшее возможное количество рыцарей среди жителей острова.
Пример:
Решение:
- Имя входного файла: standard input
- Имя выходного файла: standard output
- Ограничение по времени: 1 секунда
- Ограничение по памяти: 64 мебибайта
Задача о рыцарях и лжецах — переборная. К счастью, перебор можно ограничить всего лишь двумя вариантами: первый человек — рыцарь или лжец? Предположив один из двух вариантов, можно однозначно вычислить, рыцарь или лжец следующий (так как человек с известным статусом сказал про человека слева) и так далее по индукции до первого. В процессе индукции можно считать, сколько у нас рыцарей. Когда по индукции выяснен статус первого жителя, проверяем, соответствует ли он нашему предположению. Если же соответствующих вариантов 2, то выбираем тот, в котором меньше рыцарей (то есть заведомо присутствует столько-то, а может быть, есть и больше).
Где можно готовиться
Готовиться в одиночку намного сложнее, а школьных уроков по информатике недостаточно для успешного выступления на олимпиадах. Нужно иметь хорошую алгоритмическую подготовку, а не только уметь решать стандартные задачи, и безупречно владеть языками программирования, которые используются на олимпиадах. Большинство победителей олимпиад посещают различные факультативы, участвуют в выездных школах, где можно пообщаться с преподавателями, единомышленниками и получить от них новые знания. Это веселее, интереснее и, что важно, продуктивнее.
Например, Олимпиадные школы МФТИ, которые мы проводим на кампусе университета в летние и зимние каникулы. Ежедневно ребята полтора часа слушают лекции, полтора часа занимаются практикой. Зависимо от уровня подготовки ребят распределяют по группам: Информатика+Информатика, Информатика-Профи, Информатика Hard. Есть группы по обучению C++ с нуля, и группы, в которых учат базовые алгоритмы и готовят победителей Всероса и Межнара.
Поэтому как начинающему, так и опытному олимпиаднику будут интересны занятия. На выездных школах дети много общаются с преподавателями, там отработана система подготовки, потому занятия проходят очень эффективно.
На codeforces.com участвовать в соревнованиях могут даже новички, на acm.timus.ru тоже можно найти интересные задачи для подготовки. Также рекомендую курс на Stepik «Быстрый старт в спортивное программирование», который прошли уже свыше 9 тысяч человек.
Сложный уровень и Межнар
После базовых знаний надо приступать к освоению более продвинутых алгоритмов. В частности, познакомиться с алгоритмами нахождения кратчайшего пути в графе (алгоритмами Дейкстры, Флойда, Форда-Беллмана). Также надо изучить геометрию (тернарный поиск, алгоритмы поиска выпуклой оболочки, метод сканирующей прямой), базовую теорию игр (ретроанализ, теория Шпрага-Гранди). Более сложное динамическое программирование — динамика на деревьях, на подотрезках, подмножествах, динамика по профилю.
На студенческих соревнованиях появляются задачи на преобразование Фурье, задачи на потоки, паросочетания, стереометрические задачи на точность и другие темы, которые практически не встречаются на школьных олимпиадах.
На сайте международной олимпиады по информатике IOI опубликован текст «IOI Syllabus» — это тематическая программа IOI, где написано, что может быть на олимпиаде, а чего не может быть. На Всеросе не будут давать задачи на темы, которых нет на Межнаре, потому что Всерос — это отборочный этап перед IOI.
Участие в разных олимпиадах
Самой основной олимпиадой, которая дает возможность поступления без экзаменов в любой российский вуз по специальности — это индивидуальная Всероссийская олимпиада школьников по информатике. Есть еще командная — Всероссийская командная олимпиада школьников, но она не имеет статуса для поступления.
Как и у Всероса, первый уровень олимпиады имеет также Открытая олимпиада школьников по программированию, она проводится Московским физико-техническим институтом, Московским государственным университетом им. М. В. Ломоносова, Центром педагогического мастерства и Московским центром непрерывного математического образования. У нее есть отборочный онлайн-этап, а в марте 600 победителей приглашают в 1С для оффлайн-соревнования.
В марте проходит очный тур Индивидуальной олимпиады школьников по информатике и программированию (ИОИП) Университета ИТМО. Она тоже первого уровня. СПбГУ тоже проводит свою олимпиаду.
Первого уровня есть олимпиада «Технокубок», организованная Mail.ru Group, МФТИ, МГТУ им. Баумана и Codeforces. Третий уровень представляет Открытая олимпиада школьников по программированию «Когнитивные технологии», которую проводит «МИСиС» и МФТИ совместно с компанией Cognitive Technologies. Отбор проходит в декабре, а олимпиада в январе. Третий уровень, если он включен в список, дает определенные баллы по информатике в определенные университеты.
Как выстроить стратегию
На Всеросе дается по пять часов на решение четырех задач на каждый из двух дней участия. На Межнаре — два дня по три задачи.
Школьные олимпиады идут с зачетом частичных решений. Всегда есть задачи, которые решить относительно просто, на них можно набрать много баллов малыми усилиями, в то время как другие задачи решить полностью значительно сложнее; но получить баллы можно даже за их частичное решение. Нужно выделить время, чтобы по каждой из задач написать даже простое решение, которое получит хотя бы 10 или 15 баллов из 100. Всегда уделяйте время стратегии получения частичных баллов.
Нельзя постоянно долбить одну и ту же задачу, если она не получается, надо переключаться
Потому что иначе все может закончиться частичным баллом по одной задаче и полным провалом по другим. Обычно первые две задачи в каждом туре — самые простые. Исходя из этого, надо попытаться простые решить, по сложным — набрать хотя бы базовые баллы за простое решение.
В целом, возможны различные методы подготовки к олимпиадам. Наиболее оптимальный вариант — сочетать все способы, это значительно ускорит прогресс. Читать книги, решать задачи на сайтах, посещать факультативы и участвовать в образовательных лагерях. Самое главное — много решать.
Вы находитесь в разделе «Блоги». Мнение автора может не совпадать с позицией редакции.
