Connection Status:
Competition Arena > Reconstruct

Reconstruct

SRM 218 · 2004-11-04 · by lars2520

SRM 218 · 2004-11-04 · by lars2520 · Brute Force, Recursion
Class Name: Reconstruct
Return Type: String[]
Method Name: findPoints
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You have collected a number of data points, each consisting of an ordered triple of three integers. Unfortunately, you've lost the original data. However, before you lost the data, you calculated the Euclidean distances between each pair of points and recorded the square of each distance. Given the distances as a String[], dists, you are to find the original data points, if possible. Each element of dists will be formatted as a single space delimited list of integers. The ith integer of the jth element of dists will represent the square of the distance between the ith and jth points.

You should return a String[], the ith element of which represents the the ith data point as 3 single space delimited integers. Since distances are preserved under translation and rotation, the first element of the return should always be "0 0 0", and the second element should consist of 3 non-negative integers sorted in non-descending order. If there are multiple such returns, pick the one that is lexicographically first. For the purposes of this problem, one return is before another lexicographically if it has a lower integer in the first location for which the two differ. In other words, find the first element of the return that is different between the two, and then find the first integer in the two elements that differ, and compare them. If there is no set of points that could generate the given distances, return an empty String[].

Constraints

  • dists will contain between 1 and 20 elements, inclusive.
  • Each element of dists will contain between 1 and 50 characters, inclusive.
  • Each number in dists will be an integer between 0 and 1000, inclusive, with no extra leading zeros.
  • Each element of dists will contain the same number of integers as there are elements of dists, separated by single spaces.
  • In dists, integer i of element j will equal integer j of element i.
  • In dists, integer i of element i will equal 0.
Examples
0)
{"0 1","1 0"}
Returns: { "0 0 0",  "0 0 1" }
1)
{"0 2 2","2 0 2","2 2 0"}
Returns: { "0 0 0",  "0 1 1",  "-1 0 1" }
2)
{"0 33 25","33 0 84","25 84 0"}
Returns: { "0 0 0",  "1 4 4",  "3 -4 0" }
3)
{"0 15","15 0"}
Returns: { }

There are no three integers the sum of whose squares is 15.

4)
{"0 233 145 89 74 19 116 70 54 149 149 122 29 121 81 166 155 66 89 98","233 0 480 414 173 286 441 251 413 490 698 245 146 622 580 449 290 309 164 149","145 480 0 158 149 134 433 155 69 186 130 341 258 134 116 41 218 21 308 117","89 414 158 0 65 26 333 285 25 8 242 419 104 242 102 85 434 115 350 131","74 173 149 65 0 45 362 194 76 89 339 306 57 315 209 84 297 74 225 18","19 286 134 26 45 0 195 149 21 62 178 237 38 162 74 109 264 69 186 89","116 441 433 333 362 195 0 154 270 441 209 98 161 165 185 534 227 314 113 410","70 251 155 285 194 149 154 0 174 377 153 38 145 113 171 266 17 86 35 154","54 413 69 25 76 21 270 174 0 49 123 310 113 123 41 56 289 46 265 110","149 490 186 8 89 62 441 377 49 0 306 539 160 314 146 85 542 155 458 163","149 698 130 242 339 178 209 153 123 306 0 261 306 4 34 251 222 141 282 345","122 245 341 419 306 237 98 38 310 539 261 0 171 201 281 474 45 224 9 276","29 146 258 104 57 38 161 145 113 160 306 171 0 266 186 229 246 139 114 99","121 622 134 242 315 162 165 113 123 314 4 201 266 0 38 259 174 129 222 317","81 580 116 102 209 74 185 171 41 146 34 281 186 38 0 165 278 105 272 249","166 449 41 85 84 109 534 266 56 85 251 474 229 259 165 0 369 50 405 82","155 290 218 434 297 264 227 17 289 542 222 45 246 174 278 369 0 149 54 225","66 309 21 115 74 69 314 86 46 155 141 224 139 129 105 50 149 0 185 52","89 164 308 350 225 186 113 35 265 458 282 9 114 222 272 405 54 185 0 201","98 149 117 131 18 89 410 154 110 163 345 276 99 317 249 82 225 52 201 0"}
Returns: { "0 0 0",  "5 8 12",  "9 0 -8",  "-2 6 -7",  "3 8 -1",  "-1 3 -3",  "-6 -8 4",  "6 -5 3",  "1 2 -7",  "-2 8 -9",  "2 -9 -8",  "3 -7 8",  "-2 4 3",  "2 -9 -6",  "-1 -4 -8",  "7 6 -9",  "9 -7 5",  "7 1 -4",  "3 -4 8",  "7 7 0" }

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

Coding Area

Language: C++17 · define a public class Reconstruct with a public method vector<string> findPoints(vector<string> dists) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous