Отбор по программированию в Яндекс Кружок

Длинный тур: 16 августа 16:00 - 30 августа 23:59
Короткий тур: 6 сентября с 10:00 до 15:00 по МСК

Вопросы по условиям задач и их проверке участники задают через тестирующую систему при помощи отправки сообщения. Обратите внимание, что исходные коды решений не будут доступны в тестирующей системе.

Канал в Telegram

Отбор на обучение

Отбор проходит в два этапа.

Первый этап

Первый этап пройдет с 16 по 30 августа и будет проходить в стандартном формате. Участникам будут предложены задачи, распределенные по блокам — по 6 задач в каждом блоке. По всем задачам длинного тура суммарно вы можете сделать не более 500 посылок.

Блоки задач

Задачи делятся на 6 блоков:

C
C-B'
B'-B
B-A'
A'-A
A

Вам не нужно решать все задачи. Вы выбираете подходящую параллель:

Параллель C
·
C
+
C-B'
Параллель B'
·
C-B'
+
B'-B
Параллель B
·
B'-B
+
B-A'
Параллель A'
·
B-A'
+
A'-A
Параллель A
·
A'-A
+
A
Результаты по блокам:
C B' B A' A

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

  • прошли отбор на самостоятельное онлайн-обучение;
  • получили право участвовать во втором этапе отбора и претендовать на очное обучение.

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

Второй этап

Второй этап предварительно пройдет 6 сентября с 10:00 до 15:00 по московскому времени. Для каждой параллели будет подготовлен отдельный контест. Участник получит доступ к контесту своей параллели, определенной по результатам первого этапа, а также к контесту на одну параллель младше.

Количество и сложность задач могут различаться между параллелями. Некоторые параллели также могут проводить дополнительные испытания в рамках второго этапа.

Итоговое решение о зачислении на очное обучение принимается по результатам второго этапа.

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

Прокторинг

Информация о прокторинге будет добавлена позже, за несколько дней до начала короткого тура.

Самостоятельность выполнения

Все задания отбора должны выполняться участником самостоятельно.

Строго запрещено

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

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

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

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

Отправляя работу, участник подтверждает, что ознакомился с правилами отбора и обязуется их соблюдать.

Возрастные ограничения параллелей

  • В параллель [C] могут быть зачислены только ученики не старше 10 класса.
  • В параллель [A] могут быть зачислены только ученики 10 класса или старше, ученики 9 класса и младше могут быть зачислены в исключительных случаях на усмотрение преподавателей.

Описание параллелей

Требования, темы и преподаватели для каждой параллели отбора по программированию.

Параллель A
ДЛЯ КОГО
  • Уверенное знание C++
  • Хорошие знания структур данных: дерево отрезков, декартово дерево, дерево фенвика
  • Динамическое программирование: НВП, НОП, динамика на дереве, динамика по подмножествам, простые оптимизации
  • Структуры данных на деревьях: HLD, центроиды, переливание меньшего к большему
  • Графы: DFS, BFS, алгоритм Дейкстры, алгоритмы Прима и Крускала, поиск мостов и точек сочленения, поиск компонент сильной связности, алгоритм Куна
  • Строки: префикс функция, N-функция, бор
  • Теория чисел: деление по модулю, алгоритм Евклида, решето Эратосфена
  • Геометрия: представление вектора, основные векторные операции, поиск пересечения прямых, выпуклая оболочка
ПРИМЕРЫ ТЕМ
  • Нетривиальные алгоритмы и задачи теории чисел
  • Декомпозиции деревьев: centroid, heavy-light, ladder
  • Задачи на графах: 2-SAT, паросочетания, остовы и их применение в задачах
  • Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, разные структуры и алгоритмы для нахождения минимумов
  • Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат
  • Алгоритмы поиска потоков в сетях
  • Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне
  • Splay-деревья, link-cut
  • Алгоритмы поиска минимальных глобальных разрезов
  • Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов
  • Матроиды
  • Алгоритмы во внешней памяти
