SMAWK algoritmi

Problem Statement

We are given a totally monotone matrix $a_{i,j}$ of size $N \times M$ .

For each row, we need to find the column where the minimum value is achieved. More formally, we want to compute $f_1, f_2, \ldots, f_N$ where

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESMilutin's Plums

Rating: 2800

SMAWK algoritmi - Resources

…

f_i = \arg \min_{1 \leq j \leq M} a_{i,j}

Solution

A key observation is that the sequence of row minima positions $f_1, f_2, \ldots, f_N$ is non-decreasing.

Because of this, one can already apply divide and conquer and solve the problem in $O(N \log N)$ . However, there is an even faster algorithm called SMAWK, which solves it in $O(N + M)$ time.

The algorithm is based on two main ideas of Reduce and Interpolate.

Reduce

In this step, we try to remove columns that definitely cannot contain a row minimum.

The goal is to reduce the number of columns to at most $N$ .

We maintain a stack S of columns that have not been eliminated yet. Initially, the stack is empty.

Then we process columns from left to right, one by one.

When we process column j, we do the following:

If S is empty, push column j.
Otherwise, let
- i = |S|
- h = S.back()

Now compare the values in row i:

a_{i,j} \le a_{i,h}

then column h can be removed, so we pop it from the stack and repeat.

Otherwise, column j is added to the stack if the stack size is still smaller than N.

So the code looks like this:

This step removes many unnecessary columns while preserving all possible row minima.

Interpolate

Now we solve the problem recursively only for every second row, for example for all even-indexed rows.

After we know the minima for those rows, we can restore the minima for the remaining rows.

The reason is that the answer is non-decreasing, so for an odd row i we know that:

f_{i-1} \le f_i \le f_{i+1}

Therefore, to find f_i, it is enough to do a linear search only in the restricted range from f_{i-1} to f_{i+1}.

This makes the interpolation step efficient.

Full Algorithm

The full SMAWK algorithm works as follows:

If $N = 1$ , solve the problem directly by scanning the row.
If $M > N$ , perform one Reduce step.
Recursively solve the problem for every second row.
Use Interpolate to recover the answers for the remaining rows.

These steps call each other recursively, and the total complexity is: $O(N + M)$

vector<int> S;
for (int j = 1; j <= m; j++) {
    while (!S.empty() && a[S.size()][S.back()] > a[S.size()][j]) {
        S.pop_back();
    }
    if ((int)S.size() < n) {
        S.push_back(j);
    }
}