Fair division of a kingdom [closed]

Question

Recently, I've attended programming competition. There was a problem from it that I am still mulling over. Programming language does not matter, but I've wrote it in C++. The task was this:

As you already know, Flatland is located on the plane. There are n cities in Flatland, i-th of these cities is located at the point (xi, yi). There are ai citizens living in i-th city. The king of Flatland has decided to divide the kingdom between his two sons. He wants to build a wall in the form of infinite straight line; each of the parts will be ruled by one of the sons. The wall cannot pass through any city. To avoid envy between brothers, the populations of two parts must be as close as possible; formally, if a and b are the total number of citizens living in cities of the first and the second part respectively, the value of |a - b| must be minimized. Help the king to find the optimal division. Number of cities is less than 1000. And all coordinates are integers. Output of algorithm should be integer number of minimal |a-b|

Okay, if I knew the direction of line, it will be really easy task - binary search:

I don't want code, I want ideas because I don't have any. If I catch idea I can write code!

I don't know optimal direction, but I think it could be found somehow. So could it be found or is this task solved other way?

An example where the horizontal/vertical line is not optimal:

1

\
 \
2 \      1

Answer 1

The Ansatz

A brute force method would be to check all possible division...

First it should be noted, that the exact orientation of the line does not matter. It can always be shifted by small amounts and there are cases with more than one minimum. What matters it what cities go to which side of the kingdom. Even when simply trying all such possible combinations, it is not trivial to find them. To do so, I propose the following algorithm:

How to find all possible divisions

• For each pair of cities x and y, the line connecting them, divides the kingdom in "left" and "right". Then consider all possible combinations of left, right, x and y:

  • left + x + y vs right (C)
  • left + x vs right + y (A)
  • left + y vs right + x (D)
  • left vs right + x + y (B)

Actually I am not 100% sure but I think in this way you can find all possible division with a finite number of trials. As the cities have no size (I assumed 0 radius), the line connecting x and y can be shifted slightly to include either city on either side of the kindom.

One counter example where this simple method will definitely fail is when more than 2 cities lie on a straight line

Example

This picture illustrates one step of my above algorithm for the example from the OP. x and y are the two cities with 1 inhabitants. Actually with this pair of cities one gets already all possible divisions. (However 3 points is trivial anyhow, as there is no geometrical restriction on what combinations are possible. Interestingly only starting with 4 points their location on the plane really matters.)

Colinear points

Following some discussion and fruitful comments, I came to the conclusion that colinear points are not really a problem. One just has to consider these points when evaluating the 4 possible divisions (for each pair of points). E.g. assume in the above example is another point at (-1,2). Then this point would lie on the left for A and C and on the right for B and D.

Answer 2

For each angle A, consider the family of parallel lines which make an angle of A with the x-axis, with special case A=0 corresponding to the family of lines parallel to the X-axis.

Given A, you can use a binary search to find the line in the family which divides the kingdom most nearly equally. So we have a function f from angles to integers, mapping each angle A to the minimum value of |a-b| for lines in the family corresponding to A.

How many angles do we need to try? The situation changes materially only when A is an angle corresponding to a line between two points, an angle which I will call a "jump angle". The function is continuous, and therefore constant, away from jump angles. We have to try jump angles, of which there are about n choose 2, approximately 500,000 at most. We also have to try intervals of angles between jump angles, doubling the size, to 1,000,000 at most.

Instead of angles, it's probably more sensible to use slopes. I just like thinking in terms of angles.

The time complexity of this approach is O(n^2 log n), n^2 for the number of angles, log n for the binary search. If we can learn more about the function f, it may be possible to use a faster method to minimize f than checking every possibility. For example, it seems reasonable that the minimum of f can be found at an angle not equal to a jump angle.

It may also be possible to eliminate the binary search by using the centroid of the cities. We calculate the weighted average

(a1(x1,y1) + a2(x2,y2) + ... + an(xn,yn))/(a1+a2+...+an)

I think that lines balancing the population will pass through that point. (Hmm.) If that's the case, we only have to think about angles.

Answer 3

Case where n is less than 3

The base case is where there are two cities: in which case you simple take the perpendicular line on the line that connects the two cities.

Case with three or more cities

You can discretize the tangent by taking every pair of two cities, and see the line that connects them as the direction of the infinite line.

Why this works

If you split the number of cities in two parts, there is at least one half with two or more cities. For that part, there are two points that are the closest to the border. Whether the border passes "very closely" to that line or has the same line does not matter; because a "slightly different tangent" will not swap any city (otherwise these cities were not the closest). Since we try "every border", we will eventually generate a border with the given tangent.

Example:

Say you have the following scenario:

1
\
2\ 1

With the numbers showing the values. In this case the two closest points at the border are the one at the top and the right. So we construct a line that points 45 degrees downwards. Now we use binary search to find the most optimal split: we rotate all points, order them by ascending rotated x-value, then perform binary search on the weights. The optimal one is to split it between the origin and the two other points.

Now with four points:

1    2

2    1

Here we will investigate the following lines:

\ 1\|/2 /
 \ /|\ /
----+----
 / \|/ \
/ 2/|\1 \

And this will return either the horizontal or the vertical line.

There is a single possibility - as pointed out by @Nemo that all these points are lying on the same line. In such case there is no tangent that makes sense. In that case, one can use the perpendicular tangent as well.

Pseudocode:

for v in V
    for w in V\{v}
        calculate tangent
        for tangent and perpendicular tangent
            rotate all points such that the tangent is rotated to the y-axis
            look for a rotated line in the y-direction that splits the cities optimal
return the best split found

