# Find the most convenient meeting room

In the following question, one has to find the most convenient x-y-z co-ordinates in a building for a group of employees to sit together. I have tried finding individual average values for x, y & z but that didn't work. Moreover, a time-efficient approach is what I'm looking for.

Problem Statement -

Each floor in an IT office is arranged in a rectangular array of M×N cubicles. Cubicles on floor F are identified by coordinates (1, 1, F) to (M,N, F). There are connections between a cubicle and its neighbors on the floor. Each cubicle is also connected vertically to the corresponding cubicle one floor above and one floor below. Thus, from a given cubicle (i, j, k) on floor k, an employee can go across to one of its four neighbors (i+1, j, k), (i−1, j, k), (i, j+1, k), (i, j−1, k) on the same floor. He can also go up one floor to reach the cubicle (i, j, k+1) or down one floor to reach the cubicle (i, j, k−1).

It takes 2 units of effort for an employee to cross to a neighboring cubicle on the same floor. It takes 1 unit of effort to go to the corresponding cubicle one floor below. It costs 3 units of effort for an employee to go to the corresponding cubicle one floor up.

A group of employees want to meet to discuss something. They would like to meet in a cubicle located so that their overall effort to reach the meeting place is minimized. The cubicle where they meet can be anywhere in the building —it need not be one in which one of them sits. For instance, suppose that there are 5 employees who sit in cubicles with coordinates (28,3,17), (8,36,48), (6,36,31), (50,24,15) and (12,28,32). Then, the best cubicle for them to meet is the one at (12,28,17).

In the three problems below, you are given the list of cubicles where a group of employees sit. Your task is to identify the coordinates of the optimum cubicle for them to meet.

(a) 13 people seated in cubicles (36,90,7), (77,69,7), (75,22,7), (43,30,7), (75,62,7), (70,23,7), (76,30,7), (25,28,7), (95,56,7), (3,25,7), (51,98,7), (2,11,7), (46,46,7).

(b) 25 people seated in cubicles (51,1,73), (61,1,33), (1,1,34), (46,1,38), (23,1,94), (91,1,89), (11,1,89), (10,1,70), (37,1,73), (96,1,93), (44,1,50), (16,1,81), (50,1,28), (50,1,84), (55,1,60), (48,1,97), (3,1,62), (92,1,84), (27,1,22), (100,1,51), (59,1,31), (8,1,39), (55,1,47), (50,1,1), (33,1,45).

(c) 21 people seated in cubicles (18,72,69), (12,81,43), (40,19,33), (40,60,48), (2,78,66), (14,78,84), (70,25,3), (48,59,43), (29,4,10), (12,96,1), (89,13,74), (57,26,54), (100,32,39), (99,38,65), (13,40,43), (79,20,20), (28,91,12), (98,38,37), (40,34,41), (16,46,36), (18,1,16).

Source - Zonal Informatics Olympiad 2007 Question Paper

Thanks!

-

(a) Begin by considering the analogous one-dimensional problem: You are given $n$ integers $x_k$ between $0$ and $M$. How should you choose $\xi\in{\mathbb Z}$ such that $s:=\sum_{k=1}^n |x_k-\xi|$ is minimal? Draw a figure, choose a trial $\xi$ and check how $s$ changes when $\xi$ is moved right or left.