Вы изучите

• Основные принципы написания программ и работы в среде разработки;
• Базовыe конструкции одного из языков программирования: ввод/вывод данных из программы, условия, циклы, массивы, функции, рекурсия, встроенные сортировки;
• Алгоритмы квадратичных сортировок;
• Бинарный поиск элемента в отсортированном массиве и бинарный поиск по ответу;
• Базовые структуры данных: стек, очередь и дек;
• Алгоритмы теории чисел: aлгоритм Евклида, разложение числа на простые множества, решето Эратосфена;
• Подход динамического программирования для решения задач.
• А также познакомитесь с форматом олимпиад по программированию, узнаете об основных олимпиадах по программированию и льготах, которые они могут давать при успешном участии в них.
• И кроме этого повторите и изучите математические основы, необходимые для успешного участия в олимпиадах, такие как теория чисел, основы теории графов.

Мы ожидаем, что вы

• Умеете проводить простейшие математические рассуждения;
• Знакомы с понятием алгоритма;
• Возможно, имеете опыт работы с исполнителем “Черепашка” или аналогами;
• Не обязательно умеете программировать.

Вступительная для параллели D

Вступительная работа для параллели D состоит из теоретических задач и не требует умения программировать. Скачайте задачи вступительной. Нужно не только найти ответ к задаче, но и объяснить, почему он получается таким. Не страшно, если у вас получаются не все задачи. Оформите то, что получилось: возможно, этого хватит. Если какую-то задачу вы решили не до конца, всё равно оформите её. Это принесёт дополнительные баллы.

Оформите работу в Microsoft Word, Open Office или просто текстовым файлом. Можете оформить решение на бумаге, тогда отсканируйте или сфотографируйте его. Оформленную работу необходимо собрать в один файл (word, pdf, архив) и загрузить в анкету поступающего в параллель D. Вы можете загружать файл несколько раз, будет рассмотрена лишь последняя версия.

Кроме того, всем поступающим в параллель D также необходимо заполнить анкеты поступающего и тематическую. Они доступны на сайте. Для входа вам придется зарегистрироваться в тестирующей системе GATE, но решать задачи в ней не нужно.

Вы изучите

• Язык программирования C++ и его встроенную библиотеку STL. Для всех задач олимпиадного программирования гарантируется существование решения на C++, что делает данный язык основным в олимпиадном программировании;
• Простейшие графовые алгоритмы, такие как DFS и BFS;
• Cпособы решения задач динамического программирования: различные модификации задачек про кузнечика, количество последовательностей из 0 и 1 без двух нулей подряд;
• Бинарный поиск и бинарный поиск по ответу;
• Широко используемые методы: два указателя и сканирующую прямую;
• Простые структуры данных: стеки, очереди, деки. Научитесь реализации очереди на двух стеках, стека с поддержкой минимумa;
• Основные понятия теории чисел: сравнения по модулю, теоремы о простых числах и делении с остатком;
• А также алгоритмы теории чисел, такие как алгоритм Евклида, решето Эратосфена, быстрое возведение в степень.

Мы ожидаем, что вы

• Владеете основами языка любого программирования: вводом-выводом, базовыми операторами и типами данных, так как в данной параллели изучению языков программирования посвящено гораздо меньше времени;
• Имеете небольшой опыт решения задач, можете самостоятельно довести простейшие программы до рабочего состояния;
• Умеете проводить легкие математичские рассуждения. Углубленной математической подготовки не требуется, всем нужным определениям и теоремам мы вас научим, но если вы что-то уже знаете, то это будет плюсом.

Вступительные задачи

• Самое большое просто число
• Базовая математика
• Последовательность
• Клоун Глеб
• Случай в поликлинике

Вы изучите

• Классические задачи динамического программирования, такие как наибольшая общая подпоследовательность двух строк, наибольшая возрастающая подпоследовательность числового массива за квадрат и за O(n log n), рюкзак;
• Различные подходы к решению задач динамического программирования: динамика вперед, динамика назад, ленивая динамика;
• Хэширование для решения задач на строки: поиск подстроки в строке, наибольшая подстрока палиндром;
• Базовые графовые алгоритмы, такие как DFS, BFS и алгоритмы поиска кратчайших путей в графе;
• Топологическую сортировку графа и ее применение;
• Бинарный поиск и бинарный поиск по ответу;
• Применение рекурсии для перечисления комбинаторных объектов и переборных решений задач;
• Методы двух указателей и сканирующей прямой;
• А также повторите алгоритмы теории чисел на примере более сложных задач.

Мы ожидаем, что вы

• Уверенно владеете основами языка программирования;
• Имеете опыт участия в олимпиадах по программированию или прорешивания архивов задач;
• Знаете фундаментальные начала теории чисел и теории графов.

Вступительные задачи

• Последовательность
• Клоун Глеб
• Случай в поликлинике
• Одиннадцать
• Чей город лучше?

Вы изучите

• Большое количество задач на динамическое программирование. Данная тема встречается во многих олимпиадах на самых разных уровнях, и самый лучший способ научиться решать такие задачи — практика;
• Базовые и усложненные задачи на хэширование строк. Эта тема традиционно сложно дается в более младших параллелях, поэтому мы считаем, что важно выделить еще немного времени на закрепление этой темы;
• Комбинирование алгоритмов из различных тем, пройденных в прошлых параллелях. Например, задачи на бинарный поиск по ответу с проверкой DFS'ом или Дейкстрой;
• Задачи на два указателя, сканирующую прямую, скользящее окно. Эти темы хоть и проходятся в предыдущих параллелях, но на них выделяется немного времени на теории и практике;
• Большое количество графовых задач. В прошлых параллелях много времени уделяется базовым аспектам теории графов, что не позволяло давать более сложные задачи на эту тему;
• Переборные задачи, а также выработаете умениe решать задачи на частичный балл.

Мы ожидаем, что вы

• Уверенно владеете основами языка программирования;
• Имеете опыт решения задач;
• Имеете хорошее теоретическое знание большинства тем, пройденных в предыдущих параллелях. Однако, если вы не знаете пару тем, то не переживайте, мы обязательно найдем время, чтобы вам их рассказать.

Вступительные задачи

• Клоун Глеб
• Случай в поликлинике
• Одиннадцать
• Чей город лучше?
• Диверсия спецсвязи. Легкая версия
• Гитарник

Вы изучите

• Алгоритмы поиска кратчайших путей в графах: Дейкстра, Форд-Беллман, Флойд.
• Алгоримты поиска минимальные остовных деревьев: лемма о разрезе, Прим, Краскал
• Продолжение графовых алгоритмов: топологическую сортировку, время входа/выхода в вершину, поиск мостов и точек сочленения, компонент сильной связности;
• Строковые алгоритмы и структуры: повторение хэширования, префикс-функция, Z-функция, бор;
• Динамическое программирование, типичные состояния динамики: динамика по поддеревьям, динамика по подмножества, динамика по подотрезкам, динамика на ациклическом графе;
• Классические алгоритмы динамического программирования: рюкзак и его вариации;
• Начало сложных структур данных: дерево отрезков с модификацией в точке или на отрезке, cистема непересекающихся множеств;
• Математические темы, такие как комбинаторика, малая теорема Ферма, нахождение обратного по модулю, расширенный алгоритм Евклида.
• Базовую геометрию: понятие вектора, скалярного произведения, векторного произведения, классические задачи геометрии, а также паттерны для удобного решения задач на геометрию;
• Начала геометрии многоугольников: площадь многоугольника, принадлежность точки выпуклому и произвольному многоугольникам, выпуклая оболочка.

Мы ожидаем, что вы

• Уверенно владеете основами языка программирования, а также можете самостоятельно написать код нового для себя алгоритма;
• Хорошо знаете базовыe тем теории графов и теории чисел, а также знание базовых подходов к решению задач динамического программирования;
• Имеете опыт решения задач и участия в олимпиадах по программированию.

Вступительные задачи

• Одиннадцать
• Чей город лучше?
• Диверсия спецсвязи. Легкая версия
• Гитарник
• НЛО над Хуснешем
• Рождаемость

Вы изучите

• Cтруктуры данных на основе деревьев.
• Алгоритмы на строках и графах.
• Продвинутые методы динамического программирования.
• Задачи вычислительной геометрии.
• Динамическое программирование, типичные состояния динамики: динамика по поддеревьям, динамика по подмножества, динамика по подотрезкам, динамика на ациклическом графе, динамика по цифрам, динамика по профилю;
• Оптимизации ДП: применения структур данных для пересчета состояний, подсчет динамики с помощью возведения матрицы в степень;
• Продолжение кратчайших путей в графах: Дейкстра, Форд-Беллман, Флойд. Поиск отрицательного цикла в графе;
• Продолжение графовых алгоритмов: топологическая сортировка, время входа/выхода в вершину, поиск компонент реберной и вершинной связности;
• Алгоритмы на деревьях: LCA с двоичными подъемами, LCA с RMQ, применения для подсчета функций на путях в дереве;
• Эйлеров обход графа, применение в решении задач на деревья;
• Структуры данных: дерево отрезков сверху/снизу, массовые операции в дереве отрезков, хранение дополнительной информации в вершинах дерева отрезков, MergeSortTree, Sparse Table, СНМ, хранение дополнительной информации в СНМ, дерево Фенвика, sqrt-декомпозиция;
• Строковые алгоритмы и структуры: подходы к преодолению антихэш тестов, префикс-функция, Z-функция, бор, цифровой бор;
• Алгоритмы теории чисел: нахождение обратного по модулю, решение диофантовых уравнений, применение решета Эратосфена для вычисления мультипликативных функций;
• Геометрические задачи. Биссектрисы, перпендикуляры, параллели, серединные перпендикуляры, применения уравнения прямой, пересечения различных геометрических объектов;
• Геометрия многоугольников и окружностей: площадь многоугольника, принадлежность точки выпуклому и произвольному многоугольникам, выпуклая оболочка, касательные к многоугольнику/окружности, два указателя для решения задач на многоугольники.

