RNEST(Escape from the Mines)

general
, ,
1

How to approach the problem RNEST? (http://www.codechef.com/ACMAMR12/problems/RNEST ). Naive O(n*n)
approach gets TLE. The AC solutions probably use segment trees or sweep line. Please explain how to approach the problem?

2

I used both segment trees and sweep line. First I “normalized” the y coordinates (i.e. sorted them and renumbered them from 1 to M, where M<=2*N is the number of distinct y coordinates). Then I sorted the vertical segments of the rectangles according to their x coordinate. Thus, a rectangle will appear twice in this ordering (once for its left side and once for its right side). Then I traversed the left and right sides of the rectangles in this order from left to right (basically sweeping the plane with a vertical line).

When we encounter the left side of a rectangle:

  1. We query for one of its y coordinates to find the rectangle containing it (if any)

  2. We “insert” the rectangle in the segment tree

When we encounter the right side of a rectangle we simply remove the rectangle from the segment tree.

Inserting a rectangle in a segment tree consists of the following. Take the (normalized) interval [y1,y2-1] of its y-coordinates. Find all the segment tree nodes whose union completely covers the interval. In each node of the segment tree (there are 2*N-1 nodes in such a tree) we will have a stack. We insert the rectangle id at the top of each stack (we also remember somewhere that the left side of this rectangle was the i-th in the x-sorted order).

Removing a rectangle is done in the same manner. When a rectangle is removed we just pop the topmost element of each stack from the nodes covering its y-interval. Note that it is certain that at removal time the topmost element of each of those stacks will be the considered rectangle.

Querying is performed as follows. Let’s consider the coordinate y and we want to know the “deepest” rectangle containing it (if any). We start at the segment tree leaf corresponding to the coordinate y (i.e. to the interval [y,y]) and we move up the tree until we reach the root. For each of the visited nodes we check the rectangle at the top of its stack (unless the stack is empty). From all these O(log(N)) rectangles, the “deepest” one will be the one with the largest x coordinate of its left side (i.e. the one whose left side appears last among them in the x-sorted order).

The time complexity of this solution is O(N*log(N)).

In my explanation I assumed that you know more or less what a segment tree is and how it works (e.g. I did not explain how to find the tree nodes whose union properly covers an interval [a,b], as this is a standard procedure for segment trees).

Note that the total number of elements in all the stacks of the tree will be O(N), but there may be stacks with many elements and stacks with fewer (or zero) elements, depending on the actual rectangles. In my solution I used the stack class from STL (C++).

8 Likes