Connection Status:
Competition Arena > Supply

Supply

TCO04 Wildcard · 2004-09-07 · by lars2520

TCO04 Wildcard · 2004-09-07 · by lars2520 · Graph Theory
Class Name: Supply
Return Type: int[]
Method Name: newFactory
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

As the manager of a large company, you have a number of factories, and a number of retail stores. Each factory has a location given as (x,y), and some output capacity. Each store also has a location given as (x,y), and a demand specifying the number of products it must receive. Products are produced at the factories, and sent to the stores, and it is important that the stores receive the number of products they ask for. Recently, the factories have not been able to keep up with demand, so you are planning to build a new one. However, you are not sure where the best place to build it is. There is a constant cost of shipping per product, per unit of distance, which we'll call C. Hence, shipping 3 products from (0,0) to (3,4) costs 3*sqrt(3*3+4*4)*C = 15*C. Your new factory will have an output capacity exactly equal to the current difference between the sum of the capacities of all the factories, and the sum of the demands of all the stores. Your task is, assuming an optimal shipping plan, determine the best location to place the new factory.

A String[], factories, will specify the location and capacity of each factory in the format "X Y CAPACITY", where X, Y and CAPACITY are integers. Another String[], stores, will specify the locations and demands of the stores in the format "X Y DEMAND", where X, Y and DEMAND are integers. You should return the optimal factory location as a int[] with two elements, x and y, in that order.

Notes

  • The location of the new factory must have integral coordinates.
  • There may be multiple factories or stores at the same location.
  • The constraints ensure that the return is unique.

Constraints

  • stores will contain between 1 and 10 elements, inclusive.
  • factories will contain between 1 and 4 elements, inclusive.
  • Each X and Y in stores and factories will be between 0 and 10, inclusive.
  • Each CAPACITY and DEMAND will be between 1 and 10, inclusive.
  • There will be no extraneous leading zeros or extra spaces in either input.
  • The total DEMAND will exceed the total CAPACITY.
  • The location providing the minimum cost will be unique, and there will be no other locations that have costs within 1E-3*C of that minimum.
Examples
0)
{"4 0 10"}
{"5 0 7","10 0 8"}
Returns: { 10,  0 }

There are two stores, with demands of 7 and 8. The single existing factory has a capacity of 10, so our new factory must have a capacity of 5. The best place to put the factory is (10,0), the same spot as the store. Then, we have to ship 3 units from the existing factory to (10,0), and 7 units to (5,0). Thus, our total cost is 7*1*C + 3*6*C = 25*C.

1)
{"0 0 1"}
{"5 5 7","10 10 8","10 0 5"}
Returns: { 7,  6 }

Notice that the optimal factory placement is not always at the same location as a store. The total cost here is about 92.485*C.

2)
{"0 0 10","0 10 10","10 0 10","10 10 10"}
{"0 0 8",
 "1 1 8",
 "2 2 4",
 "3 3 9",
 "4 4 9",
 "5 5 8",
 "6 6 1",
 "7 7 5",
 "8 8 2",
 "9 9 10"}
Returns: { 3,  3 }
3)
{"0 0 1"}
{"10 10 10"}
Returns: { 10,  10 }
4)
{"0 0 10","1 1 10","1 0 10","0 1 10"}
{"0 10 9",
 "0 9 10",
 "0 8 10",
 "1 10 10",
 "1 9 10",
 "1 8 10",
 "2 10 10",
 "2 9 10",
 "2 8 10",
 "3 10 10"}
Returns: { 2,  10 }

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

Coding Area

Language: C++17 · define a public class Supply with a public method vector<int> newFactory(vector<string> factories, vector<string> stores) · 45 test cases · 2 s / 256 MB per case

Submitting as anonymous