TopCoder Statistics - Problem Statement

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

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
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.
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.
100

93

{68,50,18,52,62}

{27,15,37,45,50}

Returns: 8256
19

20

{1,2,4,8,16}

{1,2,4,8,16}

Returns: 321
40

30

{35}

{25}

Returns: 875
100

100

{100,100}

{100,100}

Returns: 10000
100

100

{100,100,100}

{100,100,100}

Returns: 10000
100

100

{100,100,100,100}

{100,100,100,100}

Returns: 10000
100

100

{100,100,100,100,100}

{100,100,100,100,100}

Returns: 10000
90

100

{80,70,90,80,75}

{15,20,25,20,25}

Returns: 8050
100

90

{15,20,25,20,25}

{80,70,90,80,75}

Returns: 8050
100

100

{49,49,48,48,50}

{49,48,49,48,50}

Returns: 9884
43

27

{32,19,39,29,1}

{12,6,17,11,22}

Returns: 1134
74

23

{72,56,47,49,15}

{3,20,16,3,6}

Returns: 1699
35

23

{6,12,20,16,31}

{14,19,14,5,14}

Returns: 805
90

62

{39,2,54}

{53,32,22}

Returns: 3280
78

60

{7,67,17,32}

{35,45,13,16}

Returns: 3972
28

55

{7,1,28,3}

{42,39,10,8}

Returns: 637
94

48

{53,54,53,66,75}

{30,12,4,44,29}

Returns: 4512
35

51

{8,13,31,26}

{8,27,29,14}

Returns: 1577
83

53

{76,40,12,10,19}

{20,16,21,6,26}

Returns: 2966
9

86

{6,3,5,3,4}

{22,18,74,82,45}

Returns: 773
3

94

{3,1,2,3}

{5,92,7,83}

Returns: 282
42

49

{21,28,20}

{40,18,48}

Returns: 2013
61

32

{30,11,34,35,1}

{9,3,6,10,19}

Returns: 876
22

20

{20,11,8,2,13}

{13,12,19,13,6}

Returns: 439
95

25

{4,14,37,37,76}

{6,11,8,15,21}

Returns: 2265
53

67

{17,1,14,38,43}

{15,9,47,27,10}

Returns: 2378
26

90

{26,24,13,11}

{24,48,41,53}

Returns: 2278
61

78

{51,25,1,46,24}

{6,52,71,21,43}

Returns: 3664
90

93

{17,39,85,18,72}

{53,43,17,49,43}

Returns: 7413
41

62

{12,3,2,41}

{30,48,40,11}

Returns: 1035
88

27

{6,5,60,80,79}

{26,21,9,25,7}

Returns: 2376
24

5

{15,24,8,6,24}

{3,1,4,1,3}

Returns: 120
74

62

{7,17,40,11,64}

{2,14,12,36,51}

Returns: 4295
89

84

{59,12,26,68,29}

{81,14,34,52,72}

Returns: 7476
32

69

{20,12,27,3}

{11,63,14,62}

Returns: 1448
28

98

{26,10,7,28,13}

{30,51,43,8,36}

Returns: 2245
4

22

{4,1,1,4,2}

{11,14,1,17,5}

Returns: 88
7

52

{2,7,6,6,7}

{49,12,28,10,9}

Returns: 364
49

47

{43,21,34,29,26}

{43,46,31,35,14}

Returns: 2303
15

60

{13,9,10}

{46,56,39}

Returns: 892
3

24

{3,1,1,1}

{5,6,3,7}

Returns: 31
42

64

{8,33,16,35,32}

{5,59,48,49,48}

Returns: 2688
40

88

{28,3,12,35,14}

{53,12,50,75,49}

Returns: 3520
31

28

{2,8,4,26,3}

{6,17,7,26,15}

Returns: 822
55

71

{9,25,26,12,52}

{55,46,55,21,48}

Returns: 3905
75

16

{39,53,5,30,59}

{16,14,3,12,8}

Returns: 1200
36

35

{33,26,13,26,25}

{26,24,4,32,10}

Returns: 1260
65

64

{49,38,46}

{27,39,63}

Returns: 4144
46

23

{37,42,45,18,40}

{4,19,4,19,3}

Returns: 1058
15

90

{12,5,8,10,7}

{49,79,74,61,79}

Returns: 1350
54

92

{3,24,26,42,19}

{76,6,65,49,34}

Returns: 4392
75

56

{67,20,34,75,20}

{7,30,16,52,41}

Returns: 4200
32

97

{8,22,7,18,8}

{49,65,6,57,45}

Returns: 2868
41

26

{12,27,37,28,28}

{26,18,26,5,10}

Returns: 1066
11

12

{10,9,2,11,7}

{10,4,4,5,9}

Returns: 132
80

59

{64,33,42,47,16}

{46,53,34,14,2}

Returns: 4720
5

76

{1,4,2,1,3}

{49,14,21,15,61}

Returns: 345
1

1

{1,1}

{1,1}

Returns: 1
1

9

{1,1}

{5,3}

Returns: 8
50

80

{1}

{1}

Returns: 1
100

100

{1,1,1,1,1}

{1,1,1,1,1}

Returns: 5
100

100

{50,40,30,20,10}

{10,20,30,40,50}

Returns: 3500
1

1

{1,1,1,1,1}

{1,1,1,1,1}

Returns: 1
10

10

{10,10,10,10,10}

{2,2,2,2,2}

Returns: 100
10

10

{9,9,9,9,9}

{3,3,3,3,3}

Returns: 95
10

10

{10,9,8,2,1}

{7,1,1,1,2}

Returns: 91
100

92

{ 68, 50, 18, 52, 62 }

{ 27, 15, 37, 45, 50 }

Returns: 8242
100

20

{ 22, 22, 22, 22, 22 }

{ 20, 9, 20, 20, 9 }

Returns: 1716
100

100

{ 20, 21, 99, 44, 38 }

{ 20, 31, 50, 22, 48 }

Returns: 8784
100

100

{ 50, 50, 50, 50, 50 }

{ 50, 50, 50, 50, 50 }

Returns: 10000

Statistics

Problem Statement for "Posters"

Problem Statement

Definition

Constraints

Examples