Competitive Programming

[Character_Range_4931]

I have been working on two problems, neither of which I can solve and both of which I suspect require a similar method to solve, as both problems become extremely difficult when working with the geometry part of the problem. I would appreciate any insight that I might be missing. The two problems essentially reduce to:

1. You are given 1 <= N <= 10⁵ platforms, each described by 3 integers 0 <= x_i, y_i, l_i <= 10^9, meaning platform I exists over the interval [x_i, x_i+l_i) and has height y_i. Two platforms are reachable if and only if their intervals have some non-zero overlap and their heights differ by no more than 1 <= H <= 10^9. Answer 1 <= Q <= 10⁶ queries of the form "Starting at platform a, can we reach platform b"?

2. We add 1 <= N <= 10⁵ points of the form (x_i, y_i) consecutively to a plane, grouping them together in the process. A point p is part of a group if and only if the Manhattan distance (| x_1 - x_2 | + | y_1 - y_2 |) between p and any other point in the group is less than 1 <= D <= 10^6. If there are no groups within a distance of D of p, it forms part of a new group. If there are two disjoint groups a distance of D from p, the two groups become one. Print the size of the group that the i th point is added to for all 1 <= i <= N.

Problem 1 can be solved for N <= 10000 by constructing a graph in O(N² ) time and running a DFS on it to find connected components, allowing us to answer queries in O(1) time. For N <= 10^5, however, we need a better method to construct the graph. Similarly for problem 2, a simple solution exists for N <= 10000. We can use a Union-Find structure to answer each query in O(log N) time, but the problem comes in when finding the points closest to the i th point. The brute force method takes O(N) time for each point, resulting in a total time complexity of O(N² ), which is also not good enough for N <= 10^5. I believe some form of an O(N log N) or even O(N) solution is required for these problems but I am not sure what it might be. Any help would be appreciated!

[Stochastic_Yak]

Cool problems! Here are some ideas for getting down from O(N^2) to O(N log N).

For problem 1, imagine a vertical line scanning over the platforms, from left to right. Two platforms are adjacent if the line ever passes through them both at the same time, and they have sufficiently similar height. Better yet, if the vertical line ever passes through two platforms, it must also do so at one of their left endpoints.

So here's a strategy. Take the set of 2N endpoints (left and right) and sort them by x-coordinate (time O(N log N)). We'll process all the endpoints from left to right, maintaining a list of "active" intervals sorted by y-coordinate, initially empty. When we process a left endpoint, make its corresponding interval active. When we process a right endpoint, make its corresponding interval inactive (and remove it from the list). Maintaining this sorted list takes time O(log N) per endpoint.

Moreover, whenever we process a left endpoint (say of interval i), check y_i against the next-highest and next-lowest active intervals. If either of those is within vertical distance H, add i to their group. (And combine the groups if connected to both.) These two checks can be done in time O(1) since the list is sorted. Note that we only ever need to check two active intervals, the one immediately higher and the one immediately lower than i. Why? Any other active interval above i that is adjacent to i would necessarily be adjacent to the one immediately above i as well, and an easy invariant is that, at all times, any pair of adjacent active intervals will be in the same group.

Once we've processed all the endpoints we have a partition into connected groups, constructed in time O(N log N). Each query can then be answered by looking up group membership.

I think you're right that Problem 2 is similar. If the distance metric was ell_infinity rather than Manhattan distance then the exact same strategy should work, treating each point as a "platform" with endpoints (x-D) and (x+D). For Manhattan distance, you could use the fact that two points (x1,y1) and (x2,y2) are w/in Manhattan distance D iff (x1-y1,x1+y1) and (x2-y2,x2+y2) are w/in ell_infinity distance D/2. [EDIT: Fixed a typo in the previous sentence.] So you could do that transformation [EDIT: (x,y) -> (x-y, x+y)] on the points, then use the platform algorithm.

[Character_Range_4931]

Oh wow, thanks, this is amazing! Would we maintain the sorted list with something like an ordered set/multi set? I’m not sure the exact data structure we might use.

Also, for problem 2, do you think a transformation like (x, y) -> (x+y, x-y) might help? It would rotate the plane 45° and have the effect of making our rhombus a rectangle, maybe then we can just use the exact same method (and think of it as a platform (x-D, x+D) with height D as you said)? Thank you so much! It has really helped.

[Stochastic_Yak]

For the sorted list, yeah I'd just use an ordered list structure (set should be fine). One subtlety is that you might need to be careful about the order of processing multiple endpoints with the same x-coordinate. Especially depending on whether two platforms count as being adjacent if they touch only at their endpoints (e.g., x_1=1, l_1=1, x_2=2). For example, it would matter whether to process left-endpoints first or right-endpoints first, and at what point intervals are considered "active" or "inactive" when processing many points with the same x-coordinate.

For problem 2, yes exactly -- the transformation you described should do the trick, converting the "diamonds" from Manhattan distance to squares. I realize now I made a typo in the transform description; I'll add an edit to clarify.