TopCoder problem "ChainOfRectangles" used in SRM 369 (Division II Level One)

Problem Statement


A sequence of rectangles is drawn on a plane that is initially completely white. Each rectangle lies strictly inside the previous one. Each rectangle is completely colored in one of three colors - red, green or blue. The colors do not mix, so when a rectangle is drawn inside another rectangle, the new color replaces any existing color in that same area.

The rectangles are described by the int[]s width and height, and the String color. The width and height of the i-th drawn rectangle are width[i] and height[i], respectively, and its color is the i-th character of color. The characters 'R', 'G' and 'B' represent red, green and blue, respectively.

After all the rectangles are drawn, calculate the total area occupied by red, the total area occupied by green, and the total area occupied by blue. Return the maximum of these three areas.



Parameters:int[], int[], String
Method signature:int getMaximalArea(int[] width, int[] height, String color)
(be sure your method is public)


-You won't be given the information about the exact location of each rectangle, since it's not needed to solve the problem.


-width will contain between 1 and 50 elements, inclusive.
-height will contain the same number of elements as width.
-color will contain the same number of characters as the number of elements in width.
-Each element of width and height will be between 1 and 10000, inclusive.
-Elements of width and height will be in strictly descending order.
-Each character of color will be 'R', 'G' or 'B'.


Returns: 100000000
There is only one 10,000x10,000 rectangle. It's colored red, so the area covered by red is 10,000 * 10,000 = 100,000,000. The areas covered by the other two colors are 0.
{10, 5}
{10, 5}
Returns: 75

Here, the area covered by blue is 5 * 5 = 25 and the area, covered by green is 10 * 10 - 5 * 5 = 75. We return max{75, 25} = 75.

{10, 9}
{8, 7}
Returns: 63

Now, the area covered by green is 17, and the area covered by blue is 63.

{10, 8, 6, 4, 2}
{9, 7, 5, 3, 1}
Returns: 36

Problem url:

Problem stats url:




PabloGilberto , Yarin , Olexiy

Problem categories:

Simple Math