Следите за ходом лагеря в наших группе ВК и телеграм канале.

Вступительная работа

Чтобы попасть в лагерь, нужно выполнить вступительную работу. Те, кто хорошо сдал зачёт в прошлом году, участвовал в олимпиадах или уже поступил в ЛКШ в этом году, могут не решать вступительную, но всё равно должны заполнить анкеты. Вступительная работа в параллели D..A началась 25-го мая и продлилась до 23:55 московского времени 9-го июня.

Учебные параллели

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

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

Выбор параллели

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

Не имеет смысла поступать в параллель выше вашего текущего уровня. От знания сложных алгоритмов мало толку без уверенного владения стандартными. Тем более бессмысленно нечестно заполнять тематическую анкету или несамостоятельно выполнять вступительную работу: последнее наверняка выявится проверкой на списывание, и вы вообще не поедете в ЛКЛ. Если вы всё же окажетесь в слишком сложной для вас параллели, преподаватели заметят это в первые дни лагеря и переведут вас в более подходящую. Верно и обратное: если вы окажетесь в слишком простой параллели, вас могут перевести выше. Но и то и другое чревато потерей времени в первые дни смены, поэтому отнеситесь к выполнению вступительной работы и заполнению тематической анкеты серьёзно.

Формат вступительной

Поступающим в параллели C2...A нужно решить практические задачи по программированию. Их принимает автоматическая тестирующая система. Зарегистрируйтесь в ней. Если вы решали вступительную в прошлом году, можете использовать старый логин. В тестирующей системе вы найдёте условия задач, и туда же будете сдавать решения — программы на одном из допустимых языков программирования. Поддерживаются: C, C++, Python 2, Python 3, Free Pascal, Delphi, Java, Go и FreeBASIC. Учитываются только правильные решения, то есть проходящие все тесты. У параллели D особый формат вступительной, смотрите их описание ниже.

Обратите внимание, в этом году мы поменяли формат тематической анкеты. Сначала вам необходимо заполнить анкету поступающего, выбрав в ней желаемые параллели. Далее вам будет доступна тематическая анкета, сформированная специально под выбранные вами параллели. Если вы захотите убрать желаемую параллель для поступления, то это никак не повлияет на заполеннные ранее ответы тематической, но если вы добавите новую параллель, то вам будет необходимо дозаполнить тематическую анкету! Отнеситесь к заполнению тематической анкеты ответственно, потому что она влияет на то, в какую параллель вы будете зачислены!

Решение вступительной

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

Зачисление

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

Поддержка

Узнать о том, как работать в тестирующей системе, и посмотреть примеры оформления программ вы можете в справке и FAQ. Прочитайте памятку участника краевой олимпиады. В ней разобраны частые ошибки решающих. Любые вопросы про вступительную работу и тестирующую систему задавайте по почте mail@sicamp.ru или в группе ВК.

Учебные параллели

D

6...7 классы

Основы программирования

Для школьников, не имеющих опыта в программировании, но желающих изучить основы. Параллель рассчитана на выпускников 6-7 классов, умеющих проводить базовые математические рассуждения и знакомых с понятием “алгоритма”.

Вы изучите

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

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

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

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

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

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

C2

6...8 классы

Алгоритмы для начинающих

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

Вы изучите

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

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

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

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

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

C1

7...9 классы

Базовые алгоритмы

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

Вы изучите

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

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

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

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

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

C0

7...9 классы

Младшая практическая параллель

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

Вы изучите

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

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

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

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

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

B2

7...10 классы

Практическое применение алгоритмов в олимпиадных задачах

Немного усложненная версия параллели B’ прошлых лет. Темы во многом пересекаются с темами B1 за исключением каких-то сложных и углубленных частей. Мы решили сблизить параллели B2 и B1 по уровню, чтобы уменьшить разрыв в знаниях между этими параллелями и облегчить последующее обучение в B1 за счет знакомства, хотя бы базового, со многими темами B1.

Вы изучите

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

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

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

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

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

B1

8...10 классы

Алгоритмы и структуры данных

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

Вы изучите

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

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

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

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

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

B0

9...10 классы

Старшая практическая параллель

Прямой аналог A’ прошлого года, переименованный для единообразия. Главной целью данной параллели является закрепление большого количества пройденных тем на практических задачах подобранных из разных олимпиад прошлых лет.

Вы изучите

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

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

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

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

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

A

9...10 классы

Продвинутые алгоритмы и решение олимпиадных задач высокого уровня

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

Вы изучите

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

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

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

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

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

Бонусы

Участникам олимпиад

Поступившим в ЛКШ

Если вы поступили в ЛКШ, но по каким-то причинам не можете туда поехать, мы готовы зачислить вас параллель соответствующего уровня. Если вы хотите поехать в ЛКЛ после ЛКШ, вступительную вам решать тоже не нужно (параллель мы выберем одной из следующих по уровню, и возможно изменим её по результатам зачёта в ЛКШ), но вашего зачисления мы не гарантируем — нам хочется, чтобы как можно больше ребят имели возможность поучиться.

Освобождённые от вступительной по результатам зачёта ЛКЛ в прошлом году:

  • Владимир Загоровский
  • Ольга Поспелова
  • Данил Кильметов
  • Константин Глазман
  • Святослав Михеев
  • Дмитрий Килин
  • София Гакашева
  • Леонид Колинько
  • Алина Халикшина
  • Ульяна Халикшина
  • Дмитрий Завадский
  • Федор Марьин
  • Алексей Няшин
  • Алексей Сауткин
  • Дмитрий Белоцерковцев
  • Варвара Доронина
  • Вячеслав Казаков
  • Софья Тепляшина
  • Тимофей Бурдин
  • Анна Постникова