Уровень 5. Продвинутые темы

Продвинутое ДП, дерево отрезков, строковые алгоритмы и теория чисел — уровень призёров региональных олимпиад.

Продвинутый арсенал: классические ДП (рюкзак, LIS), дерево отрезков, строковые алгоритмы и модульная арифметика. Этих тем достаточно для призовых мест на областных и республиканских олимпиадах. Критерий готовности к уровню 6: вы пишете дерево отрезков без подсказок и распознаёте «рюкзачные» и «строковые» задачи по формулировке.

В этом разделе

  1. 1
    Продвинутое динамическое программирование

    Классические ДП: рюкзак 0/1 за O(n·W) и наибольшая возрастающая подпоследовательность за O(n log n).

  2. 2
    Дерево отрезков

    Дерево отрезков: сумма на отрезке и обновление точки за O(log n).

  3. 3
    Алгоритмы на строках: хеширование и KMP

    Полиномиальные хеши для сравнения подстрок за O(1) и префикс-функция (KMP) для поиска образца.

  4. 4
    Теория чисел

    Модульная арифметика: быстрое возведение в степень, обратный элемент и C(n,k) по модулю.

Доска