Problem 44353. Groupwise Euclidean distance
Input:
 x —— An array of size nbyd, where each row vector denotes a point in a ddimensional space;
 g —— A grouping (index) vector g of size nby1, which divides the points in x into groups. Specifically, the rows in x corresponding to the same group index in g belong to the same group.
Output:
 y —— The groupwise Euclidean distance matrix associated with the points in x. Suppose that m = max(g), then y will be an mbym matrix, where each element y(i,j) is the Euclidean distance between group i and group j, which is defined as the minimum of the Euclidean distances between any points in group i and any other points in group j.
Example:
Example 1: n = 6, d = 1
g = [2 1 3 2 1].'; x = [3 10 15 8 5].'; y = [0 2 5 % y(1,2) = y(2,1) = min(103,53,108,85) = 2 2 0 7 % y(1,3) = y(3,1) = min(1510,155) = 5 5 7 0]; % y(2,3) = y(3,2) = min(153,158) = 7
Example 2: n = 3, d = 2
g = [1 2 2].'; x = [0 0 5 12 3 4]; y = [0 5; 5 0]; % y(1,2) = y(2,1) = min(sqrt(5^2+12^2),sqrt(3^2+4^2)) = 5
Testing:
The test suite will focus mainly on the largescale problem dimensions (e.g., large n and/or d). The purpose is to direct attention towards efficient runtime speed of execution. Note that your solution may run into a timeout error if it is not sufficiently efficient (which is why this problem falls into the Cody5:Hard category).
Scoring:
We have modified Cody's default sizebased scoring function into a performancebased scoring system (implemented by our fellow Cody player LY Cao), in which the score of your submission equals 5 times the execution time of your solution (which reprents a score resolution of 0.2 seconds and allows for more room for performance improvement). Please ignore the code size and focus only on improving the code performance, as our test suite will reject any submissions running longer than 20 seconds (in contrast to Cody's default 40 seconds timeout limit).
Please be advised that an amazingly fast solution would earn a score < 5, meaning that it completes execution of all test cases within a second!
Update (11/21/2017): Additional test cases are added to ban cheater solutions (e.g., hardcoded submissions 1351541, 1351007, 1350563, 1349442, all came from Marco Tullio).
Solution Stats
Problem Comments

4 Comments
It's too bad that one stray wrong answer with an inordinately high score size ruins the scale of the solution graph. Is there any way to fix that?
Thanks for your feedback. That stray answer tried to hack the scoring in the test suite, and is now removed. Unfortunately, the current scale of the score map is still not good (hard to distinguish good solutions with score < 50). A possible workaround (from a user side) is to modify the scoring in the test suite to truncate the high scores (>=100) to 100, and the resulting yaxis scale would be [0,100] (which makes all solutions distinguishable). But this also results in a rescoring of all solutions, which might change the current ranking of those similarly fast solutions (e.g., the current best two solutions have an equal score of 2)... I would appreciate any further suggestions (or comments from the Cody admin side) on this.
All problems should be scored by its speed rather than size imo.
leading solution is cheater solution: https://www.mathworks.com/matlabcentral/cody/problems/44353groupwiseeuclideandistance/solutions/1391283
Solution Comments
Show comments
Problem Recent Solvers72
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!