Minimum Sum of All Travel Times

Question

I found a puzzle online on interviewStreet and tried to solve it as follows:

There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time. eg: (x,y) can be reached from (x-1,y+1) in a single unit of time. Find a common meeting place which minimizes the sum of the travel times of all the persons.

I thought first about writing a solution in n² complexity in time, but the constraints are

1<=N<=10^5 and The absolute value of each co-ordinate in the input will be atmost 10^9

So, I changed my first approach and instead of looking at the problem with the distances and travel times, I looked at the different houses as different bodies with different weights. And instead of calculating all the distances, I look for the center of gravity of the group of bodies.

Here's the code of my "solve" function, vectorToTreat is an lengthX2 table storing all the data about the points on the grid and resul is the number to print to stdout:

long long solve(long long** vectorToTreat, int length){
    long long resul = 0;
    int i;
    long long x=0;
    long long y=0;
    int tmpCur=-1;
    long long tmp=-1;
    for(i=0;i<length;i++){
        x+=vectorToTreat[i][0];
        y+=vectorToTreat[i][1];
    }
    x=x/length;
    y=y/length;
    tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y));
    tmpCur = 0;
    for(i=1;i<length;i++){
        if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){
            tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
            tmpCur = i;
        }
    }
    for(i=0;i<length;i++){
        if(i!=tmpCur)
            resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1]));
    }

    return resul;
}

The problem now is that I passed 12 official test cases over 13, and I don't see what I'm doing wrong, any ideas? Thanks in advance. AE

Answer 1

The key to this problem is the notion of centroid of a set of points. The meeting place is the closest house to the centroid for the set of points representing all the houses. With this approach you can solve the problem in linear time, i.e. O(N). I did it in Python, submitted my solution and passed all tests.

However, it is easy to build a data set for which the centroid approach does not work. Here's an example:

[(0, 0), (0, 1), (0, 2), (0, 3), 
 (1, 0), (1, 1), (1, 2), (1, 3), 
 (2, 0), (2, 1), (2, 2), (2, 3), 
 (3, 0), (3, 1), (3, 2), (3, 3), 
 (101, 101)]

The best solution is meeting at the house at (2, 2) and the cost is 121 (you can find this with exhaustive search - O(N^2)). However, the centroid approach gives a different result:

• centroid is (7, 7)
• closest house to centroid is (3, 3)
• cost of meeting at (3, 3) is 132

Test cases on the web site are obviously shaped in a such a way that the centroid solution is OK, or perhaps they just wanted to figure out if you know about the notion of centroid.

Answer 2

I didn't read your code, but consider the following example:

• 2 guys live at (0, 0)
• 1 guy lives at (2, 0)
• 4 guys live at (3, 0)

The center of gravity is at (2, 0), with minimum total travel time of 8, but the optimum solution is at (3, 0) with minimum total travel time of 7.