1"""
2Divide and Conquer (D&C) Optimization for DP
3
4D&C Optimization is used to optimize 2D DP from O(n^2 * k) to O(n * k * log n).
5It's applicable when the DP satisfies the quadrangle inequality (monotonicity condition).
6
7Condition: For dp[i][j] = min(dp[i-1][k] + cost(k, j)) for k < j,
8if opt[i][j] <= opt[i][j+1], where opt[i][j] is the optimal k for dp[i][j].
9
10This means the optimal split point is monotonic: as j increases, opt doesn't decrease.
11
12Common applications:
13- Splitting array into k groups to minimize cost
14- Optimal Binary Search Tree
15- Matrix Chain Multiplication variants
16
17Time Complexity: O(k * n * log n) instead of O(k * n^2)
18Space Complexity: O(k * n)
19"""
20
21from typing import List, Callable, Tuple
22import sys
23
24
25def divide_and_conquer_dp(
26 n: int,
27 k: int,
28 cost: Callable[[int, int], float],
29 prev_dp: List[float]
30) -> List[float]:
31 """
32 Compute DP for one layer using divide and conquer optimization.
33
34 Args:
35 n: Number of elements
36 k: Current layer/group number
37 cost: Cost function cost(i, j) for range [i, j]
38 prev_dp: DP values from previous layer
39
40 Returns:
41 List of DP values for current layer
42 """
43 dp = [float('inf')] * (n + 1)
44
45 def solve(l: int, r: int, opt_l: int, opt_r: int) -> None:
46 """
47 Solve for positions [l, r] knowing optimal split is in [opt_l, opt_r].
48
49 Args:
50 l, r: Range of positions to compute
51 opt_l, opt_r: Range where optimal split point must lie
52 """
53 if l > r:
54 return
55
56 mid = (l + r) // 2
57 best_cost = float('inf')
58 best_split = opt_l
59
60 # Find optimal split point for position mid
61 for split in range(opt_l, min(opt_r, mid) + 1):
62 current_cost = prev_dp[split] + cost(split, mid)
63 if current_cost < best_cost:
64 best_cost = current_cost
65 best_split = split
66
67 dp[mid] = best_cost
68
69 # Recursively solve left and right
70 solve(l, mid - 1, opt_l, best_split)
71 solve(mid + 1, r, best_split, opt_r)
72
73 solve(1, n, 0, n)
74 return dp
75
76
77def split_array_min_cost(arr: List[int], k: int) -> Tuple[float, List[List[int]]]:
78 """
79 Split array into k groups to minimize sum of (group_sum)^2.
80
81 Problem: Given array arr, split it into k non-empty contiguous groups
82 such that sum of (sum of each group)^2 is minimized.
83
84 DP: dp[i][j] = minimum cost to split first j elements into i groups
85 Recurrence: dp[i][j] = min(dp[i-1][m] + cost(m, j)) for m in [i-1, j-1]
86 where cost(m, j) = (sum(arr[m+1:j+1]))^2
87
88 This satisfies quadrangle inequality, so D&C optimization applies.
89 """
90 n = len(arr)
91
92 # Precompute prefix sums for O(1) range sum queries
93 prefix = [0] * (n + 1)
94 for i in range(n):
95 prefix[i + 1] = prefix[i] + arr[i]
96
97 def range_sum(i: int, j: int) -> int:
98 """Sum of arr[i:j] (0-indexed, exclusive end)"""
99 return prefix[j] - prefix[i]
100
101 def cost(i: int, j: int) -> float:
102 """Cost of grouping elements from index i+1 to j"""
103 if i >= j:
104 return float('inf')
105 s = range_sum(i, j)
106 return s * s
107
108 # Initialize DP table
109 dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
110 dp[0][0] = 0
111
112 # Track splits for reconstruction
113 split = [[0] * (n + 1) for _ in range(k + 1)]
114
115 # Fill DP table using D&C optimization
116 for i in range(1, k + 1):
117 # Use D&C to compute dp[i][j] for all j
118 prev_layer = dp[i - 1]
119
120 def solve(l: int, r: int, opt_l: int, opt_r: int) -> None:
121 if l > r:
122 return
123
124 mid = (l + r) // 2
125 best_cost = float('inf')
126 best_split = opt_l
127
128 for s in range(opt_l, min(opt_r, mid) + 1):
129 current_cost = prev_layer[s] + cost(s, mid)
130 if current_cost < best_cost:
131 best_cost = current_cost
132 best_split = s
133
134 dp[i][mid] = best_cost
135 split[i][mid] = best_split
136
137 solve(l, mid - 1, opt_l, best_split)
138 solve(mid + 1, r, best_split, opt_r)
139
140 solve(i, n, i - 1, n)
141
142 # Reconstruct solution
143 groups = []
144 pos = n
145 for i in range(k, 0, -1):
146 start = split[i][pos]
147 groups.append(arr[start:pos])
148 pos = start
149 groups.reverse()
150
151 return dp[k][n], groups
152
153
154def optimal_merge_cost(arr: List[int], k: int) -> Tuple[float, List[List[int]]]:
155 """
156 Merge elements with minimum cost, creating k groups.
157
158 Problem: Given costs for each element, merge them into k groups.
159 Cost of a group is the sum of all elements in it.
160 Total cost is sum of all group costs.
161
162 DP: dp[i][j] = minimum cost to merge first j elements into i groups
163 """
164 n = len(arr)
165
166 # Prefix sum
167 prefix = [0] * (n + 1)
168 for i in range(n):
169 prefix[i + 1] = prefix[i] + arr[i]
170
171 def cost(i: int, j: int) -> float:
172 """Cost of merging elements from i+1 to j into one group"""
173 if i >= j:
174 return 0
175 return prefix[j] - prefix[i]
176
177 # Initialize DP
178 dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
179 dp[0][0] = 0
180
181 split = [[0] * (n + 1) for _ in range(k + 1)]
182
183 # Fill DP using D&C optimization
184 for i in range(1, k + 1):
185 prev_layer = dp[i - 1]
186
187 def solve(l: int, r: int, opt_l: int, opt_r: int) -> None:
188 if l > r:
189 return
190
191 mid = (l + r) // 2
192 best_cost = float('inf')
193 best_split = opt_l
194
195 for s in range(opt_l, min(opt_r, mid) + 1):
196 current_cost = prev_layer[s] + cost(s, mid)
197 if current_cost < best_cost:
198 best_cost = current_cost
199 best_split = s
200
201 dp[i][mid] = best_cost
202 split[i][mid] = best_split
203
204 solve(l, mid - 1, opt_l, best_split)
205 solve(mid + 1, r, best_split, opt_r)
206
207 solve(i, n, i - 1, n)
208
209 # Reconstruct
210 groups = []
211 pos = n
212 for i in range(k, 0, -1):
213 start = split[i][pos]
214 groups.append(arr[start:pos])
215 pos = start
216 groups.reverse()
217
218 return dp[k][n], groups
219
220
221def warehouse_allocation(n: int, k: int, positions: List[int], demands: List[int]) -> float:
222 """
223 Warehouse Allocation Problem with D&C Optimization.
224
225 Problem: Place k warehouses to serve n locations.
226 Cost of serving location i from warehouse at j is |positions[i] - positions[j]| * demands[i].
227
228 DP: dp[w][i] = minimum cost to serve first i locations using w warehouses
229 The last warehouse serves some contiguous range [j+1, i].
230
231 This satisfies the monotonicity condition for D&C optimization.
232 """
233 # Precompute costs
234 cost_cache = {}
235
236 def compute_cost(start: int, end: int, warehouse_pos: int) -> float:
237 """Cost to serve locations [start, end) from warehouse at warehouse_pos"""
238 total = 0
239 for i in range(start, end):
240 total += abs(positions[i] - warehouse_pos) * demands[i]
241 return total
242
243 def cost(i: int, j: int) -> float:
244 """
245 Minimum cost to serve locations [i+1, j] with one warehouse.
246 Optimal warehouse position is the weighted median.
247 """
248 if i >= j:
249 return 0
250
251 if (i, j) in cost_cache:
252 return cost_cache[(i, j)]
253
254 # For simplicity, try all positions in range as warehouse location
255 min_cost = float('inf')
256 for w in range(i, j):
257 c = compute_cost(i, j, positions[w])
258 min_cost = min(min_cost, c)
259
260 cost_cache[(i, j)] = min_cost
261 return min_cost
262
263 # DP with D&C optimization
264 dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
265 dp[0][0] = 0
266
267 for w in range(1, k + 1):
268 prev_layer = dp[w - 1]
269
270 def solve(l: int, r: int, opt_l: int, opt_r: int) -> None:
271 if l > r:
272 return
273
274 mid = (l + r) // 2
275 best_cost = float('inf')
276 best_split = opt_l
277
278 for s in range(opt_l, min(opt_r, mid) + 1):
279 current_cost = prev_layer[s] + cost(s, mid)
280 if current_cost < best_cost:
281 best_cost = current_cost
282 best_split = s
283
284 dp[w][mid] = best_cost
285
286 solve(l, mid - 1, opt_l, best_split)
287 solve(mid + 1, r, best_split, opt_r)
288
289 solve(w, n, w - 1, n)
290
291 return dp[k][n]
292
293
294if __name__ == "__main__":
295 print("=== Divide and Conquer DP Optimization Examples ===\n")
296
297 # Test 1: Split Array Min Cost
298 print("Test 1: Split Array to Minimize Sum of Squared Group Sums")
299 arr1 = [1, 2, 3, 4, 5, 6]
300 k1 = 3
301 min_cost1, groups1 = split_array_min_cost(arr1, k1)
302 print(f"Array: {arr1}")
303 print(f"Number of groups: {k1}")
304 print(f"Minimum cost: {min_cost1}")
305 print(f"Groups: {groups1}")
306 print(f"Verification: {sum(sum(g)**2 for g in groups1)}")
307 print()
308
309 # Test 2: Optimal Merge Cost
310 print("Test 2: Optimal Merge Cost")
311 arr2 = [3, 5, 8, 2, 4, 7, 1]
312 k2 = 4
313 min_cost2, groups2 = optimal_merge_cost(arr2, k2)
314 print(f"Array: {arr2}")
315 print(f"Number of groups: {k2}")
316 print(f"Minimum total cost: {min_cost2}")
317 print(f"Groups: {groups2}")
318 print(f"Group costs: {[sum(g) for g in groups2]}")
319 print()
320
321 # Test 3: Warehouse Allocation
322 print("Test 3: Warehouse Allocation Problem")
323 n3 = 6
324 k3 = 2
325 positions3 = [1, 3, 5, 7, 9, 11]
326 demands3 = [10, 5, 8, 12, 6, 9]
327 min_cost3 = warehouse_allocation(n3, k3, positions3, demands3)
328 print(f"Locations: {n3}")
329 print(f"Warehouses: {k3}")
330 print(f"Positions: {positions3}")
331 print(f"Demands: {demands3}")
332 print(f"Minimum cost: {min_cost3}")
333 print()
334
335 # Test 4: Large Array Performance Test
336 print("Test 4: Performance on Larger Array")
337 import time
338
339 arr4 = list(range(1, 101))
340 k4 = 10
341 start_time = time.time()
342 min_cost4, groups4 = split_array_min_cost(arr4, k4)
343 end_time = time.time()
344
345 print(f"Array size: {len(arr4)}")
346 print(f"Number of groups: {k4}")
347 print(f"Minimum cost: {min_cost4}")
348 print(f"Time taken: {end_time - start_time:.4f} seconds")
349 print(f"Group sizes: {[len(g) for g in groups4]}")
350 print()
351
352 # Test 5: Edge Cases
353 print("Test 5: Edge Cases")
354
355 # Single group
356 arr5a = [1, 2, 3, 4, 5]
357 k5a = 1
358 cost5a, groups5a = split_array_min_cost(arr5a, k5a)
359 print(f"Single group: {arr5a}, k={k5a}")
360 print(f"Cost: {cost5a}, Groups: {groups5a}")
361
362 # Each element in its own group
363 arr5b = [1, 2, 3]
364 k5b = 3
365 cost5b, groups5b = split_array_min_cost(arr5b, k5b)
366 print(f"Each in own group: {arr5b}, k={k5b}")
367 print(f"Cost: {cost5b}, Groups: {groups5b}")
368 print()
369
370 print("=== Complexity Analysis ===")
371 print("Without D&C Optimization: O(k * n^2)")
372 print("With D&C Optimization: O(k * n * log n)")
373 print()
374 print("Speedup factor for n=1000, k=10:")
375 print(f" Without: ~{10 * 1000 * 1000:,} operations")
376 print(f" With: ~{10 * 1000 * 10:,} operations")
377 print(f" Speedup: ~{100}x faster")