296. Best Meeting Point

[ErdemT09]

Resolves: #212

Algorithm:

We could think of this problem as a counting problem on a single dimension. Consider the sequence: 1-0-0-0-2-0, where values indicate the number of friends on that tile. The best meeting point would be the location with 2 friends in it. Suppose the first and one of these 2 friends wanted to meet. Their meeting cost would be 4, as longs they meet somewhere in between. Now, the latter of these 2 friends also has to move there. What should the minimum point be then? Of course, point with distance 0, so the median location, the original location of the 2 friends. Now consider a similar sequence: 2-0-1-0-2-0 When two from these 2 groups meet, the eventual cost would be two times their distance. When the median is left in the middle, the meeting point is determined by its location.

From this, we can deduce that the 2D minimum distance is just the sum of minimum column and row distances when we count the number of friends for each one of them. From left to right, we pick the smaller group and move it right and then subtract the size of this smaller group so as to mark that some friends have met. The algorithm follows from this.

[altay9]

Again, a wonderful explanation technique starting with an easier instance of the problem.