Два указателя, сортировка и бинарный поиск (24 сентября 2015)

  1. [26 минут] Задачи на два указателя
    1. Найти самый длинный подотрезок с суммой не более S
    2. Найти самый длинный подотрезок, на котором не более K нулей
    3. Найти самый длинный подотрезок, на котором не более K различных чисел. Хештаблица, сжатие координат.
    4. Даны N точек xi на прямой. Сопоставить им числа от 1 до N, чтобы было верно (pi < pj) == (xi < xj)
    5. Найти в массиве такие i, j, k : ai + aj + ak = S, O(N2)
    6. Даны N различных натуральных чисел, сколько существует треугольников с такими длинами сторон? O(N2)
    7. Операции с множествами и мультимножествами, как сортированными массивами: пересечение, объединение, разность, merge [code]

  2. [16 минут] Правильный бинпоиск. C кодом на C++: [code] . Версия 2016/17: [code]
    1. Бинпоиск для поиска элемента в отсортированном массиве? Хеш-таблица умеет тоже самое ещё быстрее.
    2. lower_bound
    3. Граничное значение монотонного предиката, который в [-1] не верен, а в [n] верен
    4. lower_bound → первый больший x, последний равный x
    5. C++: lower_bound, upper_bound, binary_search

  3. [40 минут] Задачи на бинпоиск
    1. Дан массив. Запрос: найти в массиве количество чисел от L до R.
    2. Дан массив. Запрос: найти в массиве количество чисел равных X на позициях от L до R.
    3. Дан массив. Запрос: найти позицию первого вхождения X. Пусть ответ равен K, найти за O(logK). (Бинарный поиск не хуже линейного)
    4. Даны N верёвок длин a1, ... aN; можно их резать, склеивать нельзя. Какой максимальной длины L мы сможем получить K кусков длины L?
    5. Даны N точек на прямой. Выбрать K из них, максимизировать минимальное расстояние между ближайшими
    6. Троичный поиск: дан массив A такой, что A[1] < A[2] < ... < A[k] > A[k+1] > ... > A[n], k неизвестно. Найти k за O(logn)
    7. Поиcк вещественного корня многочлена нечётной степени
    8. [homework] Даны N точек xi на прямой. Сопоставить им числа от 1 до N, чтобы было верно (pi < pj) == (xi < xj)

  4. Сложные задачи (ai, bi > 0)
    1. Поиск всех вещественных корней многочлена
    2. [homework] Даны n натуральных пар (ai, bi), выбрать k из них такие, что (∑ ai) / (∑ bi) → max
    3. [homework] Даны n натуральных пар (ai, bi), выбрать k из них такие, что (∑ ai) × (∑ bi) → max