Search for a minimum element in a given range greater than a given number

Question

We are given N (N <= 10 ⁶ ) points on the 2D plane and an integer D (N <= 10 ⁶ ), we want to find two points p1, p2 (p2 to the right of p1), so the difference between p1.y and p2.y not less than D and p2.x - p1.x minimized.

The x and y axis is in the range of 0.10 ⁶

This is a problem from the past USACO contest.

Here is my attempt to solve it:
MAXY = maximum y axis among N points.
Suppose we know p1, then we can easily find p2; taking all points whose y axis is in the range p1.y+D , MAXY, or in the range from 0 to p1.yD , and take the point that has the smallest x axis greater than px . This will be the best choice for p2.

But, since we do not know p1, we will have to try all the points for p1, and therefore the search for the best choice for p2 should be carried out efficiently.

I used a segment tree for this. Each node in the tree will store all the points in the corresponding range in sorted order along the x axis. When querying, if node falls into the query range, we get a binary search in the array for p1.x and return the smallest element larger than it.

For each p1 selection, we query the tree twice with ranges 0, p1.yD and p1.y + D, MAXY and take the best of the two returned points.

Tree building can be done in O (NlogN) time. Each request will take O (logN * logN) time, and we make N requests, so the total time (Nlogn * logn), which may not be executed for 2 seconds. (10 ⁶ * 20 * 20). Also, O (NlogN) memory will be made, which is about 80 mb (100000 * 20 * 4 kb), which is too large, since the limit is 64 mb.

How to make queries faster and use less space?

Answer 1

This can be made much simpler.

Suppose you have two copies of the array: one is sorted along the Y axis, and the other is sorted along the X axis. Now you will iterate over the Y-sorted array and for each point (let it be called cur) you should binary search for the corresponding point (with the smallest p2 .x-p1.x) in an X-sorted array. In the case of a binary search, it will find the same point or a point with a Y coordinate smaller than cur + D, you just need to remove this point from the X-sorted array (we no longer need this point in the X-sorted array, because we only increase Y-coordinate) and run the binary search again. The answer will be the smallest of the binary search results.

Since we need fast time, we need to quickly remove points from the array. This can be done using a binary tree - it can erase any node in O (logN) and can perform a binary search in O (logN). When you remove each node from the tree only once and the time is O (logN + logN) - the total time will be O (N * logN). The pre-processing time is also equal to O (N * logN). Also in memory will be O (N).

By the way, your solution is also suitable, because the actual N is 10 ^ 5, not 10 ^ 6. This allows your solution to save less than 2 seconds and use less than 20 MB of memory.

Answer 2

How about just sorting and scanning.

Sort by x, because you want to find the minimum difference by x. It takes time O (N logN).

Keep the two indexes i and j from chapter x.

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

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

Then update X by moving the pointer forward. Try P [i + 1], scan with P [i + 2] as P [j] and increase until | P [i] .x - P [j] .x | > = X. If there is a new X, set this as X.

This can make a lot of comparison at first. But as you update your X, somehow you will reduce your comparison range.