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

 

let Y be the an edge of the rectangular garden which is orthogonal to the wall, and let Y be the edge parallel to the wall.

2X + Y = S (the sum of length of the fence segments)

And we want to the answer of max(X * Y).

We know that max(X * Y) = max(2X * Y) / 2 = S/2 * S/2.

We can divide the segments into two groups, and we enumeration 2^(n/2) to each group, and merge it to find the answer.

We can only cut one segment into two parts, so one of the edges of the rectangle must consist of non-cut segments.

Case 1: one of the orthogonal-to-the-wall edges consists of non-cut segments.

For each combination in a group, if we put it on an edge of orthogonal-to-the-wall ones, we can make sure that the choices of the less of this edge must be leaved to  two combinations in another group as the length of this edge need to be close to S/4.

Case 2: the parallel-to-the-wall edge consists of non-cut segments.

This method is just similar to the method of case 1, but we changed the purpose to find a combination whose length is closed to S/2.

We can use sweeping lines algorithm, and it can run in O(2 ^ 20).

Tags: SRM