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

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