Задачи про точки на прямой. Метод разделяй и властвуй. (1 октября 2015)
- [20 минут] Подотрезок максимальной суммы
- Подотрезок максимальной суммы: решение частичными суммами + максимумами
- Подотрезок максимальной суммы: жадное решение
- Подотрезок максимальной суммы, на котором не менее K различных чисел
- [30 минут] Задачи про точки на прямой и на плоскости (дифференцирование, два указателя, бинарный поиск по ответу). Во всех задачах даны точки (xi, yi), найти точку (x, y).
- ∑ (xi-z)2 → min (и версия с весами, решение − дифференцирование)
- ∑ (xi-x)2 + (yi-y)2 → min (и версия с весами, решение − дифференцирование)
- ∑ |xi-x| → min (и версия с весами, решение без весов − медиана, решение с весами − сортировка)
- ∑ |xi-x| + |yi-y| → min (и версия с весами, решение без весов − медиана, решение с весами − сортировка)
- (*) max wi|xi-z| → min (решение − бинарный поиск по ответу)
- (*) ∑ max(|xi-x|, |yi-y|) → min (поворот на 45)
- [30 минут] Разделяй и властвуй
- Сортировка слиянием и число инверсий (код). Решение задачи про 3-инверсии.
- Алгоритм Карацубы перемножения длинных чисел: напоминание алгоритма, подробности реализации (не делать переносы, длина − степень двойки)
- Две ближайшие точки в 2D
- [не успеем] Две ближайшие точки в 3D