TopCoder problem "AcidRain" used in TCHS SRM 30 (Division I Level Three)

Problem Statement


You are a farmer living in a 2-dimensional world. Your crops look like an infinite line parallel to the x-axis, with the y-coordinate equal to 0. According to the weather forecast, the next rain will be acid, and therefore very harmful to your plants. The rain consists of an infinite number of drops that fall down vertically (parallel to the y-axis). For every x, where x is an arbitrary number (not necessarily an integer), a drop will fall toward the point (x, 0).

To protect your crops, you have built some shields above the ground. Each shield is a line segment parallel to the x-axis, with negligible thickness. If a drop of rain falls on a shield, it will flow to the closest end of the shield and continue falling straight down vertically from that point. If a drop falls exactly in the middle of a shield, the drop will divide into two equal parts that flow to opposite ends of the shield and continue falling from there. If two or more shields have common endpoints they will act as one combined shield. See examples for clarification.

The locations of your existing shields will be given in the three int[]s b, e and y. The endpoints of the i-th shield are located at (b[i], y[i]) and (e[i], y[i]). Define B as the minimum value in b, and E as the maximum value in e. Your task is to build enough additional shields to protect all the crops between (B, 0) and (E, 0), exclusive (that is, all crops whose x-coordinates lie in the open interval (B, E) ). Each shield must be a line segment parallel to the x-axis with non-zero length and a positive y-coordinate. Each shield you build must have integer endpoints and a positive length. Build these new shields in such a way that the sum of their lengths is minimized. Return the sum of the new shields' lengths.



Parameters:int[], int[], int[]
Method signature:int saveHarvest(int[] b, int[] e, int[] y)
(be sure your method is public)


-b will contain between 1 and 25 elements, inclusive.
-b, e and y will contain the same number of elements.
-Each element of b will be between 0 and 10, inclusive.
-Each element of e will be between 0 and 10, inclusive.
-For all i, the i-th element of b will be less than the i-th element of e.
-Each element of y will be between 1 and 100000, inclusive.
-No two shields will overlap, but they can have common endpoints.


Returns: 0
The method should return 0 because all harvest in the interval (1, 2) is already safe.
{1, 2}
{2, 3}
{1, 1}
Returns: 0
These two shields go from (1, 1) to (2, 1) and (2, 1) to (3, 1). Since they share a common endpoint, they act as one combined shield. No additional shields need to be built since all harvest in the interval (1, 3) is safe.
{1, 3}
{100, 100}
Returns: 0
Returns: 1
{1, 0, 3, 5}
{4, 3, 5, 6}
{10, 3, 1000, 8}
Returns: 2

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming