m1une's library

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

View on GitHub

:heavy_check_mark: Knuth Optimization
(convex/monge/knuth_optimization.hpp)

Overview

Knuth optimization accelerates interval dynamic programming of the form

\[dp[l][r] = w(l,r) + \min_{l < k < r}\left(dp[l][k] + dp[k][r]\right).\]

All intervals are half-open. Singleton and empty intervals have value zero. The implementation returns every interval value and its optimal split.

The optimization originates in Knuth’s Optimum binary search trees.

Interface

template <class IntervalCost>
auto knuth_optimization(
    int element_count,
    IntervalCost interval_cost
);

interval_cost(left, right) returns w(left, right) for [left, right).

The result is KnuthOptimizationResult<T>:

Member / Method Meaning
value[l][r] Optimal value for [l, r).
split[l][r] Leftmost optimal split k.
optimum() Returns value[0][element_count].

For intervals of length at least two, the split is strictly inside the interval.

Requirement

The recurrence must satisfy Knuth’s monotonicity:

\[opt[l][r-1] \le opt[l][r] \le opt[l+1][r].\]

A standard sufficient condition is that w obeys the quadrangle inequality and interval monotonicity. For a <= b <= c <= d:

\[w(a,c) + w(b,d) \le w(a,d) + w(b,c)\]

and

\[w(b,c) \le w(a,d).\]

Nonnegative interval sums are a common example. The implementation assumes the condition and does not verify it.

Complexity

$O(N^2)$ time and $O(N^2)$ memory, improving the unrestricted cubic recurrence.

Example

#include "convex/monge/knuth_optimization.hpp"
#include <vector>

int main() {
    std::vector<long long> weight = {2, 5, 1, 4};
    std::vector<long long> prefix(weight.size() + 1);
    for (int i = 0; i < int(weight.size()); i++) {
        prefix[i + 1] = prefix[i] + weight[i];
    }

    auto result = m1une::convex::knuth_optimization(
        int(weight.size()),
        [&](int left, int right) {
            return prefix[right] - prefix[left];
        });
}

Required by

Verified with

Code

#ifndef M1UNE_CONVEX_MONGE_KNUTH_OPTIMIZATION_HPP
#define M1UNE_CONVEX_MONGE_KNUTH_OPTIMIZATION_HPP 1

#include <algorithm>
#include <cassert>
#include <type_traits>
#include <vector>

namespace m1une {
namespace convex {

template <class T>
struct KnuthOptimizationResult {
    std::vector<std::vector<T>> value;
    std::vector<std::vector<int>> split;

    T optimum() const {
        return value[0].back();
    }
};

template <class IntervalCost>
auto knuth_optimization(int element_count, IntervalCost interval_cost)
    -> KnuthOptimizationResult<
        std::decay_t<std::invoke_result_t<IntervalCost, int, int>>> {
    assert(element_count >= 0);
    using T = std::decay_t<std::invoke_result_t<IntervalCost, int, int>>;

    KnuthOptimizationResult<T> result;
    result.value.assign(element_count + 1, std::vector<T>(element_count + 1, T()));
    result.split.assign(element_count + 1, std::vector<int>(element_count + 1, -1));

    for (int left = 0; left <= element_count; left++) result.split[left][left] = left;
    for (int left = 0; left < element_count; left++) result.split[left][left + 1] = left + 1;

    for (int length = 2; length <= element_count; length++) {
        for (int left = 0; left + length <= element_count; left++) {
            int right = left + length;
            int first = std::max(left + 1, result.split[left][right - 1]);
            int last = std::min(right - 1, result.split[left + 1][right]);
            assert(first <= last);

            int best = first;
            T best_value = result.value[left][best] + result.value[best][right];
            for (int split = first + 1; split <= last; split++) {
                T candidate = result.value[left][split] + result.value[split][right];
                if (candidate < best_value) {
                    best = split;
                    best_value = candidate;
                }
            }
            result.value[left][right] = best_value + interval_cost(left, right);
            result.split[left][right] = best;
        }
    }
    return result;
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_KNUTH_OPTIMIZATION_HPP
#line 1 "convex/monge/knuth_optimization.hpp"



#include <algorithm>
#include <cassert>
#include <type_traits>
#include <vector>

namespace m1une {
namespace convex {

template <class T>
struct KnuthOptimizationResult {
    std::vector<std::vector<T>> value;
    std::vector<std::vector<int>> split;

    T optimum() const {
        return value[0].back();
    }
};

template <class IntervalCost>
auto knuth_optimization(int element_count, IntervalCost interval_cost)
    -> KnuthOptimizationResult<
        std::decay_t<std::invoke_result_t<IntervalCost, int, int>>> {
    assert(element_count >= 0);
    using T = std::decay_t<std::invoke_result_t<IntervalCost, int, int>>;

    KnuthOptimizationResult<T> result;
    result.value.assign(element_count + 1, std::vector<T>(element_count + 1, T()));
    result.split.assign(element_count + 1, std::vector<int>(element_count + 1, -1));

    for (int left = 0; left <= element_count; left++) result.split[left][left] = left;
    for (int left = 0; left < element_count; left++) result.split[left][left + 1] = left + 1;

    for (int length = 2; length <= element_count; length++) {
        for (int left = 0; left + length <= element_count; left++) {
            int right = left + length;
            int first = std::max(left + 1, result.split[left][right - 1]);
            int last = std::min(right - 1, result.split[left + 1][right]);
            assert(first <= last);

            int best = first;
            T best_value = result.value[left][best] + result.value[best][right];
            for (int split = first + 1; split <= last; split++) {
                T candidate = result.value[left][split] + result.value[split][right];
                if (candidate < best_value) {
                    best = split;
                    best_value = candidate;
                }
            }
            result.value[left][right] = best_value + interval_cost(left, right);
            result.split[left][right] = best;
        }
    }
    return result;
}

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