TopCoder problem "Posters" used in SRM 157 (Division I Level Three)



Problem Statement

    

Yarin likes to decorate his walls with posters. Lately, he has had some trouble deciding where on the wall to put the posters so the total area of the wall that is covered with posters is maximized. The posters can of course not be cut into pieces, nor rotated, nor placed so they don't fit completely on the wall. They may overlap however (see example 0).

Create a class Posters containing the method maxCover which takes as input an int width and an int height, the width and height of the wall, and a int[] pWidth and a int[] pHeight, the width and height of each poster. Elements i in pWidth and pHeight are the width and height, respectively, of poster i. The method should return an int, the maximum area of the wall that can be covered with posters.

 

Definition

    
Class:Posters
Method:maxCover
Parameters:int, int, int[], int[]
Returns:int
Method signature:int maxCover(int width, int height, int[] pWidth, int[] pHeight)
(be sure your method is public)
    
 

Constraints

-width will be between 1 and 100, inclusive.
-height will be between 1 and 100, inclusive.
-pWidth will contain between 1 and 5 elements, inclusive.
-pHeight will contain between 1 and 5 elements, inclusive.
-pWidth and pHeight will contain the same number of elements.
-Each element in pWidth will be between 1 and width, inclusive.
-Each element in pHeight will be between 1 and height, inclusive.
 

Examples

0)
    
10
10
{7,4,1,8}
{3,5,3,4}
Returns: 74

The posters can be placed like this:

AAAAAAA...
AAAAAAABBB
AAAAAAABBB
......BBBB
......BBBB
......BBBB
DDDDDDDD..
DDDDDDDD.C
DDDDDDDD.C
DDDDDDDD.C
1)
    
90
80
{64,51}
{42,51}
Returns: 4964

With only two posters, the optimal result is always reached by putting the posters in opposite corners of the wall.

2)
    
8
6
{6,6,2,4,2}
{2,2,4,2,4}
Returns: 48
Here one poster must be surrounded by the other posters in order to get the best result.
3)
    
100
93
{68,50,18,52,62}
{27,15,37,45,50}
Returns: 8256
4)
    
19
20
{1,2,4,8,16}
{1,2,4,8,16}
Returns: 321
5)
    
40
30
{35}
{25}
Returns: 875

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1684

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4590&pm=1684

Writer:

Yarin

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, Geometry