fn orient_one_convex<'a, T>(a: &'a [T], b: &'a [T]) -> (&'a [T], &'a [T])where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/convex.rs (line 103)
93pub fn min_plus_convolution_convex_divide_and_conquer<T>(a: &[T], b: &[T]) -> Vec<T>
94where
95 T: Signed,
96{
97 let len = output_len(a.len(), b.len());
98 if len == 0 {
99 return Vec::new();
100 }
101 assert_finite(a);
102 assert_finite(b);
103 let (arbitrary, convex) = orient_one_convex(a, b);
104 convex_divide_and_conquer(arbitrary, convex)
105}
106
107pub(super) fn convex_divide_and_conquer<T>(arbitrary: &[T], convex: &[T]) -> Vec<T>
108where
109 T: Signed,
110{
111 let len = output_len(arbitrary.len(), convex.len());
112 let mut result = vec![T::zero(); len];
113
114 fn solve<T>(
115 arbitrary: &[T],
116 convex: &[T],
117 result: &mut [T],
118 rows: Range<usize>,
119 options: RangeInclusive<usize>,
120 ) where
121 T: Signed,
122 {
123 if rows.is_empty() {
124 return;
125 }
126 let row = (rows.start + rows.end) / 2;
127 let first = (*options.start()).max(row.saturating_sub(convex.len() - 1));
128 let last = (*options.end()).min(row).min(arbitrary.len() - 1);
129 let mut best_col = first;
130 let mut best_value = arbitrary[first] + convex[row - first];
131 for col in first + 1..=last {
132 let value = arbitrary[col] + convex[row - col];
133 if value < best_value {
134 best_value = value;
135 best_col = col;
136 }
137 }
138 result[row] = best_value;
139 solve(
140 arbitrary,
141 convex,
142 result,
143 rows.start..row,
144 *options.start()..=best_col,
145 );
146 solve(
147 arbitrary,
148 convex,
149 result,
150 row + 1..rows.end,
151 best_col..=*options.end(),
152 );
153 }
154
155 solve(
156 arbitrary,
157 convex,
158 &mut result,
159 0..len,
160 0..=arbitrary.len() - 1,
161 );
162 result
163}
164
165#[derive(Clone, Copy, Eq, PartialEq)]
166enum MatrixValue<T> {
167 Finite(T),
168 Infinite,
169}
170
171impl<T> Ord for MatrixValue<T>
172where
173 T: Ord,
174{
175 fn cmp(&self, other: &Self) -> Ordering {
176 match (self, other) {
177 (Self::Finite(left), Self::Finite(right)) => left.cmp(right),
178 (Self::Finite(_), Self::Infinite) => Ordering::Less,
179 (Self::Infinite, Self::Finite(_)) => Ordering::Greater,
180 (Self::Infinite, Self::Infinite) => Ordering::Equal,
181 }
182 }
183}
184
185impl<T> PartialOrd for MatrixValue<T>
186where
187 T: Ord,
188{
189 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
190 Some(self.cmp(other))
191 }
192}
193
194fn smawk<T, F>(rows: usize, cols: usize, cost: &F) -> Vec<usize>
195where
196 T: Ord,
197 F: Fn(usize, usize) -> T,
198{
199 fn solve<T, F>(rows: &[usize], cols: &[usize], cost: &F, argmins: &mut [usize])
200 where
201 T: Ord,
202 F: Fn(usize, usize) -> T,
203 {
204 if rows.is_empty() {
205 return;
206 }
207 let mut reduced = Vec::with_capacity(rows.len().min(cols.len()));
208 for &col in cols {
209 while let Some(&previous) = reduced.last() {
210 let row = rows[reduced.len() - 1];
211 if cost(row, col) <= cost(row, previous) {
212 reduced.pop();
213 } else {
214 break;
215 }
216 }
217 if reduced.len() < rows.len() {
218 reduced.push(col);
219 }
220 }
221 let odd_rows: Vec<_> = rows.iter().copied().skip(1).step_by(2).collect();
222 solve(&odd_rows, &reduced, cost, argmins);
223 let mut lower = 0;
224 for row_position in (0..rows.len()).step_by(2) {
225 let upper = if row_position + 1 < rows.len() {
226 let target = argmins[rows[row_position + 1]];
227 lower
228 + reduced[lower..]
229 .iter()
230 .position(|&col| col == target)
231 .expect("SMAWK odd-row minimum must remain in the reduced columns")
232 } else {
233 reduced.len() - 1
234 };
235 let row = rows[row_position];
236 let mut best = lower;
237 for position in lower + 1..=upper {
238 if cost(row, reduced[position]) <= cost(row, reduced[best]) {
239 best = position;
240 }
241 }
242 argmins[row] = reduced[best];
243 lower = upper;
244 }
245 }
246
247 let row_indices: Vec<_> = (0..rows).collect();
248 let col_indices: Vec<_> = (0..cols).collect();
249 let mut argmins = vec![0; rows];
250 solve(&row_indices, &col_indices, cost, &mut argmins);
251 argmins
252}
253
254/// Computes convolution when one input is convex using SMAWK in `O(n + m)`.
255///
256/// # Panics
257///
258/// Panics unless both inputs are finite and at least one is convex.
259pub fn min_plus_convolution_convex_smawk<T>(a: &[T], b: &[T]) -> Vec<T>
260where
261 T: Signed,
262{
263 let len = output_len(a.len(), b.len());
264 if len == 0 {
265 return Vec::new();
266 }
267 assert_finite(a);
268 assert_finite(b);
269 let (arbitrary, convex) = orient_one_convex(a, b);
270 convex_smawk(arbitrary, convex)
271}