Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 1942. GJam 2014 China Rd B: Party

Created by Richard Zapor

This Challenge is derived from GJam 2014 China Party. 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<=100). Total B area of <=1000

Output: [x,y,d] where [x,y] is Party House and d is everyone's total distance

Examples:

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]

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:

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.

Tags

Problem Group

Solution Statistics

12 correct solutions 1 incorrect solutions
Last solution submitted on Oct 20, 2013

Solution Comments