14 Feb 10 SRM 461

300P: ColoringRectangle

Greedy algorithm works to this problem:

After we sort the red disks and blue disks by descending order, the final disk placed order would be determined if we choose one of the largest red and blue disks as the left-most disk, where the red disks alternate with the blue disks.

Trick: The disk cannot be used whose diameter is less the height of the rectangle.

500: BuildingCities

Build a graph with at most 50 * 2000 (f[i][j]) vertexes, which means the minimum distance of vertex i which has used j new cities.

Then run shortest path algorithm (SPFA or Dijkstra) on this graph to find the answer.

950: FencingGarden

(more…)

Tags: SRM