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

  1. [7 минут] Для каждого числа первого массива определить, есть ли оно во втором
    1. Сортировка и бинпоиск
    2. Два указателя
    3. Хеш-таблица
  2. [26 минут] Задачи на два указателя
    1. Найти самый длинный подотрезок с суммой не более S
    2. Найти самый длинный подотрезок, на котором не более K нулей
    3. Найти самый длинный подотрезок, на котором не более K различных чисел
    4. Найти в массиве такие i, j, k : ai + aj + ak = S, O(N2)
    5. Даны N различных натуральных чисел, сколько существует треугольников с такими длинами сторон? O(N2)
    6. Операции с множествами и мультимножествами, как сортированными массивами: пересечение, объединение, разность, merge [code]
  3. [16 минут] Правильный бинпоиск. C кодом на C++: [code]
    1. lower_bound
    2. Граничное значение монотонного предиката, который в [-1] не верен, а в [n] верен
    3. lower_bound → первый больший x, последний равный x
    4. C++: lower_bound, upper_bound, binary_search [code] Java: binarySearch
  4. [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. [не успеем] Даны N точек на плоскости. Запрос: точка (X, Y), найти ближайшую по X с таким же Y.
    9. [не успеем] Даны N точек xi на прямой. Сопоставить им числа от 1 до N, чтобы было верно (pi < pj) == (xi < xj)
  5. [1 минута] Сложные задачи (ai, bi > 0)
    1. [не успеем] Поиск всех вещественных корней многочлена
    2. [не успеем] Даны n натуральных пар (ai, bi), выбрать k из них такие, что (∑ ai) / (∑ bi) → max
    3. [не успеем] Даны n натуральных пар (ai, bi), выбрать k из них такие, что (∑ ai) × (∑ bi) → max