ФОРМАТ ЗАНЯТИЙ
В начале каждого занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На семинарах учащиеся сдают задачи с листочка преподавателям. Параллельно, с некоторой задержкой, достаточной, чтобы успеть подумать над соответствующими задачами, проводится их разбор.
ПРЕПОДАВАТЕЛИ
Филипп Грибов, Александр Некрасов, Алексей Михненко, Антон Степанов
Параллель A'
ДЛЯ КОГО
  • Уверенное знание C++, алгоритмы и структуры данных STL
  • Знание структур данных: дерево отрезков, система непересекающихся множеств, разреженные таблицы
  • Динамическое программирование: задачи рюкзака, НВП, НОП. Динамика по подотрезкам, поддеревьям и подмножествам
  • Базовые алгоритмы поиска кратчайших путей на графах
  • Базовые геометрические примитивы: вектора, точки, прямые и окружности. Базовые операции с примитивами
  • Базовые строковые алгоритмы (хэширование, префикс и N функции)
ПРИМЕРЫ ТЕМ
  • Структуры данных: от дерева отрезков до splay-дерева
  • Оптимизации динамического программирования: convex hull trick, meet-in-the-middle, divide and conquer
  • Декомпозиции деревьев: centroid, heavy-light, ladder
  • Задачи на графах: паросочетания, потоки, dynamic connectivity problem
  • Геометрия: выпуклые оболочки, сумма Минковского
  • Строки: хэши, Ахо-Корасик, суффиксный массив
  • Полезные трюки: STL, битовые оптимизации, стресс-тестирование
ПРЕПОДАВАТЕЛИ
Иван Сафонов, Алексей Васильев, Евгений Пахомов, Андрей Павлов, Тимофей Ижицкий
Параллель B
ДЛЯ КОГО
  • Сортировки
  • Базовые знания C++, алгоритмы и структуры данных STL
  • Линейные алгоритмы (например, поиск ближайшего меньшего при помощи стека или минимум в окне)
  • Способы хранения графов и базовые применения DFS (например, нахождение компонент связности, поиск цикла в графе, проверка графа на двудольность)
  • Базовое понимание и умение решать простые задачи на динамическое программирование
ПРИМЕРЫ ТЕМ
  • Графы: BFS, DFS, их применения. Алгоритмы поиска кратчайших путей во взвешенных графах (Форда-Беллмана, Дейкстры, Флойда). Минимальные остовные деревья. Паросочетания, алгоритм Куна.
  • Деревья: алгоритм поиска наименьшего общего предка в дереве. Эйлеров обход. Декомпозиции дерева (heavy-light, centroid).
  • Строки: префикс-, N- функции, бор, автомат Ахо-Корасик, хеширование. Суффиксный массив.
  • Динамическое программирование: одномерное, многомерное, по подмаскам, подграфам, подотрезкам, подмножествам, профилю и изломанному профилю.
  • Структуры данных: дерево отрезков с массовыми операциями, декартово дерево, sparse table, система непересекающихся множеств. Дерево Фенвика.
  • Геометрия: базовые примитивы, алгоритмы построения выпуклой оболочки, быстрые алгоритмы в вычислительной геометрии.
  • И много других тем: теория Шпрага-Гранди, корневая оптимизация, метод разделяй-и-властвуй, решето Эратосфена, задача дискретного логарифмирования, meet-in-the-middle.
ПРЕПОДАВАТЕЛИ
Михаил Первеев, Денис Видяев, Герман Перов, Никита Голиков
Параллель B'
ДЛЯ КОГО
  • Знание языка программирования (C++)
  • Умение использовать встроенные алгоритмы (сортировки, поиски)
  • Умение решить задачу на динамическое программирование уровня «Кузнечик»
ПРИМЕРЫ ТЕМ
  • Важные структуры данных: дерево отрезков, разреженные таблицы, СНМ
  • Динамическое программирование: до динамики по подстрокам, подмножествам и цифрам
  • Алгоритмы на графах: до поиска мостов, точек сочленения, построения минимального остова
  • Простейшие алгоритмы на деревьях: LCA, LA, Эйлеров обход
  • Базовые алгоритмы на строках: префикс-функция, зет-функция, хэши и бор
  • Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки
ПРЕПОДАВАТЕЛИ
Мария Жогова, Михаил Кондрашин, Александр Понкратов, Константин Амеличев
Параллель C
ДЛЯ КОГО
  • Знание синтаксиса какого-либо языка программирования
  • Готовность быстро изучать C++, если вы ещё им не владеете
  • Знание математики на уровне 6–7 класса (степень, извлечение корня, понятие функции, желательно базовая планиметрия, понятие о тригонометрических функциях)
  • Опыт в математических олимпиадах будет плюсом
