CareerCup

I guess its solved. the solution has 2-3 points about it: it goes like this.
1) treat both the dimensions independently (lets first solveit for X whose cardinality is N in MxN)
2) assume a group of 0 ppl on the points where where is no group.
3) now we have an array (ith element is the total of ppl on x=1)
4) we have an array like 5 0 0 3 2 7 0 0 0 0 1
5) now for each element find the weighted sum of the rest of the elements. it can be done in O(n). Not writing the algo for that.
6) pick the index with lowest value in this array. that is x cordinates

repeat it for y
solution will be O(m+n)

Look at the perspective that the cost of moving a group of people is a (distanceX+distanceY)*amount. So we need to calculate the minimal cost moving by X and then by Y axis.

public static class Location {

        public int x;
        public int y;

        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static class MeetingLocation extends Location {

        public int amountOfPeople;

        public MeetingLocation(int x, int y, int amountOfPeople) {
            super(x, y);
            this.amountOfPeople = amountOfPeople;
        }
    }

    public static Location moveLowestCost(int n, int m, MeetingLocation... meetingLocations) {
        Location newLocation = new Location(0, 0);
        int minCostX = Integer.MAX_VALUE, minCostY = Integer.MAX_VALUE;
        for (int x = 0; x < m; x++) {
            int costX = 0;
            for (MeetingLocation location : meetingLocations) {
                costX += location.amountOfPeople * calculateAbsDistance(x, location.x);
            }
            if (minCostX > costX) {
                minCostX = costX;
                newLocation.x = x;
            }
        }
        for (int y = 0; y < n; y++) {
            int costY = 0;
            for (MeetingLocation location : meetingLocations) {
                costY += location.amountOfPeople * calculateAbsDistance(y, location.y);
            }
            if (minCostY > costY) {
                minCostY = costY;
                newLocation.y = y;
            }
        }
        return newLocation;
    }

