Сортировки, жадность (25 сентября 2014)

1. Даны N различных чисел от 1 до N, сколько существует треугольников с такими длинами сторон?
1. За O(N³)
2. За O(N²) − метод двух указателей
3. Доказательство, что метод двух указателей работает за O(N)
2. Задачи на сортировку, жадность
1. Набрать самую сильную команду из k человек (у каждого есть сила, берем k-ю порядковую статистику)
2. Рюзкзак
1. mini дискретный рюкзак: дано W и a_i, выбрать подмножество a_i, сумма которых ровно W
2. У каждой вещи есть стоимость и вес, вещи можно резать. Непрерывный рюкзак.
3. У каждой вещи есть стоимость и вес, вещи нельзя резать. Дискретный рюкзак.
3. Про суммы (выбрать k пар из n данных так, чтобы)
1. ∑ (a_ib_i) → max (решили за Θ(n))
2. (∑ a_i) / (∑ b_i) → max (решили за Θ(nlogM)) [code]
3. (∑ a_i) × (∑ b_i) → max (свели рюкзак, доказали, что NP-трудна)
4. Про отрезки
1. Максимальное число непересекающихся отрезков [code]
2. Найти длину объединения отрезков [code]
3. Найти точку, покрытую максимальным числом отрезков [code]
3. Программируем
1. Задачку про частное сумм
2. Все три задачи про отрезки