pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/concave.rs (line 178)
161pub fn min_plus_convolution_concave_envelope<T>(a: &[T], b: &[T]) -> Vec<T>
162where
163 T: Signed,
164{
165 let len = output_len(a.len(), b.len());
166 if len == 0 {
167 return Vec::new();
168 }
169 let a_is_concave = !a.iter().any(T::is_maximum) && is_concave(a);
170 let b_is_concave = !b.iter().any(T::is_maximum) && is_concave(b);
171 let (arbitrary, concave) = if b_is_concave {
172 (a, b)
173 } else if a_is_concave {
174 (b, a)
175 } else {
176 panic!("at least one min-plus convolution input must be finite and concave")
177 };
178 concave_envelope(arbitrary, concave)
179}More examples
crates/competitive/src/math/min_plus_convolution/selector.rs (line 325)
293pub fn min_plus_convolution<T>(a: &[T], b: &[T]) -> Vec<T>
294where
295 T: Signed + TryFrom<usize>,
296 T::Unsigned: TryInto<usize>,
297{
298 if (a.len() as u128) * (b.len() as u128) <= SMALL_PAIR_COUNT {
299 return min_plus_convolution_naive(a, b);
300 }
301 let a_characteristics = analyze(a);
302 let distinct_b_characteristics = (!std::ptr::eq(a, b)).then(|| analyze(b));
303 let b_characteristics = distinct_b_characteristics
304 .as_ref()
305 .unwrap_or(&a_characteristics);
306 match select_algorithm(a.len(), b.len(), &a_characteristics, b_characteristics) {
307 Algorithm::Naive => min_plus_convolution_naive(a, b),
308 Algorithm::Sparse => {
309 let a_entries = a[..a_characteristics.finite_prefix_len]
310 .iter()
311 .copied()
312 .enumerate()
313 .chain(a_characteristics.finite_entries.iter().copied());
314 let b_entries = b[..b_characteristics.finite_prefix_len]
315 .iter()
316 .copied()
317 .enumerate()
318 .chain(b_characteristics.finite_entries.iter().copied());
319 sparse(a_entries, b_entries, output_len(a.len(), b.len()))
320 }
321 Algorithm::BoundedNtt => min_plus_convolution_bounded_ntt(a, b),
322 Algorithm::ConvexDivideAndConquerLeft => convex::convex_divide_and_conquer(b, a),
323 Algorithm::ConvexDivideAndConquerRight => convex::convex_divide_and_conquer(a, b),
324 Algorithm::ConvexMerge => convex::convex_merge(a, b),
325 Algorithm::ConcaveEnvelopeLeft => concave::concave_envelope(b, a),
326 Algorithm::ConcaveEnvelopeRight => concave::concave_envelope(a, b),
327 Algorithm::ConcaveBoth => concave::concave_both(a, b),
328 algorithm @ (Algorithm::MonotoneRunsIncreasing | Algorithm::MonotoneRunsDecreasing) => {
329 let increasing = algorithm == Algorithm::MonotoneRunsIncreasing;
330 if let (Some(a_runs), Some(b_runs)) = (
331 &a_characteristics.run_entries,
332 &b_characteristics.run_entries,
333 ) {
334 monotone::monotone_runs_from_entries(a_runs, b_runs, a.len(), b.len(), increasing)
335 } else {
336 monotone::monotone_runs(a, b, increasing)
337 }
338 }
339 Algorithm::LinearLeft => piecewise_linear::linear(b, a),
340 Algorithm::LinearRight => piecewise_linear::linear(a, b),
341 Algorithm::PiecewiseLinearLeft => piecewise_linear::piecewise_linear(b, a),
342 Algorithm::PiecewiseLinearRight => piecewise_linear::piecewise_linear(a, b),
343 }
344}