competitive/math/min_plus_convolution/
monotone.rs

1use super::{Signed, assert_finite, output_len};
2
3fn run_entries<T>(values: &[T]) -> Vec<(usize, T)>
4where
5    T: Signed,
6{
7    let mut result = Vec::new();
8    for (start, &value) in values.iter().enumerate() {
9        if result.last().is_none_or(|&(_, previous)| previous != value) {
10            result.push((start, value));
11        }
12    }
13    result
14}
15
16/// Computes convolution of same-direction monotone inputs from equal-value runs.
17///
18/// If the inputs contain `r_a` and `r_b` runs, the running time is
19/// `O(r_a * r_b + n + m)`.
20///
21/// # Panics
22///
23/// Panics unless both inputs are finite and monotone in the same direction.
24pub fn min_plus_convolution_monotone_runs<T>(a: &[T], b: &[T]) -> Vec<T>
25where
26    T: Signed,
27{
28    let len = output_len(a.len(), b.len());
29    if len == 0 {
30        return Vec::new();
31    }
32    assert_finite(a);
33    assert_finite(b);
34    let increasing = if a.windows(2).all(|window| window[0] >= window[1])
35        && b.windows(2).all(|window| window[0] >= window[1])
36    {
37        false
38    } else if a.windows(2).all(|window| window[0] <= window[1])
39        && b.windows(2).all(|window| window[0] <= window[1])
40    {
41        true
42    } else {
43        panic!("both inputs must be monotone in the same direction")
44    };
45    monotone_runs(a, b, increasing)
46}
47
48pub(super) fn monotone_runs<T>(a: &[T], b: &[T], increasing: bool) -> Vec<T>
49where
50    T: Signed,
51{
52    monotone_runs_from_entries(
53        &run_entries(a),
54        &run_entries(b),
55        a.len(),
56        b.len(),
57        increasing,
58    )
59}
60
61pub(super) fn monotone_runs_from_entries<T>(
62    a_runs: &[(usize, T)],
63    b_runs: &[(usize, T)],
64    a_len: usize,
65    b_len: usize,
66    increasing: bool,
67) -> Vec<T>
68where
69    T: Signed,
70{
71    let normalize = |runs: &[(usize, T)], len: usize| {
72        if increasing {
73            runs.iter()
74                .enumerate()
75                .rev()
76                .map(|(index, &(_, value))| {
77                    (
78                        len - runs.get(index + 1).map_or(len, |&(start, _)| start),
79                        value,
80                    )
81                })
82                .collect()
83        } else {
84            runs.to_vec()
85        }
86    };
87    let a_runs = normalize(a_runs, a_len);
88    let b_runs = normalize(b_runs, b_len);
89    let len = output_len(a_len, b_len);
90    let mut result = vec![T::maximum(); len];
91    for &(left_start, left_value) in &a_runs {
92        for &(right_start, right_value) in &b_runs {
93            let output = left_start + right_start;
94            result[output] = result[output].min(left_value + right_value);
95        }
96    }
97    for output in 1..len {
98        result[output] = result[output].min(result[output - 1]);
99    }
100    if increasing {
101        result.reverse();
102    }
103    result
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109    use crate::{math::min_plus_convolution::min_plus_convolution_naive, tools::Xorshift};
110
111    #[test]
112    fn test_monotone_runs() {
113        let mut rng = Xorshift::default();
114        for _ in 0..64 {
115            let a_len = rng.random(0..=11);
116            let b_len = rng.random(0..=11);
117            let mut a = Vec::with_capacity(a_len);
118            let mut b = Vec::with_capacity(b_len);
119            let increasing = rng.random(0_u64..2) == 0;
120            let mut value = rng.random(-20_i64..=20);
121            for _ in 0..a_len {
122                a.push(value);
123                let difference = rng.random(0_i64..3);
124                value += if increasing { difference } else { -difference };
125            }
126            value = rng.random(-20_i64..=20);
127            for _ in 0..b_len {
128                b.push(value);
129                let difference = rng.random(0_i64..3);
130                value += if increasing { difference } else { -difference };
131            }
132            assert_eq!(
133                min_plus_convolution_monotone_runs(&a, &b),
134                min_plus_convolution_naive(&a, &b)
135            );
136        }
137    }
138}
competitive/math/min_plus_convolution/monotone.rs

competitive/math/min_plus_convolution/
monotone.rs
