TopCoder problem "SquaresCovering" used in Member Single Round Match 474 (Division II Level Three)



Problem Statement

    

Little Dazdraperma likes drawing a lot. She drew some red points on the plane. The coordinates of these points are given in int[] x and int[] y, where the i-th point is located at (x[i], y[i]). Her friend sells blue squares of different types. A square of type i has sides of length sides[i] and a cost of cost[i] assigned to it. She thinks that her picture will be more attractive if all the red points would be covered by squares (possibly overlapping). She decided that the sides of all the squares must be parallel to either the x or y axis. The point A is considered to be covered by a square if it lies inside it or on its boundary.



Now she wonders what is the smallest amount of money she has to spend to cover all red points with blue squares. Note that there is an unlimited amount of squares of each type and if Dazdraperma wants to buy several squares of the same type, she must pay the corresponding cost for each single square. Return the minimum cost for covering all red points with the given squares.

 

Definition

    
Class:SquaresCovering
Method:minCost
Parameters:int[], int[], int[], int[]
Returns:int
Method signature:int minCost(int[] x, int[] y, int[] cost, int[] sides)
(be sure your method is public)
    
 

Constraints

-x will contain between 1 and 16 elements, inclusive.
-y will contain the same number of elements as x.
-Each element of x will be between 0 and 1000000000 (109), inclusive.
-Each element of y will be between 0 and 1000000000 (109), inclusive.
-cost will contain between 1 and 50 elements, inclusive.
-sides will contain the same number of elements as cost.
-Each element of sides will be between 1 and 1000000000 (109), inclusive.
-Each element of cost will be between 1 and 100000000 (108), inclusive.
 

Examples

0)
    
{1,100}
{1,100}
{3,1}
{100,1}
Returns: 2
Here it is better to cover each point with its own square of size 1.
1)
    
{1,100}
{1,100}
{1,1}
{100,1}
Returns: 1
Here it is better to cover both points with one square of size 100.
2)
    
{0,100,201,300}
{0,0,1,0}
{6,100,10}
{1,100,99}
Returns: 22
In this test case it is better to cover points 0 and 1 with their own squares of size 1 and points 2 and 3 with one square of size 99.
3)
    
{41,6334,19169,11478,26962,5705,23281,41}
{18467,26500,15724,29358,24464,28145,16827,18467}
{292,11943,5437,14605,154,12383,18717,19896,21727,11539,19913,26300,9895,23812,30334,4665,7712,6869,27645,32758}
{9962,2996,4828,32392,33,293,17422,19719,5448,14772,1870,25668,17036,28704,31323,17674,15142,28254,25548,32663}
Returns: 738
Note that red points can coincide.
4)
    
{41,6334,9169,1478,6962,5705,3281}
{8467,6500,5724,9358,4464,8145,6827}
{92,43,37,15,54,83,17,96,27,39,13,100,95,12,34,65,12,69,45,58}
{962,996,828,392,903,293,422,719,448,772,870,668,36,704,323,674,142,254,548,663}
Returns: 84

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14185&pm=10960

Writer:

K.A.D.R

Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp , maksay

Problem categories:

Dynamic Programming, Geometry, Search