Третья лекция

  1. Изоморфизм деревьев
    1. Проверка за O(NlogN) с хешами
    2. Какие хеш-функции можно использовать? (экспонента, логарифм)
    3. Проверка за O(N) с хешами (ввели понятие "тип вершин", перебираем вершины в порядке возрастания типа)
    4. Избавляемся от хешей: меняем пару "хеш, хеш-таблица" на "бор", ребра бора нужно хранить в хеш-таблице.
    5. Проверка за O(N) без хешей, с маленькиой константой и коротким кодом (в каждой вершине бора храним только одно ребро)
  2. Жадность
    1. Стандартные задачи из теории расписаний
      1. Даны времена выполнения заказов общий дедлайн, выполнить максимум заказов (сортировка)
      2. За каждый не выполненный заказ платим штраф wi, минимизировать штраф
        1. Непрерывная задача: сортировка по частному
        2. Дискретная задача: рюкзак, NP-трудная
      3. Штрафа нет, но дедлайн у каждого заказа свой, выполнить все заказы (сортировка по дедлайну)
      4. Штрафа нет, но дедлайн у каждого заказа свой, выполнить max количество заказов
        1. Решение 1 за O(n2): сортировка по дедлайну, а внутри динамика
        2. Решение 2 за O(n2): заказ с минимальным временем выгодно брать, пытаемся в таком порядке добавлять заказы
        3. Решение 3 за O(nlogn): в решении 1 вместо динамики жадно берем заказ если можем, а если не можем, пытаемся заменить и улучшить суммарное время
    2. Сведение нескольких задач к последней идее
      1. Коробки (масса, прочность)
      2. Школьники вылезают из ямы (рост, длина рук)
      3. Авторитеты (необходимый авторитет для присоединения, изменение авторитета)
    3. Задачи, которые решаются сортировкой
      1. Компаратор: (1,2) лучше (2,1)
      2. Доказательство корректности: транзитивность компаратора.
      3. Пример: задача о двух станках (честное решение не простое, но сортировка (1,2) лучше (2,1) работает)
      4. Ззадача про белоснежку из контеста (см. задачу из контеста)