JOIN
Get Time
long_comps_intel  Problem Statement
Contest: Intel Multi-Threading Competition 4
Problem: NearestNeighbors

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:
  1. The number of elements in A and B and the number of dimensions are chosen uniformly in the given ranges.
  2. A random integer G is chosen uniformly between 1 and 100.
  3. 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.
  4. A probability p is generated uniformly between 0 and 1
  5. 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)
    
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)
    
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)
    
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)
    
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)
    
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)
    
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)
    
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)
    
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)
    
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)
    
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

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.