5

We are given N (N <= 106) points on a 2D plane and an integer D (N <= 106), we want to find two points p1,p2 (p2 to the right of p1) such that the difference between p1.y and p2.y is at least D and p2.x - p1.x is minimized.

The x and y axis are in the range 0..106

This is a problem from a USACO past contest.

Here is my attempt to solve it:
MAXY = The maximum y axis among the N points.
Suppose we know p1, then we can find p2 quite easily; by taking all the points which have their y-axis in the range p1.y+D to MAXY or in the range 0 to p1.y-D and take the point which has the smallest x-axis greater than p.x. This will be the best choice for p2.

But as we don't know p1, we will have to try all points for p1 and so finding the best choice for p2 should be done efficiently.

I used a segment tree for that. Every node in the tree will store all the points in the corresponding range in sorted order of x-axis. While querying, if a node falls in the query range then we binary search on the array for p1.x and return the smallest element greater than it.

For every choice of p1, we query the tree twice with the ranges 0,p1.y-D and p1.y+D,MAXY and take the best of the two points returned.

The building of the tree can be done in O(NlogN) time. Every query will take O(logN*logN) time, and we make N queries, so the total time taken is (Nlogn*logn) which might not run within the time limits of 2 seconds. (106*20*20). Also the memory taken will be O(NlogN) which is about 80 mb (100000*20*4 kb) which is too much as the limit is 64 mb.

How can we do the queries faster and using lesser space?

2147483647
  • 1,177
  • 3
  • 13
  • 33

2 Answers2

5

It can be done much easier.

Suppose you have two copies of the array: one sorted by Y-axis and another by X-axis. Now you'll iterate through the Y-sorted array and for each point (let name it cur) you should binary search an appropriate point (with the smallest p2.x - p1.x) in the X-sorted array. In case of binary search will find the same point or the point with Y-coordinate less than cur+D you should just delete that point from X-sorted array (we'll never need that point in X-sorted array again because we only increase Y-coordinate) and run binary search again. The answer will be the smallest of the binary search results.

As we need fast timing we should erase points from array quickly. It can be done by using binary tree - it can erase any node in O(logN) time and can do binary search in O(logN) time. As you delete each node from the tree only once and it takes O(logN + logN) time - total time will be O(N * logN). Preprocesssing time is O(N * logN) too. Also the memory taken will be O(N).

By the way your solution is also appropriate because actual N is 10^5 not 10^6. Which allows your solution to keep timing below 2 seconds, and to use less than 20MB of memory.

Mikhail Melnik
  • 966
  • 9
  • 19
  • Yes you are right N < 10^5, but your solution is much more smarter than using segment trees. – 2147483647 Sep 06 '13 at 02:23
  • @A.06 and Mikhail, if I have the points `[(1,1),(2,2),(3,3),(5,5)]` and `D = 3`. Wouldn't the first binary search delete the point, `(2,2)`, which is needed for the solution? – גלעד ברקן Sep 06 '13 at 14:10
  • 1
    @groovy at first iteration it will delete points (1,1), (2,2) and (3,3) for the X-sorted array. But at the second iteration it will take point (2,2) form Y-sorted array, which we didn't clear and will find the correct answer, point (5,5). – Mikhail Melnik Sep 06 '13 at 15:39
1

How about just do Sort & Scan.

Sort by x since you want to find the minimum difference by x. It take O(N logN) time and in place.

Maintain two index i and j from the head of x.

The faster goes first, find the position of |P[i].y - P[j].y| > D

and the X = |P[i].x - P[j].x| is your first available choice.

Then updating X by moving the to index forward. Try P[i+1], scan from P[i+2] as P[j] and increase until |P[i].x - P[j].x| >= X. If there is an available new X, set this as X.

This might make do lot of compare at first. But since you updating your X, somehow will make your compare range shrinking.

BigTailWolf
  • 1,028
  • 6
  • 17
  • 1
    It is very wrong solution because you'll loose a lot of appropriate values. Consider the following test case: D=2, P[0].y=1, P[1].y=2, P[2].y=0, P[3].y=3. You'll check every point with 3, and will find the only answer points 0 and 3, however points 1 and 2 are appropriate too and it is the correct answer. – Mikhail Melnik Sep 05 '13 at 16:21
  • OK, I changed a little. See how it works. After P[0] and P[3]. Then check P[1] and P[2] and go on. – BigTailWolf Sep 05 '13 at 19:20
  • The actually performance will be much better than the worst case O(N^2) – BigTailWolf Sep 06 '13 at 16:04
  • Asymptotics is still O(N^2). It is slightly less than O(N^2) but the actual running time on huge tests will be more like some minutes not seconds. – Mikhail Melnik Sep 06 '13 at 16:41