Задачи на динамику (7 октября 2016)

  1. [35 минут] Динамика: общие идеи
    1. Количество способов дойти из 1 в N, используя ходы +1,+2,...,+k
    2. Калькулятор.Easy: x → x+1, 2x, 3x; n ≤ 106. Простая линейная динамика.
    3. Динамика вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор)
    4. Калькулятор.Hard: x → 2x+1, 3x+2, 5x+1 ; n ≤ 1018. Ленивая динамика с конца.
    5. Динамика и ацикличный граф: состояния, переходы, вперед, назад, ленивость
    6. Восстановление ответа, 2 способа: или храним ссылки между состояниями , или не храним
− Перерыв −
  1. [25 минут] Задачи (простые)
    1. Максимальный по сумме чисел лево-верхний путь в "матрице чисел c непроходимыми дырками" (простое упрожнение)
    2. Задача Иосифа (n людей по кругу, считалочка, выходит каждый k-й, кто остался?). O(n). (учимся видеть состояния)
    3. Есть одна кучка. Двое играют в игру "первый может брать a1, a2, ... ak, второй может брать b1, ... bm", кто не может ходить проиграл (более сложное состояние)
    4. Выбрать самую длинную подпоследовательность-палиндром O(n2) (динамика по подотрезкам)
    5. [skipped] Оптимизируем память: до O(n), если не нужно восстанавливать ответ, до O(n2/wordsize), если нужно.
  2. [30 минут] Задачи (посложнее)
    1. Рюкзак без стоимостей (набрать вес ровно W подмножеством предметов). Решается за O(2n/2n) и O(nW/wordsize).
      1. Решение за O(nW) времени и памяти, оптимируем память до O(nW/wordsize)
      2. [skipped] Оптимизируем время до O(nW/wordsize) (bitset = массив + битовые операции, как с целыми числами)
      3. O(W) памяти одним массивом, без восстановления ответа
      4. O(W) памяти с восстановлением ответа, доказываем, что в ответе нет повторов
    2. Наибольшая общая возрастающая подпоследовательность за O(n2)
      1. НВП = online курс, НОП = f[i,j]
      2. Решение НОВП за n3: f[i,j,prev], i и j не обязательно концы последовательностей
      3. Решение НОВП за n4: f[i,j], i и j обязательно концы последовательностей, prev=a[i]
      4. Решение НОВП за n3 и n2 памяти: f[i,j], i − конец, j − необязательно
      5. Решение НОВП за n2: то же, что и предыдущее, но слудующее i возьмём жадно
    3. [skipped] Folding: запаковать строку timus : 1238 за O(n3)
      1. [skipped] Решаем за O(n4)
      2. [skipped] Решаем за O(n3 log n) − догадались перебирать только делители
      3. [skipped] Решаем за O(n3) − догадались насчитать динамику LCP[i,j]