    public static int calculateAbsDistance(int x, int x1) {
        if (x >= x1) {
            return x - x1;
        } else {
            return x1 - x;
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        final Location newLoc = moveLowestCost(3, 4, new MeetingLocation(0, 1, 4), new MeetingLocation(1, 3, 3), new MeetingLocation(2, 0, 5));
        System.out.println("X = " + newLoc.x + "; Y = " + newLoc.y);
    }

Find the center of mass with respect to x round it to nearest x,
Find the average of y
get the intersection of above two equation
that should be the meeting point.

for eg :
Group1: (0, 1), 4

Group2: (1, 3), 3

Group3: (2, 0), 5

wrt to x cm =(4*0 + 1*3+2*5)/12 =~1
wrt to y = average (1+3+0)/3 = ~1


x=1
and y=1
meeting point should be (1,1)

Hey, I just found out that in the given example (1,1) is not the minimum,
it is (1,0)....
Cost is 4 at (1,0).

as someone has already pointed, find the geometric median (GM), (weighted in this case, as multiple elements at same place)
Sometimes, its good to calculate min distance for constant number of points close to GM.
may be around 100-150 for many people/groups (~10000)

Inspired by abhishek's idea. It seems that there is a O(G) solution for this problem. Since everyone agree with the two dimensional problem can be reduced to two one dimensional problem. I will not repeat it again. I just focus on how to solve the one dimensional problem with O(G).

Suppose, people are standing like this, a[0], a[1], ... a[n-1]. There is a[i] people standing at spot i. There are G spots having people(G <= n). Assuming these G spots are g[1], g[2], ..., g[G], where gi is in [0,...,n-1]. Without losing generality, we can also assume that g[1] < g[2] < ... < g[G].

It's not hard to prove that the optimal spot must come from these G spots. I will pass the prove here and left it as an exercise if you guys have interest.

Since the above observation, we can just compute the cost of moving to the spot of every group and then chose the minimal one. There is an obvious O(G^2) algorithm to do this.

But using kilotaras's idea, we can do it in O(G)(no sorting).

cost[1] = sum((g[i]-g[1])*a[g[i]], i = 2,...,G) // the cost of moving to the 
spot of first group. This step is O(G).

cur_r = sum(a[g[i]], i = 2,...,G) //How many people is on the right side of the 
second group including the second group. This step is O(G).

cur_l = a[g[1]] //How many  people is on the left side of the second group not 
including the second group. 

for i = 2:G       
    gap = g[i] - g[i-1];
    cost[i] = cost[i-1] - cur_r*gap + cur_l*gap;
    if i != G
        cur_r = cur_r - a[g[i]];
        cur_l = cur_l + a[g[i]];
    end
end

The minimal of cost[i] is the answer.

Using the example 5 1 0 3 to illustrate the algorithm. In this example,

n = 4, G = 3.

g[1] = 0, g[2] = 1, g[3] = 3.

a[0] = 5, a[1] = 1, a[2] = 0, a[3] = 3.

(1) cost[1] = 1*1+3*3 = 10, cur_r = 4, cur_l = 5.

(2) cost[2] = 10 - 4*1 + 5*1 = 11, gap = g[2] - g[1] = 1, cur_r = 4 - a[g[2]] = 3, cur_l = 6.

(3) cost[3] = 11 - 3*2 + 6*2 = 17, gap = g[3] - g[2] = 2.

the more population at a cordinte the less we want them to move. so the one center point should be weighted mean of inverse of population.So we can take the LCM (population of each place)and do following

Summation (Xi * LCM(Pop)/pop(Xi,Yi), Summation (Yi * LCM(Pop)/pop(Xi,Yi),

the proof lies in the section formula of dividing lines into m:n ratio.
One more thing, We must respect the sign of a cordinate as Xi,Yi can be in any quadrant.

Here is what I did in C#:

public struct Group
        {
            public Point Location;
            public int Count;
        }

        public Point GetNearestCenter(Group[] input)
        {
            if (input == null || input.Length == 0)
            {
                throw new ArgumentException();
            }

            Rectangle rect = this.GetBoundingBox(input);
            Point result = new Point();
            int moveSteps = int.MaxValue;

            for (int x = rect.X; x < rect.Right; x++)
            {
                for (int y = rect.Y; y < rect.Bottom; y++)
                {
                    int temp = 0;
                    for (int i = 0; i < input.Length; i++)
                    {
                        temp += Math.Abs(input[i].Location.X - x) * input[i].Count + Math.Abs(input[i].Location.Y - y) * input[i].Count;
                    }

                    if (temp < moveSteps)
                    {
                        result = new Point(x, y);
                        moveSteps = temp;
                    }
                }
            }


            return result;
        }

        private Rectangle GetBoundingBox(Group[] inputs)
        {
            int xmax = int.MinValue;
            int ymax = int.MinValue;
            int ymin = int.MaxValue;
            int xmin = int.MaxValue;

            for (int i = 0; i < inputs.Length; i++)
            {
                xmax = Math.Max(xmax, inputs[i].Location.X);
                ymax = Math.Max(ymax, inputs[i].Location.Y);
                xmin = Math.Min(xmin, inputs[i].Location.X);
                ymin = Math.Min(ymin, inputs[i].Location.Y);
            }

            return new Rectangle(xmin, ymin, xmax - xmin, ymax - ymin);
        }

Test:
/// <summary>
///A test for GetNearestCenter
///</summary>
[TestMethod()]
public void GetNearestCenterTest()
{
Google1 target = new Google1(); // TODO: Initialize to an appropriate value
Google1.Group[] input = new Google1.Group[]{
new Google1.Group(){Location = new Point(0, 1), Count=4},
new Google1.Group(){Location = new Point(1, 3), Count=3},
new Google1.Group(){Location = new Point(2, 0), Count=5}
};
Point expected = new Point(1, 1); // TODO: Initialize to an appropriate value
Point actual;
actual = target.GetNearestCenter(input);
Assert.AreEqual(expected, actual);
}

The question is equal to min (Sigma |Xi-X | +Sigma |Yi-Y | )=min| Sigma |Xi-X | | +min| Sigma |Yi-Y | |
Test all the possible X for Xi,
and test all the possible Y for Yi will get a complexity of (O(m+n));

The solution is as follows:
As xiaoc10 said, we should reduce the problem to two one dimensional problem.
Now, assume that we are going to find the best X. First sort the group based on their x => O(G) because possible value for x is limited!
Then start from one of the ends of the list, try to sum up the number of people in each group until the sum is greater or equal to total/2. Here will be the best place!

An easy intuitive solution would be O(mn) where m is number of rows and n is number of columns ....

First create four arrays two each of size m and n respectively

1. array 1 of size m will contain how many elements lie before x coordinate
2. array 2 of size m will contain how many elements lie after x coordinate
3. array 3 of size n will contain how many elements lie above y co-ordinate
4. array 4 of size n will contain how many elements lie below y co-ordinate

In each of the arrays, the x or y co-ordinates refer to the array index.

Now follow the following steps:

1. Compute Cost[0][0]
2. Compute Cost[0][1] as Cost[0][0]+array[1]-array2[1] (No need to account for y-axis movement.
3. Compute Cost[1][0] as Cost[0][0]+array3[1]-array4[1]

Whichever i,j pair has minimum value for cost will be the answer.

I'm not really sure about the correctness of previously mentioned algorithms

Check my analysis. The time complexity is O(G).
allenlipeng47.com/PersonalPage/index/view/89/nkey

I think this can be solved in O(n>m?n:m) time and O(n>m?n:m) space. We have to find the median of x coordinates and median of all y coordinates in the k points and the answer will be (x_median,y_median);

Assumption is this function takes in the following inputs: a. total number of points :int k= 4+3+5 = 12; b. An array of coordinates: struct coord_t c[12] = {(0,1),(0,1),(0,1), (0,1), (1,3), (1,3),(1,3),(2,0),(2,0),(2,0),(2,0),(2,0)}; c.int size = n>m ? n:m;

Let the input of the coordinates be an array of coordinates. coord_t c[k]

struct coord_t {
int x;
int y;
};

1. My idea is to create an array of size = n>m?n:m;
2. int array[size] = {0} ; //initialize all the elements in the array to zero

for(i=0;i<k;i++)
{
array[c[i].x] = +1;
count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
if(array[i]!=0)
{
tempCount += array[i];
}
if(tempCount >= count/2)
{
break;
}
}
int x_median = i;

//similarly with y coordinate.

int array[size] = {0} ; //initialize all the elements in the array to zero
for(i=0;i<k;i++)
{
array[c[i].y] = +1;
count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
if(array[i]!=0)
{
tempCount += array[i];
}
if(tempCount >= count/2)
{
break;
}
}

int y_median = i;

coord_t temp;
temp.x = x_median;
temp.y= y_median;
return temp;


Sample Working code for MxM matrix with k points:

/*Problem Given a MxM grid . and N people placed in random position on the grid. Find the optimal meeting point of all the people. / / Answer: Find the median of all the x coordiates of the positions of the people. Find the median of all the y coordinates of the positions of the people. */


#include<stdio.h>
#include<stdlib.h>
typedef struct coord_struct {
int x;
int y;
}coord_struct;

typedef struct distance {
int count;
}distance;

coord_struct toFindTheOptimalDistance (int N, int M, coord_struct input[])
{
coord_struct z ;
z.x=0;
z.y=0;
int i,j;
distance * array_dist;
array_dist = (distance*)(malloc(sizeof(distance)*M));
for(i=0;i<M;i++)
{
array_dist[i].count =0;
}

for(i=0;i<N;i++)
{
array_dist[input[i].x].count +=1;
printf("%d and %d\n",input[i].x,array_dist[input[i].x].count);
}
j=0;
for(i=0;i<=N/2;)
{
printf("%d\n",i);
if(array_dist[j].count !=0)
i+=array_dist[j].count;


j++;
}

printf("x coordinate = %d",j-1);
int x= j-1;
for(i=0;i<M;i++)
array_dist[i].count =0;

for(i=0;i<N;i++)
{
array_dist[input[i].y].count +=1;
}
j=0;
for(i=0;i<N/2;)
{

if(array_dist[j].count !=0)
i+=array_dist[j].count;

j++;
}

int y =j-1;
printf("y coordinate = %d",j-1);
z.x=x;
z.y =y;
return z;
}
int main()
{
coord_struct input[5];
input[0].x =1;
input[0].y =2;
input[1].x =1;
input[1].y =2;
input[2].x =4;
input[2].y =1;
input[3].x = 5;
input[3].y = 2;
input[4].x = 5;
input[4].y = 2;
int size = m>n?m:n;
coord_struct x = toFindTheOptimalDistance(5,size,input);
}

My guess is that if we find center of mass of this configuration:
i.e. weighted average of their cordinates, that should be what we are looking for. But I cant prove it will be the minimum. Again in algorithms we hardly prove anything unless someone points out a wrong case :).