m1une's library

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

View on GitHub

:heavy_check_mark: Alien Trick
(convex/alien_trick.hpp)

Overview

The Alien Trick, also called Lagrangian relaxation or WQS binary search, converts an optimization problem with an exact-count constraint into a sequence of unconstrained penalized problems.

This header provides:

Both functions return the optimum among solutions whose count is exactly target_count.

The public namespace is m1une::convex.

Oracle Contract

For minimization, oracle(penalty) must return a pair {penalized_value, count} minimizing

\[\mathrm{original\ value} + \mathrm{penalty} \cdot \mathrm{count}.\]

For maximization, it must return a pair maximizing

\[\mathrm{original\ value} - \mathrm{penalty} \cdot \mathrm{count}.\]

If several solutions have the same penalized value, the oracle must choose the one with the larger count. Consequently, the returned count is non-increasing as the penalty increases.

The exact-count optimum must be discrete convex for minimization or discrete concave for maximization. Without this condition, the relaxed problem can skip the requested count and the Alien Trick cannot recover its optimum.

Penalty Bounds

lower and upper are inclusive integral penalty bounds. They must satisfy:

All values, penalties, products, and intermediate oracle calculations must fit their respective types.

Complexity

If one oracle call takes $O(D)$ time, the helper takes $O(D \log(\mathrm{upper}-\mathrm{lower}+1))$ time and $O(1)$ additional space, excluding the oracle.

Example

#include "convex/alien_trick.hpp"

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::vector<long long> exact = {25, 12, 5, 2, 3, 8};

    auto oracle = [&exact](long long penalty) {
        std::pair<long long, int> best;
        best.first = exact[0];
        best.second = 0;
        for (int count = 1; count < int(exact.size()); count++) {
            long long value = exact[count] + penalty * count;
            if (value < best.first || (value == best.first && best.second < count)) {
                best.first = value;
                best.second = count;
            }
        }
        return best;
    };

    std::cout << m1une::convex::alien_trick_minimize(
        -100LL,
        100LL,
        3,
        oracle
    ) << "\n";
}

Required by

Verified with

Code

#ifndef M1UNE_CONVEX_ALIEN_TRICK_HPP
#define M1UNE_CONVEX_ALIEN_TRICK_HPP 1

#include <cassert>
#include <concepts>
#include <numeric>
#include <type_traits>
#include <utility>

namespace m1une {
namespace convex {

namespace detail {

template <std::integral Penalty, std::integral Count, class Oracle>
Penalty alien_trick_penalty(Penalty lower, Penalty upper, Count target_count, Oracle& oracle) {
    assert(lower <= upper);
    assert(oracle(lower).second >= target_count);
    assert(oracle(upper).second <= target_count);

    while (lower < upper) {
        Penalty middle = std::midpoint(lower, upper);
        if (middle == lower) ++middle;
        if (oracle(middle).second >= target_count) {
            lower = middle;
        } else {
            upper = middle - 1;
        }
    }
    return lower;
}

}  // namespace detail

// Recovers the minimum value among solutions using exactly `target_count`
// items. The oracle minimizes value + penalty * count and breaks ties in favor
// of the larger count.
template <std::integral Penalty, std::integral Count, class Oracle>
auto alien_trick_minimize(Penalty lower, Penalty upper, Count target_count, Oracle oracle) {
    Penalty penalty = detail::alien_trick_penalty(lower, upper, target_count, oracle);
    auto result = oracle(penalty);
    using Value = std::remove_cvref_t<decltype(result.first)>;
    return result.first - static_cast<Value>(penalty) * static_cast<Value>(target_count);
}

// Recovers the maximum value among solutions using exactly `target_count`
// items. The oracle maximizes value - penalty * count and breaks ties in favor
// of the larger count.
template <std::integral Penalty, std::integral Count, class Oracle>
auto alien_trick_maximize(Penalty lower, Penalty upper, Count target_count, Oracle oracle) {
    Penalty penalty = detail::alien_trick_penalty(lower, upper, target_count, oracle);
    auto result = oracle(penalty);
    using Value = std::remove_cvref_t<decltype(result.first)>;
    return result.first + static_cast<Value>(penalty) * static_cast<Value>(target_count);
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_ALIEN_TRICK_HPP
#line 1 "convex/alien_trick.hpp"



#include <cassert>
#include <concepts>
#include <numeric>
#include <type_traits>
#include <utility>

namespace m1une {
namespace convex {

namespace detail {

template <std::integral Penalty, std::integral Count, class Oracle>
Penalty alien_trick_penalty(Penalty lower, Penalty upper, Count target_count, Oracle& oracle) {
    assert(lower <= upper);
    assert(oracle(lower).second >= target_count);
    assert(oracle(upper).second <= target_count);

    while (lower < upper) {
        Penalty middle = std::midpoint(lower, upper);
        if (middle == lower) ++middle;
        if (oracle(middle).second >= target_count) {
            lower = middle;
        } else {
            upper = middle - 1;
        }
    }
    return lower;
}

}  // namespace detail

// Recovers the minimum value among solutions using exactly `target_count`
// items. The oracle minimizes value + penalty * count and breaks ties in favor
// of the larger count.
template <std::integral Penalty, std::integral Count, class Oracle>
auto alien_trick_minimize(Penalty lower, Penalty upper, Count target_count, Oracle oracle) {
    Penalty penalty = detail::alien_trick_penalty(lower, upper, target_count, oracle);
    auto result = oracle(penalty);
    using Value = std::remove_cvref_t<decltype(result.first)>;
    return result.first - static_cast<Value>(penalty) * static_cast<Value>(target_count);
}

// Recovers the maximum value among solutions using exactly `target_count`
// items. The oracle maximizes value - penalty * count and breaks ties in favor
// of the larger count.
template <std::integral Penalty, std::integral Count, class Oracle>
auto alien_trick_maximize(Penalty lower, Penalty upper, Count target_count, Oracle oracle) {
    Penalty penalty = detail::alien_trick_penalty(lower, upper, target_count, oracle);
    auto result = oracle(penalty);
    using Value = std::remove_cvref_t<decltype(result.first)>;
    return result.first + static_cast<Value>(penalty) * static_cast<Value>(target_count);
}

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