TopCoder problem "ConstructionFromMatches" used in TCCC07 Qual 1 (Division I Level Three)



Problem Statement

    

There is a shop in your city, in which matches of different integer thicknesses from 1 to N, inclusive, are sold. All matches in the shop have the same length. The (i-1)-th element of cost is the cost of one match with thickness i.

You wish to buy some matches and use them to construct a 2xM rectangle. For example, if M=5, then the rectangle will look as follows (characters '|' and '-' correspond to matches):

 _ _ _ _ _
| | | | | |
 _ _ _ _ _
| | | | | |
 _ _ _ _ _

You are given two int[]s, top and bottom, each containing exactly M elements. top and bottom contain the required thicknesses of the squares in the top and bottom rows of the rectangle, respectively, from left to right. The thickness of a square is the sum of the thicknesses of its four sides. Return the minimum total cost of matches needed to construct the required rectangle, or -1 if it's not possible.

 

Definition

    
Class:ConstructionFromMatches
Method:minimumCost
Parameters:int[], int[], int[]
Returns:int
Method signature:int minimumCost(int[] cost, int[] top, int[] bottom)
(be sure your method is public)
    
 

Constraints

-cost will contain between 1 and 12 elements, inclusive.
-Each element of cost will be between 1 and 100000, inclusive.
-Elements of cost will be in strictly ascending order.
-top will contain between 1 and 50 elements, inclusive.
-bottom will contain the same number of elements as top.
-Each element of top and bottom will be between 4 and 48, inclusive.
 

Examples

0)
    
{1, 2}
{7}
{5}
Returns: 10

The cheapest solution contains 3 matches of thickness 2 and 4 matches of thickness 1. It may look as follows (each digit d denotes a single match of thickness d):

 1
2 2
 2
1 1
 1
1)
    
{1}
{5}
{5}
Returns: -1
Obviously we can't get a square with thickness 5 using only matches of thickness 1.
2)
    
{1, 5, 9}
{7, 10}
{8, 9}
Returns: 56

One of the optimal solutions looks as follows (each digit d denotes a single match of thickness d):

 1 3
1 3 1
 2 3
1 3 1
 2 2
3)
    
{1, 3, 4, 7, 9}
{13, 14, 13, 11, 9, 7, 11, 8, 8, 10}
{18, 14, 17, 10, 8, 4, 8, 13, 14, 13}
Returns: 194

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10888&pm=8146

Writer:

ivan_metelsky

Testers:

PabloGilberto , vorthys , Olexiy

Problem categories:

Dynamic Programming