Egalitarianism2
SRM 611 · 2013-12-22 · by ivan_metelsky
SRM 611 · 2013-12-22 · by ivan_metelsky · Graph Theory, Math
Problem Statement
Problem Statement
There are N cities in the plane.
For convenience, the cities are numbered 0 through N-1.
For each i, the city number i is represented by the point at coordinates (x[i], y[i]).
The king wants to connect all cities by building exactly N-1 roads. Each road must connect two cities. All roads must be straight. Hence, the length of a road is equal to the Euclidean distance between the two points it connects. The roads are allowed to cross and even overlap arbitrarily. (You cannot change roads at a crossing. Hence, the N-1 roads connect all cities if and only if their topology is a tree.)
The king does not care about roads being short. However, people often complain if some roads are short and others are long. Therefore, the king would like to select a set of N-1 roads such that they connect all cities, and the standard deviation of the sequence of their lengths is as small as possible.
Formally, given a sequence of real numbers (a1,...,aS) we can compute their standard deviation as follows. First, let b = ((a1+...+aS) / S) be their mean - i.e., the average of our numbers. Next, let c = (sum_i (b-ai)^2) be the sum of squared distances of all values from the mean. Finally, the standard deviation of our sequence is computed as sqrt(c/S). Note that our sequence will contain exactly N-1 road lengths, hence in the above formulas S will be equal to N-1.
You are given theint[] s x and y with N elements each: the coordinates of the N points.
Compute and return the smallest possible value of the standard deviation of lengths of selected roads.
The king wants to connect all cities by building exactly N-1 roads. Each road must connect two cities. All roads must be straight. Hence, the length of a road is equal to the Euclidean distance between the two points it connects. The roads are allowed to cross and even overlap arbitrarily. (You cannot change roads at a crossing. Hence, the N-1 roads connect all cities if and only if their topology is a tree.)
The king does not care about roads being short. However, people often complain if some roads are short and others are long. Therefore, the king would like to select a set of N-1 roads such that they connect all cities, and the standard deviation of the sequence of their lengths is as small as possible.
Formally, given a sequence of real numbers (a1,...,aS) we can compute their standard deviation as follows. First, let b = ((a1+...+aS) / S) be their mean - i.e., the average of our numbers. Next, let c = (sum_i (b-ai)^2) be the sum of squared distances of all values from the mean. Finally, the standard deviation of our sequence is computed as sqrt(c/S). Note that our sequence will contain exactly N-1 road lengths, hence in the above formulas S will be equal to N-1.
You are given the
Notes
- The Euclidean distance between points (a,b) and (c,d) equals sqrt( (a-c)^2 + (b-d)^2 ).
- Your return value must have an absolute or a relative error of less than 1e-9.
Constraints
- x will contain between 3 and 20 elements, inclusive.
- x and y will contain same number of elements.
- Each element in x will be between -1,000,000 and 1,000,000, inclusive.
- Each element in y will be between -1,000,000 and 1,000,000, inclusive.
- No two cities will be located in the same place.
Examples
0)
{0,0,1,1}
{0,1,0,1}
Returns: 0.0
We can build these roads: 0-1, 1-3, 3-2.
1)
{0,0,0}
{0,9,10}
Returns: 0.5
The optimal solution is to build the roads with lengths 9 and 10. (Note that these two roads overlap, but that is allowed.)
2)
{12,46,81,56}
{0,45,2,67}
Returns: 6.102799971320928
3)
{0,0,0,0,0,0,0}
{0,2,3,9,10,15,16}
Returns: 0.9428090415820632
4)
{167053, 536770, -590401, 507047, 350178, -274523, -584679, -766795, -664177, 267757, -291856, -765547, 604801, -682922, -404590, 468001, 607925, 503849, -499699, -798637}
{-12396, -66098, -56843, 20270, 81510, -23294, 10423, 24007, -24343, -21587, -6318, -7396, -68622, 56304, -85680, -14890, -38373, -25477, -38240, 11736}
Returns: 40056.95946451828
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Egalitarianism2 with a public method double minStdev(vector<int> x, vector<int> y) · 111 test cases · 2 s / 256 MB per case