Level 5. Advanced Topics

Advanced DP, segment trees, string algorithms, and number theory — the level of regional olympiad prize winners.

The advanced arsenal: classic DP (the knapsack, LIS), the segment tree, string algorithms and modular arithmetic. These topics are enough for prize places at regional and national olympiads. The readiness criterion for level 6: you write a segment tree without hints and recognize "knapsack" and "string" problems from their statements.

In this section

  1. 1
    Advanced Dynamic Programming

    Classic DP: the 0/1 knapsack in O(n·W) and the longest increasing subsequence in O(n log n).

  2. 2
    Segment Tree

    The segment tree: range sum and point update in O(log n).

  3. 3
    String Algorithms: Hashing and KMP

    Polynomial hashes for comparing substrings in O(1) and the prefix function (KMP) for pattern search.

  4. 4
    Number Theory

    Modular arithmetic: fast exponentiation, the modular inverse and C(n,k) modulo a prime.

Доска