Connection Status:
Competition Arena > KingdomXCitiesandVillages

KingdomXCitiesandVillages

Member SRM 503 · 2010-11-01 · by dolphinigle

Member SRM 503 · 2010-11-01 · by dolphinigle · Math, Sorting
Class Name: KingdomXCitiesandVillages
Return Type: double
Method Name: determineLength
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

The Grid Kingdom lies on a plane. There are N cities and M villages in the Grid Kingdom, each is a point on the plane. The i-th city is located at coordinates (cityX[i], cityY[i]) and the i-th village is located at coordinates (villageX[i], villageY[i]). Initially, there are no roads in the kingdom, so no village is initially connected to any city.

To improve this, the king has ordered that each village shall be connected to a city by a system of roads. The scheme for building the roads is as follows:

While there exists a village that is not connected to any city:
  1. Pick one unconnected village (each has an equal probability of being chosen), call it V.
  2. Select a point, X, which is nearest to V, in terms of Euclidean Distance, and is either a city or a village-that-is-already-connected-to-a-city. If multiple such points are equally near, pick any of the nearest points with equal probability.
  3. Construct a road from V to X. The length of this road is equal to the Euclidean Distance between points V and X. V is now connected to a city.
Return the expected total length of all the roads that will be constructed after all villages are connected to a city.

Notes

  • The Euclidean distance between two points (X1, Y1) and (X2, Y2) is defined as the square root of ((X1-X2)^2 + (Y1-Y2)^2).
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • cityX will contain between 1 and 50 elements, inclusive.
  • cityY will contain the same number of elements as cityX.
  • Each element in cityX and cityY will be between 0 and 1,000,000, inclusive.
  • villageX will contain between 1 and 50 elements, inclusive.
  • villageY will contain the same number of elements as villageX.
  • Each element in villageX and villageY will be between 0 and 1,000,000, inclusive.
  • The location of all cities will be distinct.
  • The location of all villages will be distinct.
  • There will be no pair of city and village that is located at the same location.
Examples
0)
{3}
{0}
{3,3}
{2,1}
Returns: 2.5

If village 0 is chosen first, the total length is 3. Otherwise it's 2. The expected length is their average.

1)
{1,4,7,10}
{5,5,5,5}
{1,4,7,10}
{4,4,4,4}
Returns: 4.0

This time the order doesn't matter, each village will be connected to the city closest to it.

2)
{1,2,3}
{4,4,4}
{4,5,6}
{4,4,4}
Returns: 4.166666666666667
3)
{0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8}
{1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,10,10,10,10,10}
{1}
{1000}
Returns: 990.0005050503762
4)
{1000000}
{1000000}
{0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8}
{1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,10,10,10,10,10}
Returns: 1414284.9775396662

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

Coding Area

Language: C++17 · define a public class KingdomXCitiesandVillages with a public method double determineLength(vector<int> cityX, vector<int> cityY, vector<int> villageX, vector<int> villageY) · 183 test cases · 2 s / 256 MB per case

Submitting as anonymous