Problem Statement |
| | You will be given two sets of points in N-dimensional space: A and B. Your task is: for every point b in set B, find the point a in set A that is closest to b (using Euclidean distance).
More specifically, you will be given String[]'s A and B, where each element represents a point. Each element is a single-space delimited list of N reals between 0 and 1 (inclusive), where the ith real corresponds to the ith dimension. You should return a int[] with |B| elements. Element j of the return should be the index into A of the point closest to the jth element of B (all indexed from 0).
Scoring will be based on the quality of your algorithm's return. For a test case, your score will be proptional to |B|*N/sum(distance2). Your final score will be the sum of your scores on the individual test cases.
The test cases will be generated as follows:
- The number of elements in A and B and the number of dimensions are chosen uniformly in the given ranges.
- A random integer G is chosen uniformly between 1 and 100.
- G Gaussian distributions are created. For each distribution, a mean and standard deviation are chosen randomly at uniform for each dimension between 0 and 1.
- A probability p is generated uniformly between 0 and 1
- Next, the points of A and B are generated. Each point either comes from one of the Gaussian distributions (with probability p), or is chosen uniformly at random from the unit hyper-cube. If a point is generated from one of the gaussian distributions, but falls outside the unit hyper-cube, that point is regenerated (from the same distribution) until it falls within the unit hyper-cube. Points generated from the Gaussian distributions have each of their dimensions generated independently from a normal curve according to the mean and standard deviation for that dimension.
|
| |
Definition |
| | | Class: | NearestNeighbors | | Method: | nearest | | Parameters: | String[], String[] | | Returns: | int[] | | Method signature: | int[] nearest(String[] A, String[] B) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 15 seconds. |
| - | The memory limit is 1024 megabytes. |
| - | The thread limit is 32 threads (including the primary thread). |
| - | An invalid return will receive a score of 0. |
| |
Constraints |
| - | A and B will each contain between 1 and 50,000 elements, inclusive. |
| - | N will be between 10 and 50, inclusive. |
| - | Each decimal number will have exactly 6 digits after the decimal point. |
| |
Examples |
| 0) | |
| | | Returns:
"In this test case, A has 10 elements, while B has 10 elements. There are 15 dimensions." | Download the example here: (1.2K)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex0.gz |
|
|
| 1) | |
| | | Returns:
"In this test case, A has 20 elements, while B has 20 elements. There are 39 dimensions." | Download the example here: (5.9K)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex1.gz |
|
|
| 2) | |
| | | Returns:
"In this test case, A has 50 elements, while B has 50 elements. There are 48 dimensions." | Download the example here: (18K)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex2.gz |
|
|
| 3) | |
| | | Returns:
"In this test case, A has 100 elements, while B has 100 elements. There are 50 dimensions." | Download the example here: (37K)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex3.gz |
|
|
| 4) | |
| | | Returns:
"In this test case, A has 21752 elements, while B has 45585 elements. There are 30 dimensions." | Download the example here: (7.1M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex4.gz |
|
|
| 5) | |
| | | Returns:
"In this test case, A has 39555 elements, while B has 23042 elements. There are 32 dimensions." | Download the example here: (7.0M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex5.gz |
|
|
| 6) | |
| | | Returns:
"In this test case, A has 49232 elements, while B has 49679 elements. There are 19 dimensions." | Download the example here: (6.6M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex6.gz |
|
|
| 7) | |
| | | Returns:
"In this test case, A has 42095 elements, while B has 35872 elements. There are 49 dimensions." | Download the example here: (13M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex7.gz |
|
|
| 8) | |
| | | Returns:
"In this test case, A has 18979 elements, while B has 36506 elements. There are 16 dimensions." | Download the example here: (3.1M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex8.gz |
|
|
| 9) | |
| | | Returns:
"In this test case, A has 10555 elements, while B has 45064 elements. There are 47 dimensions." | Download the example here: (9.2M)
http://www.topcoder.com/contest/problem/NearestNeighbors/ex9.gz |
|
|