Найти тему
803 подписчика

Продолжается регистрация на дополнительный отбор в группы кружка олимпиадного программирования при ЮМШ.

8 января на почту, указанную при регистрации, будет выслана ссылка на практическое задание (контест на платформе CF). Чтобы кандидам было проще разобраться, в какую группу пробовать поступить, методисты кружка сформулировали требования к знаниям и навыкам, необходимым для успешного обучения у нас.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Для групп "Орлята" @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Теоретическое знание и навыки практической работы по темам:
1) Типы данных
2) Циклы
3) Списки
4) Сортировки
5) Работа с остатками (математика)

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Для группы "Аксолотли" @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Технические навыки для группы "Орлята" + владение следующими знаниями (теория и практика):
1) Алгоритмы сортировок
2) Работа с двумерными списками
3) Базовые алгоритмы теории чисел: проверка числа на простоту, нахождение наибольшего общего делителя чисел
4) Рекурсия
5) Работа со множествами и словарями

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Для группы "Котята" @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Всё вышеперечисленное + умение самостоятельно и грамотно использовать знания по следующим темам:
1) C++. STL: <algorithm>, контейнеры (std::vector, std::deque, std::set, std::map, std::unordered_set, std::unordered_map), адаптеры контейнеров (стеки и очереди), std::pair.
2) Работа со строками, простые парсеры.
3) Графы. Способы хранения, простые алгоритмы: dfs, bfs, алгоритм Дейкстры.
4) Ориентированные графы. Топологическая сортировка, компоненты сильной связности.
5) Динамическое программирование-1 (в том числе многомерное). Классические задачи (задача о рюкзаке, наибольшая общая подпоследовательность, расстояние Левенштейна). Восстановление ответа.
6) Битовые маски. Перебор всех двоичных последовательностей заданной длины.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Для группы "Бурундучки" @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Всё вышеперечисленное + владение теорией большей части программы + умение самостоятельно и грамотно реализовывать хотя бы некоторые алгоритмы из КАЖДОЙ темы ниже:
1. Графы: взвешенные графы, DFS, BFS, алгоритмы Флойда, Форда-Белмана, Дейкстры, Прима и их приложения.
2. Динамическое программирование-2: дискретная задача о рюкзаке (и задача о двух кучках монет), наибольшая возрастающая подпоследовательность, задача про бросание телефонов; мемоизация, замена параметра.
3.Теория чисел-1: алгоритм Евклида, алгоритмы за корень (проверка на простоту, разложение на множители, функция Эйлера), решето Эратосфена.
4. Теория чисел-2: вычисления по модулю (арифметика, обратный элемент, первообразный корень, тест Миллера-Рабина, дискретный логарифм).
5. Комбинаторика-1: рекурсивная генерация объектов, следующий и предыдущий объект (подмножества, перестановки, сочетания, скобочные последовательности, разбиения на слагаемые).
6. Комбинаторика-2: количество объектов, объект по номеру и номер по объекту (подмножества, перестановки, сочетания, разбиения на слагаемые, числа Стирлинга).
7. Строки: полиномиальное хеширование (и алгоритм Рабина-Карпа), хеши подстрок, префикс-функция (и алгоритм Кнута-Морриса-Пратта), z-функция (и алгоритм Гасфилда), палиндромы (и алгоритм Манакера).
8. Система непересекающихся множеств (и присоединение меньшего к большему).

Регистрация доступна по ссылке: https://forms.gle/oJ6Q5GAAs37AzjW48
2 минуты