Get Time
long_comps_topcoder  Problem Statement
Contest: TCAP 2012 TCAP 2012
Problem: TheUniverseUnravels

Problem Statement


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.



Parameters:String[], String[], int[], int[]
Method signature:String[] predictCoordinates(String[] coords, String[] ranks, int[] minDist, int[] maxDist)
(be sure your method is public)


-Let (A[0], A[1], ..., A[9]) and (B[0], B[1], ..., B[9]) be two points in 10-dimensional space. The Euclidean distance between them is the square root of (A[0] - B[0])^2 + (A[1] - B[1])^2 + ... + (A[9] - B[9])^2.
-In both input String[]s, the integers are separated by single spaces and contain no unnecessary leading zeros. The same limitations must hold for your return value.
-The time limit is 10 seconds (this includes only the time spent in your code). The memory limit is 1024 megabytes.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 100 full submission test cases.


N = 1036
N = 472
N = 1991
N = 520
N = 1909
N = 1330
N = 1006
N = 1612
N = 769
N = 1434

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.