Problem 1942. GJam 2014 China Rd B: Party

Created by Richard Zapor

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:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2929486/dashboard#s=p1\"><w:r><w:t>GJam 2014 China Party</w:t></w:r></w:hyperlink><w:r><w:t>. Small Case.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Goal is determine the optimal Party House. Given a set of people to attend a party, select the home from this set that minimizes the total travel of people. People travel only NSEW, no diagonals, to reach the host's home. If multiple homes have equal distance then select the home with minimum X. If there are more than one with Min distance and equal Min X then choose the house with Min Y.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The input is an array that defines rectangles of partiers. One line of the array is [xmin,ymin,xmax,ymax]. Blocks do not overlap.</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>Input:</w:t></w:r><w:r><w:t> [M], Bx4 matrix (B&lt;=100). Total B area of &lt;=1000</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> [x,y,d] where [x,y] is Party House and d is everyone's total distance</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>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[M [x y d]\n[0 0 2 2] [1 1 12]\n[-1 2 -1 2;0 0 0 0;1 3 1 3] [-1 2 6]]]></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>Contest Performance:</w:t></w:r><w:r><w:t> Best Delta Time of 16 minutes with 496 of 2010 able to process the small data set. The large data set was only achieved by 47 in the 3 hrs of contest duration.</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>Commentary:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1) The small can be solved by brute force since fewer than 1000 points require evaluation.\n2) The large case, which is giving me fits, has up to 1,000,000 points to evaluate.\n3) Graphing the small case with surf gives some unexpected asymmetric results relative to the simple centroid.]]></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>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2929486/dashboard#s=p1">GJam 2014 China Party</a>. Small Case.The Goal is determine the optimal Party House. Given a set of people to attend a party, select the home from this set that minimizes the total travel of people. People travel only NSEW, no diagonals, to reach the host's home. If multiple homes have equal distance then select the home with minimum X. If there are more than one with Min distance and equal Min X then choose the house with Min Y.The input is an array that defines rectangles of partiers. One line of the array is [xmin,ymin,xmax,ymax]. Blocks do not overlap.Input: [M], Bx4 matrix (B&lt;=100). Total B area of &lt;=1000Output: [x,y,d] where [x,y] is Party House and d is everyone's total distanceExamples:<pre class="language-matlab">M [x y d]
[0 0 2 2] [1 1 12]
[-1 2 -1 2;0 0 0 0;1 3 1 3] [-1 2 6]
</pre>Contest Performance: Best Delta Time of 16 minutes with 496 of 2010 able to process the small data set. The large data set was only achieved by 47 in the 3 hrs of contest duration.Commentary:<pre class="language-matlab">1) The small can be solved by brute force since fewer than 1000 points require evaluation.
2) The large case, which is giving me fits, has up to 1,000,000 points to evaluate.
3) Graphing the small case with surf gives some unexpected asymmetric results relative to the simple centroid.
</pre>

Solve

Solution Stats

15 Solutions
5 Solvers

Last Solution submitted on Aug 04, 2019

Last 200 Solutions

Solution Comments

Solution 335988

1 Comment

1 Comment

Alfonso Nieto-Castanon on 20 Oct 2013

I am sure there are other more subtle ways to go about it but this seems about as fast as I can make it for a general brute-force solution (0.11s)

Solution 335653

1 Comment

1 Comment

Tim on 18 Oct 2013

This one seems to work for the large test case, too, although it is not a general solution [for size(p,1)>100 it only tests corner points].

Problem Recent Solvers5

Problem Tags

Problem 1942. GJam 2014 China Rd B: Party

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author236

Problem Tags

Problem 1942. GJam 2014 China Rd B: Party

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author236

Problem Tags

Players