ПРИМЕРЫ ТЕМ
  • Сортировки: квадратичные, MergeSort, QuickSort
  • Бинарный поиск: обычный и по ответу
  • Теория чисел: алгоритм Евклида, разбиение числа на простые
  • Простейшие структуры данных: vector, set, map, стек, очередь, дек
  • Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП, подсчёт комбинаторных объектов
  • Базовые алгоритмы на графы: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда-Беллмана, конденсация графа
  • Простая геометрия: векторы, прямые, окружности
ПРЕПОДАВАТЕЛИ
Полина Романченко, Алексей Кулдошин, Алиса Нестеренко, Лиза Жукова

Рекомендации

Предположим, вы решили, что вам подходит параллель [B]. Чтобы попасть в неё, решите как можно больше задач, помеченных [B'-B] и [B-A']. Также советуем посмотреть и решить задачи, соответствующие параллели на пол ступени ниже от желаемой. Например, для рассматриваемого выше случая, это задачи, помеченные как [C-B']. Если вы верно определили желаемую параллель, то эти задачи должны вам показаться простыми. Вы их быстро решите и таким образом обезопасите себя: если не попадёте в [B], то в [B'] попадёте наверняка!

Правила поведения

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

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

Решение о «похожести» решений принимается нами. Участник отбора будет дисквалифицирован, даже если его решение было без его ведома получено и сдано другим участником.

Расшифровка вердиктов тестирующей системы

Ошибка компиляции
Исполняемый файл не был создан при компиляции. В этом случае запуск решения на тестах не производится. Возможные причины: синтаксическая ошибка в программе; неверно указан язык программирования.
Нарушение правил безопасности
Программа нарушает правила олимпиады. Возможные причины: нарушение правил олимпиады; ошибка в программе; вызов system("pause") в программах на C/C++.
Превышено максимальное время работы
Программа превысила лимит времени работы. Возможные причины: неэффективное решение; ошибка в программе (программа зацикливается); ошибка в считывании данных; программа ожидает от пользователя нажатия на клавишу после вывода ответа.
Превышен лимит по памяти
Программа превысила лимит используемой памяти. Возможные причины: неэффективное решение; ошибка в программе; бесконечная (или очень большая) рекурсия; ошибки при работе с указателями в C/C++ также могут диагностироваться, как «Превышен лимит по памяти».
Ошибка выполнения
Программа совершила некорректное действие в ходе исполнения. Возможные причины: некорректное арифметическое действие (деление на ноль, извлечение корня из отрицательного числа, переполнение переменной); ошибка при работе с памятью и структурами данных; нарушение правил олимпиады (работа с файлами, вызов сторонних программ); бесконечная (или очень большая) рекурсия; синтаксические и иные ошибки в программах на Python и других интерпретируемых языках; в программе явно указан ненулевой код возврата.
Неправильный формат вывода
Вывод программы не соответствует условию задачи. Возможные причины: программа выводит ответ в формате, не соответствующем условию задачи; программа не вывела ничего; программа выводит результат в файл, а не на стандартный вывод; ошибка в программе (например, программа вывела ответ дважды); в программе есть отладочный вывод; программа выводит лишние сообщения типа «Введите число» или «Ответ»; программа должна вывести числа в одной строке через пробел, а вывела их в разных строках или наоборот; программа должна вывести целое число, а выводит действительное.
Неправильный ответ
Программа вывела неправильный ответ. Возможные причины: неверный алгоритм решения; ошибка в программе.
OK
Программа выдала правильный ответ на этом тесте.
Пропущен
Запуск программы на данном тесте не производился. Возможные причины: предыдущий тест данной подзадачи не пройден.
Ошибка проверяющей системы
Тестирующая система не смогла выполнить проверку решения. Возможные причины: не волнуйтесь, это будет скоро исправлено.

Примеры решения задачи A+B

C++
#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b;
}
Java
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(a + b);
    }
}
Python
a = int(input())
b = int(input())
print(a + b)
Pascal
var
    a, b: integer;
begin
    readln(a, b);
    writeln(a + b);
end.