Результаты и условия задач
| 4 ноября – командный легкий тур |  Результаты | Условия: PS |
| 4 ноября – командный сложный | Результаты | Условия: PS |
| 5 ноября – личный легкий тур | Результаты | Условия:  DOC |
| 5 ноября – личный сложный тур | Результаты | Условия: PS |
| 6 ноября – командная олимпиада Санкт-Петербурга и Кирова, легкий тур – Киров | Результаты | Условия: PS |
| 6 ноября – командная олимпиада Санкт-Петербурга и Кирова, сложный тур – ACM | Результаты | Условия: PS |
| 7 ноября – личный тур (задачи A-G – легкие, следующие – сложные) | Результаты | Условия: DOC |
| 8 ноября – легкий командный тур | Результаты | Условия: PS |
| 8 ноября – сложный командный тур | Результаты | Условия: PS |
| 9 ноября – легкий личный тур | Результаты | Условия: DOC |
| 9 ноября – сложный личный тур | Результаты | Условия: DOC |
| 11 ноября – легкий командный тур | Результаты | Условия: RTF |
| 11 ноября – сложный командный тур | Результаты | Условия: PS |
| 12 ноября – легкий личный тур на структуры данных | Результаты | Условия: DOC |
| 12 ноября – сложный личный тур | Результаты | Условия: DOC |
Программы лекций
4 ноября (суббота)
Лекция С: Как эффективно и без ошибок решать олимпиадные задачи по информатике
1. Порядок решения олимпиадной задачи во время тура
2. Оптимальное использование типов данных
3. Программистские ошибки и способы их контроля
4. Эффективное управление директивами компилятора
Лекция B: Инварианты. Введение в нимберсы. Динамическое программирование и метод деления пополам.
Понятие инварианта. Инвариант в математике. Математическая задача о вещественных числах.
Понятие инварианта а программировании на примере задачи поиска K максимальных элементов в массиве, K кратчайших путей в графе. Расширение понятия инварианта в программировании. Задача о наибольшем произведении (выбор трёх чисел из N) в терминах инвариантов. Инвариант как инструмент доказательного программирования.
Операция XOR. Инвариант в игре ним.
Метод динамического программирования как построение инварианта. Связь между инвариантом и функцией динамики на примере задачи «Покупка билетов». Задача о выборе подмножества элементов массива с максимальной суммой, в котором никакие два элемента не являются смежными.
Метод деления пополам. Минимальная теория, детали реализации. Задача «Провода».
Лекция A: LCS & LIS: advanced algorithms
1. Нахождение lcs за O(nm).
2. Алгоритм Хиршберга для нахождения lcs в линейной памяти, O(nm).
3. Нахождение lcs длины не менее k за O((k – n)m).
4. Нахождение lis за O(n\log n).
5. Нахождение lcs за O(r\log n).
5 ноября (воскресенье)
Лекция С: Динамическое программирование
1. Подсчет числа сочетаний: факториалы, рекурсия, динамическое программирование.
2. Общие принципы построения динамического программирования.
3. Основные применения динамического программирования:
б. Нахождение минимального (максимального) решения (задача на минимальную стоимость проезда на сетке).
в. Позиционные игры (задача «Игра с датами»).
4. Задача «Банкомат».
5. «Рюкзак».
Лекция BС: Введение в геометрию
1. Координаты и векторы.
2. Ориентированная площадь.
3. Уравнения линий.
Лекция А: Приближение функций
1. Интерполяционные многочлены Лагранжа и Ньютона.
2. Вычисление многочлена Ньютона через разделенные разности.
3. Выбор узлов интерполяции для уменьшения погрешности.
4. Кусочная интерполяция. Сплайны – кубические, параболические.
6 ноября (понедельник)
Лекция С: О пользе и вреде рекурсии
1. О вреде рекурсии ;)
2. О пользе рекурсии :)
3. Backtracking (Перебор с возвратом)
Лекция B: Максимальный поток и максимальное паросочетание
1. Максимальный поток.
б) сети с несколькими источниками и стоками.
в) алгоритм Форда-Фалкерсона.
г) алгоритм Эдмонса-Карпа.
2. Максимальное паросочетание.
б) сведение задачи о максимальном паросочетании в двудольном графе к задаче о нахождении максимального потока.
3. Решение задач сведения к задаче о построении максимального потока.
Лекция A: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы
7 ноября (вторник)
10.00–15.30 Личный практический тур (с перерывом на обед) сдача решений («одно окно») таблица результатов
16.00–17.30 Лекции (все лекции читаются параллельно)
Лекция С: Рекурсия и динамическое программирование
1. Разбор задач прошедшего тура.
Лекция B: Дерево интервалов. (Система непересекающихся множеств)
1. Дерево интервалов.
2. Дерево максимумов.
3. Дерево отрезков.
4. Быстрый подсчет площади объединения прямоугольников.
5. Другие примеры использования.
(Система непересекающихся множеств)
Лекция A: Производящие функции
1. Что такое производящие функции.
2. Степенные производящие функции.
3. Экспоненциальные производящие функции.
4. Примеры задач.
8 ноября (среда)
Лекция С: Поиск кратчайших путей в графах
1. Поиск кратчайших путей во взвешенных графах.
2. Алгоритм Дейкстры
3. Восстановление пути
4. Примеры
5. Дополнение: использование кучи в Алгоритме дейкстры.
Лекция B: Декартово дерево. Бор
1. Декартово дерево
b. Описание свойств
c. Конкретная реализация операций
d. Напоследок: когда не хватает set, map STL
2. Бор
b. Простейшая реализация
c. Оптимизация предыдущего метода
d. Сжатый бор
e. Разбор задачи «Файловый менеджер» с Всероссийской олимпиады 2006
f. Применение не для строк
g. Построение суффиксного дерева с линейной памятью (?)
h. Вкратце о применении суффиксного дерева (?)
Лекция A: Алгоритмы проверки чисел на простоту и факторизации
1. Тест Соловея-Штрассена.
2. Тест Рабина-Миллера
9 ноября (четверг)
Лекция C: Метод рекурсивного спуска
1. Задача о вычислении значения арифметического выражения
2. Формулы Бэкуса-Науэра для арифметического выражения
3. Написание программы методом рекурсивного спуска.
4. Обощения (отслеживание ошибок, вычисление логических выражений, вычисление переменных, функций, возведение в степень).
5. Пара слов о синтаксическом разборе. Формализация понятия «число».
Лекция B: Геометрия
Вычислительная планиметрия. Векторы. Площадь. Полярный угол. Построение выпуклой оболочки – алгоритмы Грэхема, Джарвиса.
Лекция A: Минимальный разрез в графе
1. Минимальный s-t разрез в графе, связь с максимальным потоком
2. Постановка задачи, наивный алгоритм
3. Решение за O(n) поисков минимальных s-t разрезов
4. Алгоритм проталкивания предпотока, его выгодная модификация
5. Алгоритм поиска минимального разреза в графе
6. Временные оценки для различных реализаций
11 ноября (суббота)
Лекция C: Структуры данных – 1
1. Списки: представление в массиве, списки в динамической памяти; добавление, удаление, поиск элемента; двусвязные и кольцевые списки.
2. Стеки: реализация на массивах, реализация на списках.
3. Очереди: реализация на массиве (циклический буфер), на списках.
4. Деки
5. Бинарный поиск в отсортированном массиве
6. Поиск k-го по величине элемента в массиве
Лекция C++: Использование библиотеки STL
1. Основные контейнеры: vector, stack, queue, map, set, multiset, priority_queue, back(), front() и top()
2. Работа с map/set: count, find, operator [] для map, удаление элементов, использование итераторов, *begin() и *rbegin()
3. Строка и строковый поток: string::substr, istringstream, ostringstream
4. Основные алгоритмы: min/max/swap, sort, stable_sort, next_permutation / prev_permutation, min_element, max_element, reverse, copy, generate, generate_n, find, count, find_first_of, count_if, accumulate, inner_product, binary_search, lower_bound, equal_range
5. Хитрости: vector::reserve, container.swap
6. Полезные мелочи: копирование объектов и const references, #include-файлы, “>>", typedef, make_pair, typeof в GNU
Лекция A: Дерево Фенвика. RMQ, LCA
1. Дерево Фенвика
2. Двумерное дерево Фенвика
3. Метод сжатия координат
4. задача о Парковке
5. FIND_LESS_THAN на отрезке
6. RMQ <O(n*log n), O(1)>
7. LCA <O(n*log n), O(log n)>
12 ноября (воскресенье)
Лекция C: Структуры данных – 2
1. Heap, Heap-sort и очередь с приоритетами
2. Хеш-таблицы: хеш-функции, методы разрешения коллизий, хеширование с открытой адресацией, двойное хеширование
(3. Двоичные деревья поиска: поиск, добавление и удаление, сбалансированные деревья.)
Лекция B: Методы решения геометрических задач
1. Теорема Хелли
2. Метод границ
3. Метод деления на 2dimension
Будут рассмотрены классические задачи
1. Разместить круглый бассейн максимального размера среди колонн.
2. В данном наборе линейных неравенств найти максимальное количество совместных.
Лекция A: Криптография
1. Постановка задачи. Криптография и стеганография.
2. Классические криптографические алгоритмы: шифры замены и перестановки.
3. Абсолютно стойкий шифр и почему им не пользуются.
4. Современная симметричная криптография: потоковые и блочные шифраторы (ГОСТ 28147–89).
5. Хэш-функция SHA1.
6. Современная криптография с открытым ключом: RSA, электронная подпись, открытое распределение ключей.