| This problem takes its inspiration in theoretical physics. If you are interested in more details, we welcome you to check the following introductive text.
There are N points in a 10-dimensional space. This means that each point has exactly 10 coordinates. Let the j-th coordinate of i-th point be X[i][j]. (All indices in this problem are 0-based.) N will be chosen between 100 and 2000, inclusive. (In this and next sentences "to choose" means "to choose uniformly and independently, at random".) Each coordinate of each point will be chosen between 0 and 1000, inclusive. For each point i, a real number p[i] between 0.2 and 1.0 will be chosen. Then, for each j, the j-th coordinate of i-th point will be hidden with probability p[i] (and thus it will be known to you with probability 1 - p[i]). The information about coordinates will be provided as String[] **coords**, where i-th element describes i-th point and is formatted "X'[i][0] X'[i][1] ... X'[i][9]" (quotes for clarity). Here X'[i][j] = X[i][j] if the j-th coordinate of i-th point is known to and X'[i][j] = -1 if it is hidden.
You will also be given some additional information about the points:
- Let
`dist`(i, j) be the Euclidean distance between points i and j (see notes for exact formula). We define `rank`[i][j] as the number of different points k such that `dist`(i, k) < `dist`(i, j). In this definition k is allowed to be equal to i. For example, `rank`[i][i] = 0. If point j is the nearest one to point i (and j does not coincide with i), then `rank`[i][j] = 1, and so on. You will be given information about all ranks as String[] **ranks**. The i-th element of **ranks** will be formatted "`rank`[i][0] `rank`[i][1] ... `rank`[i][N-1]" (quotes for clarity).
- You will be given int[]
**minDist**, where **minDist**[i] is the square of Euclidean distance from point i to the closest other point. More formally, **minDist**[i] = min{`dist`(i, j)^2 | 0 <= j < N, j != i}.
- You will be given int[]
**maxDist**, where **maxDist**[i] is the square of Euclidean distance from point i to the farthest other point. That is, **maxDist**[i] = max{`dist`(i, j)^2 | 0 <= j < N}.
Your task is to implement a method `predictCoordinates`. Given **coords**, **ranks**, **minDist** and **maxDist**, it should predict the coordinates of all points as precisely as possible. Let PX[i][j] be the predicted j-th coordinate of the i-th point. The return value must be a String[] containing exactly N elements. The i-th element of the return must be formatted "PX[i][0] PX[i][1] ... PX[i][9]" (quotes for clarity).
Scoring works as follows. For each test case, we will calculate your raw and normalized scores. If you exceeded time or memory limit, your solution crashed, return value is improperly formatted or at least one of the predicted coordinates is not in 0..1000, then your raw score is -1.0 and your normalized score is 0. Otherwise, the raw score for a test case will be the arithmetic average of Euclidean distances between X[i] (real location of i-th point) and PX[i] (predicted location of i-th point), for all i between 0 and N-1, inclusive. Your normalized score for each provisional and final test case will be 1000 * (BEST + 1) / (YOUR + 1), where YOUR is your raw score for this test case and BEST is the lowest non-negative raw score of all competitors for this test case. Finally, your total score is equal to the sum of normalized scores on all test cases.
The problem comes with an offline tester. You can use it to test your solution locally. |