Furthermore as nearly all geometrical approaches, this method can suffer from the fact that multiple dots are located on the same line in which case by adding a simple rotation one can either include/exclude one of the points. This is indeed a dirty hack to the problem.

This Haskell program calculates the "optimal direction" (if the above solution is correct) for a given list of points:

import Data.List

type Point = (Int,Int)
type WPoint = (Point,Int)
type Direction = Point

dirmul :: Direction -> WPoint -> Int
dirmul (dx,dy) ((xa,ya),_) = xa*dx+ya*dy

dirCompare :: Direction -> WPoint -> WPoint -> Ordering
dirCompare d pa pb = compare (dirmul d pa) (dirmul d pb)

optimalSplit :: [WPoint] -> Direction
optimalSplit pts = (-dy,dx)
    where wsum = sum $ map snd pts
          (dx,dy) = argmin (bestSplit pts wsum) $ concat [splits pa pb | pa <- pts, pb <- pts, pa /= pb]

splits :: WPoint -> WPoint -> [Direction]
splits ((xa,ya),_) ((xb,yb),_) = [(xb-xa,yb-ya),(ya-yb,xb-xa)]

bestSplit :: [WPoint] -> Int -> Direction -> Int
bestSplit pts wsum d = bestSplitScan cmp ordl 0 wsum
    where cmp = dirCompare d
          ordl = sortBy cmp pts

bestSplitScan :: ((a,Int) -> (a,Int) -> Ordering) -> [(a,Int)] -> Int -> Int -> Int
bestSplitScan _ [] l r = abs $ l-r
bestSplitScan cmp ((x1,w1):xs) l r = min (abs $ l-r) (bestSplitScan cmp (dropWhile eqf xs) (l+d) (r-d))
    where eqf = (==) EQ . cmp (x1,w1)
          d = w1+(sum $ map snd $ takeWhile eqf xs)

argmin :: (Ord b) => (a -> b) -> [a] -> a
argmin _ [x] = x
argmin f (x:xs) | (f x) <= f ax = x
                | otherwise = ax
    where ax = argmin f xs

For instance:

*Main> optimalSplit [((0,0),2),((0,1),1),((1,0),1)]
(-1,1)
*Main> optimalSplit [((0,0),2),((0,1),1),((1,0),1),((1,1),2)]
(-1,0)

So the direction is a line in which if the line moves one element to the left, it moves one element to the top as well. This is the first example. For the second case, it picks a line that moves in the x-direction so it splits horizontally. This algorithm allows only integral points and does not take into account slightly tweaking the line in case the points are placed on the same line: these are all in or all out for a line parallel.

Answer 4

[Edit: Bold-faced text is relevant to concerns expressed previously in comments.]

[Edit 2: As I should have pointed out earlier, this answer is a supplement to the earlier answer by tobi303, which gives a similar algorithm. The main purpose was to show that the basic idea of that algorithm is sound and sufficiently general. Despite minor differences in the details of the algorithms proposed in the two answers, I think a careful reading of the "why it works" section, applied to either algorithm, will show that the algorithm is in fact complete.]

If all the cities are in one straight line (including the case where there are only one or two cities), then the solution is simple. I assume you can detect and solve this case, so the rest of the answer will deal with all other cases.

If there are more than two cities and they are not all collinear, the "brute force" solution is:

for each city X, 
  for each city Y where Y is not X
    construct a directed line that passes through X and then Y.
    Divide the cities in two subsets: 
    S1 = all the cities to the left of this line
    S2 = all the other cities (including cities exactly on the line)
    Evaluate the "unfairness" of this division.

Among all subdivisions of cities found in this way, choose the one with the least unfairness. Return the difference. Done.

Note that the line found in this way is not the line that divides the cities "fairly"; it is merely parallel to some such line. If we had to find the actual dividing line we would have to do a little more work to figure out exactly where to put that parallel line. But the requested return value is merely |a-b|.

Why this works:

Suppose that the line L1 divides the cities in the fairest way possible. There is not a unique line that does this; there will be (mathematically speaking) an infinite number of lines that achieve the same "best" division, but such lines exist, and all we need to suppose is that L1 is one of those lines.

Let the city A be the closest to L1 on one side of the line and the city B be closest to L1 on the other side. (If A and B are not uniquely identified, that is if there are two or more cities on one side of L1 that are tied for "closest to L1", we can set L2 = L1 and skip forward to the procedure for L2, below.)

Consider rotations of L1 in each direction, using the point where L1 crosses the line AB as a pivot point. In at least one direction of rotation, a rotated image of L1 will "hit" one of the other cities, call it C, without touching either A or B. (This follows from the fact that the cities are not all along one line.) At that point, C is closer to the image of L1 than A or B (whichever of those cities is on the same side of the original L1 as C was). The Mean Value Theorem of calculus tells us that at some point during the rotation, C was exactly as close to the rotated image of L1 as the city A or B, whichever is on the same side of that line.

What this shows is that there is always a line L2 that divides the cities as fairly as possible, such that there are two cities, D and E, on the same side of L2 and tied for "closest city to L2" among all cities on that side of L2.

Now consider two directed lines through D and E: L3, which passes through D and then E, and L4, which passes through E and then D. The cities that are on the other side of L2 than D and E consist either of all the cities to the left of L3, or all the cities to the left of L4. (Note that this works even if L3 and L4 happen to pass through more than two cities.)

The procedure described before is simply a way to find all possible lines that could be line L3 or line L4 in any execution of this procedure starting from a line L1 that solves the problem. (Note that while there are always infinite possible choices of L1, every such L1 results in lines L3 and L4 selected from the finite set of lines that pass through two or more cities.) So the procedure will find the division of cities described by L1, which is the solution to the problem.