Connection Status:
Competition Arena > SquaresCovering

SquaresCovering

Member Single Round Match 474 · 2009-12-03 · by K.A.D.R

Member Single Round Match 474 · 2009-12-03 · by K.A.D.R · Dynamic Programming, Geometry, Search
Class Name: SquaresCovering
Return Type: int
Method Name: minCost
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SquaresCovering with a public method int minCost(vector<int> x, vector<int> y, vector<int> cost, vector<int> sides) · 118 test cases · 2 s / 256 MB per case

Submitting as anonymous