Dynamic Programming21 sections · 916 units
Open in Course

IOI Aliens - Preprocessing

Simplifying the problem

First, sort points by xx-coordinate. Then remove dominated points: if point A's required square completely contains point B's required square, remove B. Point B will be covered whenever A is. After cleanup, the remaining points have a special structure: their required squares are nested in a specific way.

If i<ji < j in sorted order, point ii's required square starts at a smaller xx-coordinate. The problem becomes: partition the cleaned points into segments, where each segment is covered by one square photo. Find the lowest total area, accounting for overlap between adjacent photos.