Codeforces 674C Levels and Regions - Walkthrough

Partition $N$ elements into exactly $K$ groups. Each group has a cost. Find the lowest total. Direct DP: $O(NK)$ states, $O(N)$ transition = $O(N^2 K)$. Apply Aliens to remove $K$ dimension.

With penalty, we get $O(N^2)$ DP per binary search. Still slow. Apply CHT to reduce transition to $O(N)$. Combined: $O(N \log N)$ per binary search. Total: $O(N \log N \log(\text{answer}))$. Multiple optimizations stack.