TopCoder problem "PointsOnAxis" used in SRM 159 (Division I Level Three)



Problem Statement

    

There are several distinct points located on the non-negative side of the x-axis. One of those points is at the origin (at 0). For each unique pair of points we write down the distance between them. Note that pairs (a, b) and pairs (b, a) are not unique pairs.

Given a int[] of those distances, return a int[] containing the locations of all points arranged in ascending order. If more than one set of locations is possible then return the set (represented as a int[]) which is lexicographically earliest (see example 1). A int[], n, comes before a int[], m, lexicographically if and only if, for the first element in which they differ, the element of n is smaller. If no set of locations is possible then return an empty int[].

For example: distances = {5, 2, 1, 6, 2, 3, 3, 4, 5, 6, 3, 9, 1, 4, 1}. This in order is {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 9}. The only possible arrangement of points is the following:

  0    1    2    3    4    5    6    7    8    9
--x----|----|----x----x----x----x----|----|----x--

Here 'x' represents a point. Thus the method should return {0, 3, 4, 5, 6, 9}

 

Definition

    
Class:PointsOnAxis
Method:findPoints
Parameters:int[]
Returns:int[]
Method signature:int[] findPoints(int[] distances)
(be sure your method is public)
    
 

Notes

-There cannot be more than one point at the same location, because elements in distances are never 0.
 

Constraints

-the number of elements in distances will be N(N-1)/2, where N is the number of points.
-N will be between 2 and 10 inclusive.
-each element in distances will be between 1 and 1000000 inclusive.
 

Examples

0)
    
{5, 2, 1, 6, 2, 3, 3, 4, 5, 6, 3, 9, 1, 4, 1}
Returns: { 0,  3,  4,  5,  6,  9 }
See above.
1)
    
{20,100,120}
Returns: { 0,  20,  120 }
The possible sets of locations are {0,100,120} and {0,20,120}. Since 20 comes before 100, the method should return {0,20,120}.
2)
    
{1,2,3,4,5,7}
Returns: { 0,  2,  3,  7 }
3)
    
{1,2,4}
Returns: { }
There are no possible sets of locations.
4)
    
{237601, 843904, 56786, 429289, 52254, 83576, 220417,
606303, 180815, 191688, 185347, 154025, 17184, 787118,
414615, 791650, 760328, 623487, 372503, 4532, 26790,
163631, 377035, 345713, 208872, 31322, 168163, 136841}
Returns: { 0,  52254,  56786,  83576,  220417,  237601,  429289,  843904 }
5)
    
{1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 6, 7}
Returns: { 0,  1,  2,  5,  6,  7 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1670

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4600&pm=1670

Writer:

dimkadimon

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, Recursion