IOI Aliens - Walkthrough

Cover points with at most $K$ squares. Find the lowest total area. The iconic problem that named the trick. Preprocess: reduce to covering intervals.

Some intervals dominate others. Reduce to $O(N)$ needed intervals. DP: $dp[i]$ = min cost to cover first $i$ intervals. Transition: pick where last square starts. Apply CHT. Aliens trick: penalize each square by $\lambda$. Binary search to use exactly $K$. Total: $O(N \log N \log(\text{cost}))$.