Задачи про точки на прямой. Метод разделяй и властвуй. (1 октября 2015)

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