CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage


Time Complexity

Optimising DP with Segtree

Tree DP Complexity

dfs(src, par):
    for c in adj[src]:
        if c == par
        dfs(c, par)
        for x in range(adj[src].size):
            for y in range(adj[c].size):
                print("hello world")

The time complexity of this function is O(n^2). Why?

Transitions in Bitmask DP


for cnt in [1, n]:
    for mask in [0, 2^n]:
        if set_bit_count(mask) != cnt:
        for set bit i in mask:
            for unset bit j in mask:
                nxt = mask | (1 << j)
                dp[j][nxt] = func(dp[i][mask])

What is the time complexity of this DP? It looks like $O(n^3 \cdot 2^n)$, but it’s actually $O(n^2 \cdot 2^n)$. Why? The time complexity of the inner 2 for-loops is $O(n^2)$. Now, consider any bitmask b. How many times will the inner 2 for-loops be executed for this bitmask? Exactly once. Since there are $2^n$ unique bitmasks, the total time complexity is $O(n^2 \cdot 2^n)$.

A different argument : When cnt is equal to r, there are $n \choose r$ bitmasks for which the inner 2 for-loops would be executed. Hence, the time complexity is

$$ n^2 \cdot \left[ {n \choose 0} + {n \choose 1} + \dots {n \choose n}\right] = n^2 \cdot 2^n $$

Hence, this style can be used to solve variations of TSP and Hamiltonian path problems. Here, the transitions are intuitive, BFS like. The first level contains paths with one element, all of them are processed first. Then, the second level contains 2 elements in the path, all of them are processed before moving onto the 3rd level and so on.

But what if you want to use the classical algorithm for TSP? In this distributing DP, how are you sure that there are no partial contributions?

for mask in [0, 2^n]:
    for set bit i in mask:
        for unset bit j in mask:
            nxt = mask | (1 << j)
            dp[j][nxt] = func(dp[i][mask])

Note that any mask will take contribution from its submasks only. A submask is always less than a mask. Hence, by the time we reach a particular mask, it would already have taken all the contributions it was supposed to. Hence, its own DP value is now correct, and we can push its contribution to its supermasks.

Another argument: Arrange all the bitmasks on the number line from left to right, and draw a directed edge from x to y if x can provide contribution to y. You can see that the resulting graph would be a DAG, and 1, 2, ... n would be a toplogical ordering. Hence, processing DP from left to right works.

Custom Comparator for Set

auto func = [](pair<int, int> small, pair<int, int> big) {
            if (small.first == big.first) {
                return small.second > big.second;
            return small.first < big.first;
        set<pair<int, int>, decltype(func)> current_degrees(func);