Параллель B

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

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

Программа:

1.      Применение сортировок: скользящее окно, два указателя, сканирующая прямая, сжатие координат.

2.      Бинарный поиск и его применения.

3.      Применение структур данных STL к решению задач: set, multiset, map, priority_queue, rope.

4.      Хеширование строк и других объектов, хеш-таблицы.

5.      Динамическое программирование на подотрезках, на поддеревьях, на подмножествах, по профилю.

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

7.      Кратчайшие пути в графах (алгоритмы Дейкстры, Флойда, Форда-Беллмана), минимальные остовные деревья (алгоритм Прима) и система непересекающихся множеств (алгоритм Краскала).

8.      Одномерные деревья отрезков и их применения (задачи RMQ, RSQ, групповые операции, дерево отображений).

9.      Задачи LCA (наименьший общий предок) и LA (k-й предок). Разреженные таблицы.

10.    Вычислительная геометрия на плоскости.

11.     Быстрые алгоритмы вычислительной геометрии. Применение структур данных в вычислительной геометрии.

Обратите внимание:

Рабочим языком параллели B является C++. Вступительное задание можно решать и на другом языке программирования, однако к моменту начала школы нужно освоить C++ в рамках онлайн-курса “Введение в программирование (C++)” от Яндекса и НИУ ВШЭ.

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

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

Поступление.

Для того чтобы подать заявку на параллель B, необходимо
1) заполнить регистрационную анкету (по кнопке "Регистрация" на главной странице открывается эта же анкета),
2) выполнить тестовое задание на параллель B.
Все вопросы, связанные непосредственно с задачами тестовых заданий, следует задавать, используя вкладку «сообщения» внутри системы Яндекс.Контест.