Мы ожидаем, что вы

• Уверенно владеете основами языка программирования, а также можете самостоятельно написать код нового для себя алгоритма. Кроме того можете самостоятельно найти ошибку в коде или тест, на котором не работает решение;
• Знаете основные алгоритмы на графах и основные структуры данных (стек, очередь, список, куча);
• Уверенно владеете техниками перебора, динамического программирования и знаете предыдущие темы теории чисел;
• Имеете опыт решения задач с применением алгоритмов. Опыт участия в олимпиадах регионального уровня будет плюсом.

Вступительные задачи

• Диверсия спецсвязи. Легкая версия
• Гитарник
• НЛО над Хуснешем
• Рождаемость
• Vector. ЛКЛ Edition
• Родословная

Вы изучите

• Большое количество задач на динамическое программирование, в том числе задачи на комбинирование структур данных с подсчетом динамики;
• Применение структур данных. Комбинирование ДО со сканлайном, спуск по дереву отрезков, двумерное ДО, хранение дополнительной информации в дереве отрезков;
• Дерево Фенвика. Прибавление на отрезке, значение в точке. Спуск по дереву Фенвика, двумерное дерево Фенвика.
• Корневую декомпозицию и алгоритм Мо. Решение задачи о динамической связанности оффлайн;
• Корневые оптимизации. Подсчет количества треугольников в графе;
• Задачи на деревьях. Применение LCA и обходов, cуммы на путях, сумма на поддереве с прибавлением числа в вершине;
• Систему непересекающихся множеств. Задачи на переливание (добавления меньшего множества к большему);
• Хэширование. Поиск коллизии по заданному модулю, уменьшение количества коллизий, парадокс дней рождения;
• Рандомизированные алгоритмы в геометрии и графах. Рандомизированный поиск мостов и 2-разрезов в графе. Метод Монте-Карло;
• Алгоритм разделяй и властвуй. Поиск пары ближайших точек на плоскости и другие задачи;
• Задачи вычислительной геометрии;
• Строковые алгоритмы и структуры: бор, цифровой бор, префикс- и Z-функции;
• Избранные задачи на темы прошлых параллелей;
• Прорешаете задачи с олимпиад прошлых лет, таких как региональный этап ВсОШ, заключительный этап ВсОШ, открытая олимпиада по программированию, ВКОШП;
• Выработаете умение решать сложные задачи на частичный балл, попрактикуетесь в написании стресс-тестов;
• А также порешаете контесты на время в условиях приближенным к реальным олимпиадам.

Мы ожидаем, что вы

• Знаете теорию по всем темам предыдущих параллелей.
• Уверенно умеете писать на выбранном языке программирования, самостоятельно реализовать рассказанный алгоритм/подход.
• Участвовали в региональных и заключительных этапах олимпиад.

Вступительные задачи

• Гитарник
• Vector. ЛКЛ Edition
• Родословная
• Диверсия спецсвязи. Сложная версия
• Красивые комнаты
• Ремонт дороги
• НВП на случайном дереве

Вы изучите

• Heavy-light и центроидную декомпозции;
• Суффиксные структуры и алгоритмы их построения;
• Алгоритмы поиска потока в графе: Форд-Беллман, Диница;
• Редко используемые структуры данных, например, декартово дерево;
• Персистентные структуры данных;
• Сложные оптимизации динамического программирования: CHT, разделяй и властвуй, MITM;
• Алгоритм быстрого преобразования Фурье;
• Применение разных структур данных и их комбинирование для решения задач.
• Порешаете контесты на время в условиях приближенным к реальным олимпиадам.

Мы ожидаем, что вы

• Имеете значительный опыт решения задач и участия в олимпиадах;
• Уверенно владеете алгоритмами параллели B0, в том числе структурами данных;
• Могли ранее обучаться в параллели A в ЛКЛ или ЛКШ — мы подстроим программу под ваши знания, возможно организуем несколько групп.

Вступительные задачи

• Родословная
• Диверсия спецсвязи. Сложная версия
• Красивые комнаты
• Ремонт дороги
• НВП на случайном дереве
• После дождичка, в четверг...