Структуры данных (9 октября 2013)

  1. Разбор задачи про БОЛЬШОЙ холодильник [код]
  2. Задачи [код]
    1. Удалить из массива за O(1)
    2. Минимум на стеке, минимум на очереди − вы уже знаете
    3. Максимумы на отрезке длины ровно K (через очередь + новая идея)
    4. Отрезок с максимальной суммой
      1. За O(N) через частичные минимумы частичных сумм
      2. За O(N) с O(1) доп.памяти
      3. Числа на окружности, O(N)
      4. Длина отрезка от L до R, O(N)
      5. Длина отрезка от L до R, числа стоят на окружности, O(N)
    5. Подотрезок массива длины не более k с максимальным количеством различных чисел. O(N).
    6. Подотрезок массива, в котором не более k различных чисел максимальной суммы. O(N).
    7. Амортизационный анализ
      1. Про расширяемый вектор: тоже самое, но чуть проще
      2. Структура данных, которая умеет искать сколько чисел от L до R
      3. А еще нужно быстро уметь сливать две структуры.
      4. А теперь задача: сколько чисел от L до R, можно числа добавлять
      5. Обобщение: статическая задача, O(Build), O(Get), получили пополняемую структуру

  3. Теоретические задачи на дом
    Даны N точек, нужно выбрать K так, чтобы минимизировать максимальное из расстояний от исходной до ближайшей выбранной
    1. Точки на прямой, O(NK).
    2. Точки на прямой, O(N × logX).
    3. Точки на окружности, O(N2 × logX).
    4. Точки на окружности, O(N2/K × logX).
    5. Точки на окружности, O(N × logX).

  4. Упражнения
    1. Доказательство корректности алгоритм поиска отрезка с максимальной суммы с O(1) доп.памяти
    2. Решить задачу про отрезок максимальной сумме на окружности за O(N) проще, чем рассказывалось на лекции
    3. Не более k различных чисел на отрезке. Ищем отрезок с максимальной суммой. Обсудили случай "неотрицательные числа". Что делать, если есть отрицательные?