Skip to main content

is_convex

competitive::math::min_plus_convolution::convex

Function is_convex 

Source 
pub(super) fn is_convex<T>(values: &[T]) -> bool
where
    T: Signed,
Examples found in repository?
crates/competitive/src/math/min_plus_convolution/convex.rs (line 20)
16fn orient_one_convex<'a, T>(a: &'a [T], b: &'a [T]) -> (&'a [T], &'a [T])
17where
18    T: Signed,
19{
20    if is_convex(b) {
21        (a, b)
22    } else if is_convex(a) {
23        (b, a)
24    } else {
25        panic!("at least one min-plus convolution input must be convex")
26    }
27}
28
29/// Computes convolution of two convex inputs by merging their slope sequences.
30///
31/// The running time is `O(n + m)`.
32///
33/// # Panics
34///
35/// Panics unless both inputs are finite and convex.
36pub fn min_plus_convolution_convex_merge<T>(a: &[T], b: &[T]) -> Vec<T>
37where
38    T: Signed,
39{
40    let len = output_len(a.len(), b.len());
41    if len == 0 {
42        return Vec::new();
43    }
44    assert_finite(a);
45    assert_finite(b);
46    assert!(is_convex(a) && is_convex(b), "both inputs must be convex");
47    convex_merge(a, b)
48}
More examples
Hide additional examples
crates/competitive/src/math/min_plus_convolution/near_convex.rs (line 15)
3fn validate_witness<T>(values: &[T], witness: &[T], delta: T)
4where
5    T: Signed,
6{
7    assert_eq!(
8        values.len(),
9        witness.len(),
10        "near-convex witness must have the same length as its input"
11    );
12    assert_finite(values);
13    assert_finite(witness);
14    assert!(
15        !delta.is_negative() && is_convex(witness),
16        "near-convex delta must be nonnegative and the witness convex"
17    );
18    assert!(
19        values
20            .iter()
21            .zip(witness)
22            .all(|(&value, &lower)| lower <= value && value - lower <= delta),
23        "near-convex witness must satisfy witness[i] <= input[i] <= witness[i] + delta"
24    );
25}