m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: SMAWK
(convex/monge/smawk.hpp)

Overview

SMAWK finds an optimum in every row of an implicit totally monotone matrix. The matrix is supplied as a callback, so the full rectangular matrix never needs to be stored or evaluated.

The algorithm was introduced by Aggarwal, Klawe, Moran, Shor, and Wilber in Geometric applications of a matrix-searching algorithm.

For minima, total monotonicity means that the leftmost minimizing columns stay nondecreasing after selecting any subset of rows and columns. Every Monge matrix is totally monotone, so SMAWK is the standard linear-time row-minimum primitive for Monge optimization.

All names are in m1une::convex.

Interface

template <class Value>
std::vector<int> smawk_row_argmin(
    int row_count,
    int column_count,
    Value value
);

template <class Value>
std::vector<int> smawk_row_argmax(
    int row_count,
    int column_count,
    Value value
);

value(row, column) returns the matrix entry at that position. The result contains the selected column for every row. Ties choose the leftmost optimum.

Explicit rectangular matrices have convenience overloads:

template <class T>
std::vector<int> smawk_row_argmin(
    const std::vector<std::vector<T>>& matrix
);

template <class T>
std::vector<int> smawk_row_argmax(
    const std::vector<std::vector<T>>& matrix
);

The generic form accepts a strict comparator:

template <class Value, class Compare = std::less<>>
std::vector<int> smawk_row_optima(
    int row_count,
    int column_count,
    Value value,
    Compare compare = Compare()
);

compare(a, b) must return whether a is strictly better than b.

If there are no columns, every answer is -1. If there are no rows, the result is empty.

Requirements

For smawk_row_argmin, the implicit matrix must be totally monotone for leftmost minima. For smawk_row_argmax, it must be totally monotone under the reversed comparison. The implementation does not verify this precondition.

The callback may return values by value or by reference. Values only need to support the selected comparison.

Complexity

SMAWK uses $O(H + W)$ callback evaluations and $O(H + W)$ additional memory for an H by W matrix. This assumes each callback evaluation and comparison take $O(1)$ time.

Example

#include "convex/monge/smawk.hpp"
#include <iostream>

int main() {
    int rows = 5;
    int columns = 8;
    auto value = [](int row, int column) {
        long long difference = row * 2LL - column;
        return difference * difference;
    };

    auto argmin = m1une::convex::smawk_row_argmin(rows, columns, value);
    for (int column : argmin) std::cout << column << "\n";
}

Required by

Verified with

Code

#ifndef M1UNE_CONVEX_MONGE_SMAWK_HPP
#define M1UNE_CONVEX_MONGE_SMAWK_HPP 1

#include <cassert>
#include <functional>
#include <numeric>
#include <vector>

namespace m1une {
namespace convex {

namespace smawk_detail {

template <class Select>
void solve(const std::vector<int>& rows, const std::vector<int>& columns,
           const Select& select, std::vector<int>& answer) {
    if (rows.empty()) return;

    std::vector<int> reduced;
    reduced.reserve(columns.size());
    for (int column : columns) {
        while (!reduced.empty()) {
            int row = rows[int(reduced.size()) - 1];
            if (!select(row, reduced.back(), column)) break;
            reduced.pop_back();
        }
        if (reduced.size() < rows.size()) reduced.push_back(column);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < int(rows.size()); i += 2) odd_rows.push_back(rows[i]);
    solve(odd_rows, reduced, select, answer);

    int left = 0;
    int right = 0;
    for (int i = 0; i < int(rows.size()); i += 2) {
        if (i + 1 < int(rows.size())) {
            while (reduced[right] != answer[rows[i + 1]]) right++;
        } else {
            right = int(reduced.size()) - 1;
        }

        int best = left;
        for (int j = left + 1; j <= right; j++) {
            if (select(rows[i], reduced[best], reduced[j])) {
                best = j;
            }
        }
        answer[rows[i]] = reduced[best];
        left = right;
    }
}

template <class Select>
std::vector<int> row_optima(int row_count, int column_count, const Select& select) {
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;

    std::vector<int> rows(row_count), columns(column_count);
    std::iota(rows.begin(), rows.end(), 0);
    std::iota(columns.begin(), columns.end(), 0);
    solve(rows, columns, select, answer);
    return answer;
}

}  // namespace smawk_detail

template <class Value, class Compare = std::less<>>
std::vector<int> smawk_row_optima(int row_count, int column_count, Value value,
                                  Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    return smawk_detail::row_optima(
        row_count, column_count,
        [&](int row, int current, int candidate) {
            return compare(value(row, candidate), value(row, current));
        });
}

template <class Value>
std::vector<int> smawk_row_argmin(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> smawk_row_argmax(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> smawk_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> smawk_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_SMAWK_HPP
#line 1 "convex/monge/smawk.hpp"



#include <cassert>
#include <functional>
#include <numeric>
#include <vector>

namespace m1une {
namespace convex {

namespace smawk_detail {

template <class Select>
void solve(const std::vector<int>& rows, const std::vector<int>& columns,
           const Select& select, std::vector<int>& answer) {
    if (rows.empty()) return;

    std::vector<int> reduced;
    reduced.reserve(columns.size());
    for (int column : columns) {
        while (!reduced.empty()) {
            int row = rows[int(reduced.size()) - 1];
            if (!select(row, reduced.back(), column)) break;
            reduced.pop_back();
        }
        if (reduced.size() < rows.size()) reduced.push_back(column);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < int(rows.size()); i += 2) odd_rows.push_back(rows[i]);
    solve(odd_rows, reduced, select, answer);

    int left = 0;
    int right = 0;
    for (int i = 0; i < int(rows.size()); i += 2) {
        if (i + 1 < int(rows.size())) {
            while (reduced[right] != answer[rows[i + 1]]) right++;
        } else {
            right = int(reduced.size()) - 1;
        }

        int best = left;
        for (int j = left + 1; j <= right; j++) {
            if (select(rows[i], reduced[best], reduced[j])) {
                best = j;
            }
        }
        answer[rows[i]] = reduced[best];
        left = right;
    }
}

template <class Select>
std::vector<int> row_optima(int row_count, int column_count, const Select& select) {
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;

    std::vector<int> rows(row_count), columns(column_count);
    std::iota(rows.begin(), rows.end(), 0);
    std::iota(columns.begin(), columns.end(), 0);
    solve(rows, columns, select, answer);
    return answer;
}

}  // namespace smawk_detail

template <class Value, class Compare = std::less<>>
std::vector<int> smawk_row_optima(int row_count, int column_count, Value value,
                                  Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    return smawk_detail::row_optima(
        row_count, column_count,
        [&](int row, int current, int candidate) {
            return compare(value(row, candidate), value(row, current));
        });
}

template <class Value>
std::vector<int> smawk_row_argmin(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> smawk_row_argmax(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> smawk_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> smawk_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une
Back to top page