The problem was solved by: Cosmin Negruseri, Eugene Kenny, Filip Buruiana. Cosmin pointed out that this problem appears in CLRS where they give a O(n2lg n) algorithm for finding the segments. I got it from problem ANTS in NEERC 2007.
Solution 1:The dumbest possible thing I could think of is to try some random segments between white and black points and if two intersect then fix the problem by swapping their endpoints. (This could introduce other intersections, though.). So if it happens that you pick first AC and BD, you notice that they intersect, you swap them and you get AD and BC.
The problem is: If you keep doing this, are you guaranteed to terminate? Whenever you try to solve a termination problem the first thing that comes to mind is "Can I find a measure that changes monotonically and is bounded?" And, by starring at the figure you notice that the two new segments are shorter than the old ones: |AD|+|BC|<|AC|+|BD|. Is this always true? The triangle inequality in AED is |AE|+|ED|>|AD| and in BEC it is |BE|+|EC|>|BC|. If we add these two we get that indeed the new segments are always shorter. Since the sum of the lengths of all students is nonnegative the process described earlier must terminate. We are done.
What would be an algorithm to find these segments? See weighted bipartite matching. The Hungarian algorithm works in O(n3).
Solution 2: Eugene and CLRS give another solution. If you draw a few examples it becomes apparent that you can always find a segment which splits the problem in two smaller ones: on the left of it (viewed as a line) you have an equal number of whites and blacks and the same for the right, of course. Does this always happen? I'm going to give a very informal argument. Pick the left-most point and then sweep the other points with a line starting from this point. Is it possible that the first and the last points you sweep are of the same color and whenever you have an equal number of blacks and whites on the right you are sweeping thru a point of the same color? Not really. Keep track of the difference |whites on the left|-|blacks on the left|. This changes with +/-1 at each step. Suppose the first time it goes thru zero you are swapping a point of the same color. Draw this! Then you must have many points of the opposite color "to go" and therefore you'll pass again thru zero.
OK, this is not really a good explanation but I'm sick and tired (literally).
Anyway, this suggests an O(n2lg n) algorithm: Pick leftmost, sort the others by angle, sweep and keep track of the difference on the left, find a proper segment to split the problem in two. Repeat. In the worst case you do the main loop n times and the sorting takes O(n lg n). If you are lucky and you always split the problem in half then you have T(n)=2T(n/2)+O(n lg n) which, by the Master theorem, is O(n lg n) [edit, see below: actually, O(n lg2n)].
4 comments:
"by the Master theorem, is O(n lg n)"
Don't you mean O(n lg^2 n)?
It's case 3.
But f(n) = n log n is not Omega(n^(1+epsilon)) for any epsilon > 0. This fits exactly into Case 2 of master theorem with k = 1, giving a bound of O(n lg^2 n).
You are right. Sorry for not paying more attention to your first comment.
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.