Controls
Min Segments: 3
Problem
Bearcu has a circular array of N jewels with spiritual values. Divide it into minimal segments where each segment's sum ≤ K.
Key techniques: Array duplication, prefix sums, binary search, greedy segmentation, local search optimization.
Example: N=8, K=5, [2,2,2,1,3,1,2,1] → 3 segments
Phase 1: Array Duplication
Circular array is duplicated to handle segments that wrap around.
Original Circular Array
2
1
2
2
2
3
1
4
↻
Duplicated Linear Array
Original (1-8)
2
1
2
2
2
3
1
4
3
5
1
6
2
7
1
8
|
Duplicated (9-16)
2
9
2
10
2
11
1
12
3
13
1
14
2
15
1
16
Why Duplicate?
- Segments can wrap from index N back to 1
- By duplicating, we treat all segments as linear in a single array
- Example: segment [N-1, N, 1] becomes [N-1, N, N+1]