Click here to view the problem.
I can't come to a solution better than O(n^2) but with n<=500000 this won't work!
My Idea is to sort them by (beauty+intellect+richness) and test any of them with those after it.
Please help!
+1
A:
If you restrict the problem to two attributes (e.g. only B_i and R_i, just for illustration purposes), you can think of these attributes as points in a 2D plane. For each point (corresponding to a Lady) you'll have to count the number of points in the (semi-infinite) rectangle 'right and above' the given point.
I think a faster than O(n^2) solution would involve a range tree although I have not thought about the details. See also an illustration here.
EDIT: and you would store (or update while building) the number of points 'below' each node with the node so you can e.g. easily get the number of points below or above the splitting point of a given node.
Andre Holzner
2010-10-05 21:15:17
Wouldn't three attributes fit well into a cube? I see the O(n^3) based on your proposed solution using a cube. If you add a first pass through the data, you can gain a bounds on 'semi-infinite', I think.
Brian Stinar
2010-10-05 21:35:40
`n` is the number of points, so there are `3n` coordinate values in total. The 'canonical' solution would be to compare the three coordinates of all `n` points with those of all other `n-1` points, requiring `3*n*(n-1)/2 = O(n^2)` comparisons in total. According to the wikipedia article, the query time for a range tree is `O(log^d(n) + k)` where `k` is the number of points retrieved. I would think that one can get rid of the `+k` because one does not want to know all the coordinates of the points in question, just how many they are (which is what one can store in the tree nodes).
Andre Holzner
2010-10-05 21:54:09
Brian: The word `semi-infinite` might be misleading, you're right, in fact as the number of points is finite, all points fit into a cube.
Andre Holzner
2010-10-05 21:55:11
Thanks for the clarification. This is an interesting problem.
Brian Stinar
2010-10-05 22:00:20
+1
A:
I think you can solve this in O(n log n) by considering each lady as a point in 3-space and computing the convex hull of the points (see, e.g., here). Then, any point inside the hull is a potential suicide case.
Rafe
2010-10-06 02:19:30
Unfortunately, I think it's great... but wrong! Having slept on it, I've come up with the following counter example: (9, 0, 0), (0, 9, 0), (0, 0, 9), (1, 1, 1). The first three points plus the origin define the convex hull and the fourth point is in the interior - but alas does not define a suicidal case. Rats.
Rafe
2010-10-07 22:38:43