Problem 44353. Group-wise Euclidean distance

Created by Peng Liu

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>x</w:t></w:r><w:r><w:t> —— An array of size</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>n-by-d</w:t></w:r><w:r><w:t>, where each row vector denotes a point in a d-dimensional space;</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>g</w:t></w:r><w:r><w:t> —— A grouping (index) vector g of size</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>n-by-1</w:t></w:r><w:r><w:t>, 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>y</w:t></w:r><w:r><w:t> —— The group-wise Euclidean distance matrix associated with the points in x. Suppose that m = max(g), then y will be an</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>m-by-m</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example 1: n = 6, d = 1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[g = [2 1 3 2 1].';\nx = [3 10 15 8 5].';\ny = [0 2 5 % y(1,2) = y(2,1) = min(10-3,5-3,10-8,8-5) = 2\n 2 0 7 % y(1,3) = y(3,1) = min(15-10,15-5) = 5\n 5 7 0]; % y(2,3) = y(3,2) = min(15-3,15-8) = 7]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example 2: n = 3, d = 2</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[g = [1 2 2].';\nx = [0 0\n 5 12\n 3 4];\ny = [0 5;\n 5 0]; % y(1,2) = y(2,1) = min(sqrt(5^2+12^2),sqrt(3^2+4^2)) = 5]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Testing</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The test suite will focus mainly on the large-scale 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 time-out error if it is not sufficiently efficient (which is why this problem falls into the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/groups/35\"><w:r><w:t>Cody5:Hard</w:t></w:r></w:hyperlink><w:r><w:t> category).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>We have modified Cody's default size-based scoring function into a performance-based scoring system (implemented by our fellow Cody player</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/players/3021298-ly-cao\"><w:r><w:t>LY Cao</w:t></w:r></w:hyperlink><w:r><w:t>), 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).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Please be advised that an amazingly fast solution would earn a score &lt; 5, meaning that it completes execution of all test cases within a second!</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Update</w:t></w:r><w:r><w:t> (11/21/2017): Additional test cases are added to ban cheater solutions (e.g., hard-coded submissions 1351541, 1351007, 1350563, 1349442, all came from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/players/3931805-marco-tullio\"><w:r><w:t>Marco Tullio</w:t></w:r></w:hyperlink><w:r><w:t>).</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Input:<ul><li>x —— An array of size n-by-d, where each row vector denotes a point in a d-dimensional space;</li><li>g —— A grouping (index) vector g of size n-by-1, 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.</li></ul>Output:<ul><li>y —— The group-wise Euclidean distance matrix associated with the points in x. Suppose that m = max(g), then y will be an m-by-m 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.</li></ul>Example:Example 1: n = 6, d = 1<pre class="language-matlab">g = [2 1 3 2 1].';
x = [3 10 15 8 5].';
y = [0 2 5 % y(1,2) = y(2,1) = min(10-3,5-3,10-8,8-5) = 2
 2 0 7 % y(1,3) = y(3,1) = min(15-10,15-5) = 5
 5 7 0]; % y(2,3) = y(3,2) = min(15-3,15-8) = 7
</pre>Example 2: n = 3, d = 2<pre class="language-matlab">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
</pre>Testing:The test suite will focus mainly on the large-scale 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 time-out error if it is not sufficiently efficient (which is why this problem falls into the <a href = "https://www.mathworks.com/matlabcentral/cody/groups/35">Cody5:Hard</a> category).Scoring:We have modified Cody's default size-based scoring function into a performance-based scoring system (implemented by our fellow Cody player <a href = "https://www.mathworks.com/matlabcentral/cody/players/3021298-ly-cao">LY Cao</a>), 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 &lt; 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., hard-coded submissions 1351541, 1351007, 1350563, 1349442, all came from <a href = "https://www.mathworks.com/matlabcentral/cody/players/3931805-marco-tullio">Marco Tullio</a>).

*Input*:
 
* *x* —— An array of size *n-by-d*, where each row vector denotes a point in a d-dimensional space;
* *g* —— A grouping (index) vector g of size *n-by-1*, 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 group-wise Euclidean distance matrix associated with the points in x. Suppose that m = max(g), then y will be an *m-by-m* 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(10-3,5-3,10-8,8-5) = 2
       2   0   7            % y(1,3) = y(3,1) = min(15-10,15-5) = 5
       5   7   0];          % y(2,3) = y(3,2) = min(15-3,15-8) = 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 large-scale 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 time-out error if it is not sufficiently efficient (which is why this problem falls into the <https://www.mathworks.com/matlabcentral/cody/groups/35 Cody5:Hard> category).

*Scoring*:

We have modified Cody's default size-based scoring function into a performance-based scoring system (implemented by our fellow Cody player <https://www.mathworks.com/matlabcentral/cody/players/3021298-ly-cao 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., hard-coded submissions 1351541, 1351007, 1350563, 1349442, all came from <https://www.mathworks.com/matlabcentral/cody/players/3931805-marco-tullio Marco Tullio>).

Solve

Solution Stats

404 Solutions
68 Solvers

Last Solution submitted on Sep 30, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

goc3 on 26 Oct 2017

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?

Peng Liu on 26 Oct 2017

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 y-axis scale would be [0,100] (which makes all solutions distinguishable). But this also results in a re-scoring 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.

Ziheng Hu on 22 Dec 2017

All problems should be scored by its speed rather than size imo.

Gunther S on 5 Jan 2018

leading solution is cheater solution: https://www.mathworks.com/matlabcentral/cody/problems/44353-group-wise-euclidean-distance/solutions/1391283

Solution Comments

Solution 1351541

3 Comments

3 Comments

Peng Liu on 21 Nov 2017

Banned cheater solution.

Alfonso Nieto-Castanon on 21 Nov 2017

if you are feeling overwhelmed by a particularly persistent cheater just know that you can ban a player from your own problems by adding to your testsuite something like: lines=textread('groupDist.m','%s'); id=str2num(regexp(lines{end},'\d+','match','once')); assert(~ismember(id,[123456789 234567890]),'banned player id'); (where the array in the ismember line contains the list of player ids that you want to ban from your problem -e.g. my player id is 1379371; please do not ban me :)

Peng Liu on 21 Nov 2017

Many thanks Alfonso for your suggestion. I was just thinking if I can ban a persistent cheater based on the player id. What you suggested is exactly what I need. If this guy cheats one more time (which is getting harder now with my added pcode in the test suite), I will definitely ban the guy using your suggested code.

Solution 1351007

1 Comment

1 Comment

Peng Liu on 20 Nov 2017

What's the point to keep cheating?

Solution 1350563

1 Comment

1 Comment

Peng Liu on 20 Nov 2017

Dis-allowed.

Solution 1349442

1 Comment

1 Comment

Peng Liu on 19 Nov 2017

Hard-coded solutions are disallowed.

Solution 1312213

1 Comment

1 Comment

Dyuman Joshi on 24 Apr 2021

How is it possible to have size 2 for this big code?

Problem Recent Solvers68

Problem Tags

cody5 speed

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!