Problem 1942. GJam 2014 China Rd B: Party
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.
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers5
Suggested Problems
-
Find the longest sequence of 1's in a binary sequence.
6188 Solvers
-
Get the area codes from a list of phone numbers
1052 Solvers
-
444 Solvers
-
616 Solvers
-
6960 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!