Задачи стек (21 октября 2016)

1. Разбор контеста на динамику
1. [7 минут] nearest (наилучшее приближение, расставить плюсы и минусы)
2. Кодинг
1. [10 минут] Дек на циклическом массиве своими руками. Сравнение: дек на списках, дек на массиве.
2. [7 минут] Двусвязный список с удалением (задача про детей, которые стоят по кругу)
3. Теория
1. [10 минут] Динамический массив (vector): избавимся от амортизации, ленивое копирование (a[i] и push_back за O(1) в худшем)
4. [30 минут] Задачи на стек
1. Несколько типов скобок. Проверить на правильность. Найти парные скобки. O(n).
2. Ближайший слева меньший, ближайший справа меньший за O(n).
3. Массив положительных чисел, ищем отрезок: ∑ × min → max
4. Ищем за O(wh) подпрямоугольник из нулей максимальной площади в матрице
5. [40 минут] Дополнительные задачи
1. Посчитать по всем отрезкам массива сумму "минимум на отрезке" за O(n)
2. Найти количество подпрямоугольников из нулей в матрице
3. Несколько типов скобок. Найти максимальную по длине подстроку, являющуюся правильной скобочной последовательностью за O(n).
4. По бесконечной прямой в одну сторону идут группы людей, скорость движения группы обратно пропорциональна количеству людей. Когда одна группа догоняет другую, оги объединяются. Сколько в итоге групп останется?
6. [skipped] Найти k-ю скобочную последовательность из m типов скобок.
7. [skipped] Разбор выражений стеком