ChipWire

SRM 131 · 2003-01-30 · by pmadden

Class Name: ChipWire

Return Type: int

Method Name: length

Arg Types: (vector<int>, vector<int>)

Problem Statement

In the design of integrated circuits, we frequently have to connect several points with wires. All wires travel either horizontally (the X direction) or vertically (the Y direction). Write a method to determine the minimum total length of wire needed to connect a group of points; note that we can sometimes reduce the connection length by adding additional points.

For two points at (3, 0) and (5, 7), we would need a total of 9 units of wire to connect them. A wire could travel horizontally for 2 units, turn, and then travel vertically for another 7 units. There are actually many different ways to connect these points using 9 units of wire; an alternate connection could go vertically first.

For three points at (0, 0), (3, -8), and (5, 7), we would need a total of 20 units: a wire from (0, 0) to (3, 0), a wire from (3, 0) to (3, -8), and a wire from (3, 0) to (5, 7). These wires have lengths of 3, 8, and 9, respectively. Note that the point (3, 0) is not one of the three original points. As with the example above, there are several ways for the wire from (3, 0) to (5, 7) to travel, each with a length of 9.

Create a class ChipWire that has a method length that takes a int[] x and a int[] y, which represent the coordinates for a set of points. The method returns an int which is the minimum total length of wire needed to connect the points, using as many additional points as necessary.

Constraints

x will contain between 0 and 5 elements inclusive
y will contain between 0 and 5 elements inclusive
x and y will contain the same number of elements
each element of x will be between -10000 and 10000 inclusive
each element of y will be between -10000 and 10000 inclusive

Examples

{3, 5}
{0,7}
Returns: 9

This is the first example described above; there are many ways to connect these two points, all with a length of 9 units.

{0,3,5}
{0, -8, 7}
Returns: 20

This is the second example; an additional point at (3, 0) is added.

{0}
{4}
Returns: 0

Total length is zero; one point is trivially connected.

{0,3,6,7,8}
{0,-3,10,0,8}
Returns: 22

{0,5000,9000,10000}
{0,-5000, 1000, 1}
Returns: 16000

10)

{10,20,30,40,40}
{20,20,20,20,20}
Returns: 30

The points need not be unique.

11)

{}
{}
Returns: 0

It takes no wire to connect an empty set of points.

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

Coding Area

Language: C++17 · define a public class ChipWire with a public method int length(vector<int> x, vector<int> y) · 32 test cases · 2 s / 256 MB per case