SQRT heuristics - Course 4

Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 4/Module 9: SQRT Techniques/SQRT heuristics

SQRT heuristics

SQRT heuristics

Root heuristics is a generalized name for methods and data structures that rely on the fact:

if you split a set of $n$ elements into blocks of $\sqrt{n}$ elements, then there will be no more than $\sqrt{n}$ blocks.

Up next

Mo’s Algorithm

Mo’s Algorithm

Key idea:
“there are many small objects, but they are small; there are few large objects”

Splitting into heavy and light objects

A classic example is square-root factorization.

If $d \ge \sqrt{n}$ is a “large” divisor of the number $n$ , then it corresponds to a “small” divisor:

$\frac{n}{d} \le \sqrt{n}.$

That is, there are few large divisors, because each large one corresponds to a small one.

Such logic is often transferred to other objects: strings, graph vertices, query types, item weights, etc.

Long and short strings

Problem

You need to maintain a set of strings online and process operations:

Add a string to the set
Remove a string from the set
For a given string, count how many times it occurs as a substring among all strings in the set

Idea

Split strings into:

short: $|s| < L$
long: $|s| \ge L$

Here $L$ is chosen as $\sqrt{S}$ , where $S$ is the total length of all strings.

Then there are few long strings: no more than $\frac{S}{L} = O(\sqrt{S})$ .

How to answer queries

For add/remove:
- iterate over all short substrings of the string
- compute their hashes and update a hash table (counter)
Query type 3:
- if the string is short, just look up its hash in the table
- if the string is long, we can afford to check it against all strings in the set (because there will be few long queries)

Triangles in a graph

Problem

Given a graph with $n$ vertices and $m \approx n$ edges. You need to count the number of cycles of length 3 (triangles).

Definition of a heavy vertex

A vertex is heavy if its degree is greater than $\frac{S}{L} = O(\sqrt{S})$ , otherwise it is light.

There are few heavy vertices: no more than $O(\sqrt{n})$ .

Estimating the number of triangles

We break it down by the number of heavy vertices in the triangle:

No heavy vertices
The triangle has an edge $(a,b)$ , the third vertex $c$ lies in the intersection/union of neighbors.
Since degrees are small, we get a bound on the order of $m \approx n$ .
One heavy
Similarly: there is a “light” edge → the estimate is also $O(m\sqrt{n})$ .
Two heavy
Fix the edge $(a,c)$ , there are $O(m)$ ways.
There are only $O(\sqrt{n})$ heavy vertices → again .
Three heavy
There are few heavy vertices, brute force also fits.

In total, there are “not that many” triangles: on the order of $O(m\sqrt{n})$ .

Simple solution (idea)

Sort vertices by (degree, id).
Then iterate over paths of the form $v \to u \to w$ in the correct order and check for the presence of the edge $v \to w$ .

Knapsack in $O(S\sqrt{S})$ and faster

Statement

There are $n$ items with weights $w_1, \dots, w_n$ , and:

$\sum w_i = S.$

Standard DP works in $O(S \cdot n)$ .

Observation: there are few distinct weights

If there are $k$ distinct positive weights with sum $S$ , then:

$S \ge 1 + 2 + \dots + k = \frac{k(k+1)}{2}$

hence:

$k \le O(\sqrt{S}).$

That is, the number of distinct weights is at most $O(\sqrt{S})$ .

Compressing multiplicities (decomposition into powers of two)

If weight $x$ occurs $k$ times, decompose $k$ into a sum of powers of two and replace these $k$ items with items of weights:

$x,\ 2x,\ 4x,\ \dots$

This preserves all sums of the form $q \cdot x$ for $q \le k$ .

After such a transformation, the number of items becomes on the order of $O(number\_of\_weights \cdot \log S)$ , and then we run the standard DP.

Note: the knapsack solution can be greatly sped up using bitset.

)

O(m\sqrt{n})

long long count_triangles(int n, vector<vector<int>> &g) {
    vector<int> deg(n);
    for (int v = 0; v < n; v++) deg[v] = (int)g[v].size();

    auto better = [&](int a, int b) {
        if (deg[a] != deg[b]) return deg[a] < deg[b];
        return a < b;
    };

    // sort vertices by (degree, id)
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), better);

    // sort adjacency lists in the same order
    for (int v = 0; v < n; v++) {
        sort(g[v].begin(), g[v].end(), better);
    }

    vector<int> cnt(n, 0);
    long long ans = 0;

    for (int v : order) {
        // mark all "forward" neighbors of v
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 1;
        }

        // count triangles v - u - w where v<u<w in this order
        for (int u : g[v]) {
            if (!better(v, u)) break;
            for (int w : g[u]) {
                if (!better(u, w)) break;
                ans += cnt[w];
            }
        }

        // unmark
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 0;
        }
    }

    return ans;
}