Connection Status:
Competition Arena > PointsOnAxis

PointsOnAxis

SRM 159 · 2003-08-12 · by dimkadimon

SRM 159 · 2003-08-12 · by dimkadimon · Brute Force, Recursion
Class Name: PointsOnAxis
Return Type: int[]
Method Name: findPoints
Arg Types: (vector<int>)
Problem Statement

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}

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 }

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

Coding Area

Language: C++17 · define a public class PointsOnAxis with a public method vector<int> findPoints(vector<int> distances) · 51 test cases · 2 s / 256 MB per case

Submitting as anonymous