Function bounded_requirements_from_extrema 

fn bounded_requirements_from_extrema<T>(
    a_len: usize,
    b_len: usize,
    (a_min, a_max): (T, T),
    (b_min, b_max): (T, T),
) -> Option<BoundedRequirements<T>>
where
    T: Signed,
    T::Unsigned: TryInto<usize>,

Examples found in repository

crates/competitive/src/math/min_plus_convolution/mod.rs (line 209)

pub fn min_plus_convolution_bounded_ntt<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
    T::Unsigned: TryInto<usize>,
{
    let output_len = output_len(a.len(), b.len());
    if output_len == 0 {
        return Vec::new();
    }
    let (Some(a_extrema), Some(b_extrema)) = (finite_extrema(a), finite_extrema(b)) else {
        return vec![T::maximum(); output_len];
    };
    let requirements = bounded_requirements_from_extrema(a.len(), b.len(), a_extrema, b_extrema)
        .expect("bounded min-plus convolution encoding must fit the 2^23 NTT limit");
    let mut left = vec![MInt998244353::from(0_u32); a.len() * requirements.base];
    let mut right = vec![MInt998244353::from(0_u32); b.len() * requirements.base];
    for (index, &value) in a.iter().enumerate() {
        if !value.is_maximum() {
            let normalized: usize = value
                .abs_diff(requirements.a_min)
                .try_into()
                .ok()
                .expect("bounded min-plus convolution value span must fit usize");
            left[index * requirements.base + normalized] = MInt998244353::from(1_u32);
        }
    }
    for (index, &value) in b.iter().enumerate() {
        if !value.is_maximum() {
            let normalized: usize = value
                .abs_diff(requirements.b_min)
                .try_into()
                .ok()
                .expect("bounded min-plus convolution value span must fit usize");
            right[index * requirements.base + normalized] = MInt998244353::from(1_u32);
        }
    }
    let coefficients = Convolve998244353::convolve(left, right);
    let encoded_len = output_len
        .checked_mul(requirements.base)
        .expect("bounded min-plus convolution encoded length must fit usize");
    let mut result = Vec::with_capacity(output_len);
    for chunk in coefficients[..encoded_len].chunks_exact(requirements.base) {
        let value = if let Some(normalized) = chunk.iter().position(|&value| u32::from(value) != 0)
        {
            requirements.a_min
                + requirements.b_min
                + T::try_from(normalized)
                    .ok()
                    .expect("bounded min-plus convolution value must fit the output type")
        } else {
            T::maximum()
        };
        result.push(value);
    }
    result
}

crates/competitive/src/math/min_plus_convolution/selector.rs (line 191)

fn select_algorithm<T>(
    a_len: usize,
    b_len: usize,
    a_characteristics: &InputCharacteristics<T>,
    b_characteristics: &InputCharacteristics<T>,
) -> Algorithm
where
    T: Signed + TryFrom<usize>,
    T::Unsigned: TryInto<usize>,
{
    let output = a_len.saturating_add(b_len).saturating_sub(1) as u128;
    let mut selected = ((a_len as u128) * (b_len as u128), Algorithm::Naive);
    let mut consider = |work: u128, algorithm| {
        if work < selected.0 {
            selected = (work, algorithm);
        }
    };

    consider(
        // min_plus/sparse: 50% finite inputs are already over 10% faster than
        // the INF-skipping naive scan, while dense pair enumeration loses.
        scaled_work(
            3,
            (a_characteristics.finite_count as u128) * (b_characteristics.finite_count as u128),
        ),
        Algorithm::Sparse,
    );
    if let (Some(a_extrema), Some(b_extrema)) =
        (a_characteristics.extrema, b_characteristics.extrema)
        && let Some(requirements) =
            bounded_requirements_from_extrema(a_len, b_len, a_extrema, b_extrema)
    {
        // min_plus/bounded: small transforms need a wider margin for encoding
        // overhead; at 2^20 and above the NTT wins from a lower work ratio.
        consider(
            scaled_work(
                if requirements.transform_len < 1 << 20 {
                    8
                } else {
                    6
                },
                (requirements.transform_len as u128) * (requirements.transform_len.ilog2() as u128),
            ),
            Algorithm::BoundedNtt,
        );
    }

    if a_characteristics.is_convex && b_characteristics.is_convex {
        consider(output, Algorithm::ConvexMerge);
    } else if a_characteristics.is_convex {
        consider(
            scaled_work(2, output),
            Algorithm::ConvexDivideAndConquerLeft,
        );
    } else if b_characteristics.is_convex {
        consider(
            scaled_work(2, output),
            Algorithm::ConvexDivideAndConquerRight,
        );
    }
    if a_characteristics.is_concave && b_characteristics.is_concave {
        consider(output, Algorithm::ConcaveBoth);
    } else if a_characteristics.is_concave || b_characteristics.is_concave {
        consider(
            scaled_work(8, output.saturating_mul(output.max(1).ilog2() as u128 + 1)),
            if a_characteristics.is_concave {
                Algorithm::ConcaveEnvelopeLeft
            } else {
                Algorithm::ConcaveEnvelopeRight
            },
        );
    }
    let increasing = a_characteristics.is_nondecreasing && b_characteristics.is_nondecreasing;
    let decreasing = a_characteristics.is_nonincreasing && b_characteristics.is_nonincreasing;
    if increasing || decreasing {
        consider(
            scaled_work(
                4,
                a_characteristics
                    .run_count
                    .saturating_mul(b_characteristics.run_count) as u128,
            ) + output,
            if decreasing {
                Algorithm::MonotoneRunsDecreasing
            } else {
                Algorithm::MonotoneRunsIncreasing
            },
        );
    }
    let piecewise = match (
        a_characteristics.finite_count == a_len,
        b_characteristics.finite_count == b_len,
    ) {
        (true, true) if a_characteristics.piece_count < b_characteristics.piece_count => {
            Some((a_characteristics.piece_count, true))
        }
        (true, true) => Some((b_characteristics.piece_count, false)),
        (true, false) => Some((a_characteristics.piece_count, true)),
        (false, true) => Some((b_characteristics.piece_count, false)),
        (false, false) => None,
    };
    if let Some((pieces, structured_is_left)) = piecewise {
        if pieces == 1 {
            consider(
                output,
                if structured_is_left {
                    Algorithm::LinearLeft
                } else {
                    Algorithm::LinearRight
                },
            );
        } else {
            consider(
                scaled_work(4, (pieces as u128).saturating_mul(output)),
                if structured_is_left {
                    Algorithm::PiecewiseLinearLeft
                } else {
                    Algorithm::PiecewiseLinearRight
                },
            );
        }
    }
    selected.1
}