Rectangle Shrinking: A range-set based method, and an advertisement for CFStress...

Problem: Rectangle Shrinking

Part 1: Notations

: A brick. denotes the part of belonging to the -th floor. For example, if , then , , and , .

: The set of bricks whose .

: The set of bricks whose .

: Remove a brick .

: Shrink a brick to another non-empty brick.

: Keep a brick unchanged.

Note that in our solution we may operate on a part of brick. For example, for a brick , we may while .

Part 2: Idea

I think ing is troublesome. If you shrink , you have to shrink in the same way, i.e., has to be aligned with . So is there a solution that only performs and on every ? But that is impossible, because the bricks may overlap themselves even with considering . So what if are pairwise non-overlapping (because we could perform some pre- and pre- to make pairwise non-overlapping)? [Pre-computation]

In that case, we can consider each floor independently. Let

For example, if

, then

We sort w.r.t , and traverse like .

Case 1 (): If is not overlapping now, then we add to the answer, no matter if is from or not.

Case 2 (): If is fully contained in the union of other rectangles, then we always remove , no matter if is from or not.

and are relatively easier, no matter or .

Case 3 (): If is partially overlapping with other bricks.

Case 3.1: If : . Move the to the right to avoid overlapping.

Case 3.2: If : all bricks that overlap with by moving their right endpoints (i.e., *.r), to the left.

It is guaranteed in Case 3.2 that every brick overlapping with is from because we have already performed pre-calculations in to make them non-overlapping. The complexity is not an issue, by amortized analysis, each will do at most once and at most twice (keep/move left endpoint+keep/move right endpoint).

Part 3: Implementation

First I copy a range-set implementation from nok0. Basically, it maintains a set of intervals using . When inserting/erasing a range, it can merge/split/erase intervals automatically, using binary search (Yes, stop learning useless algorithms, go to learn binary search!). It supports many APIs, here are some useful APIs in our implementation:

(1) : Insert an interval .

(2) : Return an interval covering , if not exists, returning .

(3) : Return a bool variable indication whether interval is fully covered.

(4) : Return . Note that API could calculate the , so it is also useful for calculating the Sprague-Grundy (SG) number. SG number is irrelevant to our topic.

(5) (added by me): Return .

There are also APIs that we don't use in this implementation, but they are also beneficial:

(6) : Erase . That may lead to interval splitting, for example, if we erase from , we get two intervals remaining: and .

(7) : Get the size of intervals.

(8) : Output all intervals for debugging.

So, we implement the pre-computation step (first paragraph in Part2) as follows:

sort B w.r.t l (left endpoint).
Initial a range set named rs.
for(auto& x: B){
    int rightl = rs.right(x.l), leftr = rs.left(x.r);
    if(right <= rightr){
        rs.insert(rightl, leftr);
        for(int i = 1; i <= 2; ++i)  {
             Ci = Ai; Ci.push_back({x.u, x.rightl, x.d, x.leftr, x.id}); //push into Ci
        }
    }else{
        //Case 2, fully contained, remove it!
        //We actually do nothing here
    }
}  

Then, how to calculate from each floor independently? We need another set that is sorted by in the ascending order, let's call it , to maintain rectangles in . If Case 3.2 happens, we need to find such quickly by , i.e., find an interval quickly, using binary search, such that the right endpoint of () is greater or equal than . Note that when we find such an , you need to iterate to the end of , that's why my previous submissions WA at test15--I only handle one of them. Here is the sketch of the implementation:

for(int i = 1; i <= 2; ++i){
    Initialize sortbyr; //Remember to initialize because we handle each floor independently!
    sort(Ci.begin(), Ci.end());
    Initial a range set named rs.
    for(auto x: Ci){
         bool lcovered = rs.covered(l), rcovered = rs.covered(r);
         if(!lcovered && !rcovered){
             //Case 1, Keep
             if(u == d){
                //so
                sortbyr.insert({x.u, x.l, x.d, x.r, x.id});
             }
             ans[x.id].insert(node{j+1, x.l, j+1, x.r, x.id}); //No matter u == d or u != d, we only consider one floor here!
             rs.insert(x.l, x.r);
         }else if(lcovered && !recovered){
             if(u == d){
                 //Case 3.1
                 int rightl = rs.right(l);
                 ans[x.id].insert(x.u, x.rightl, x.d, x.r, x.id);
                 rs.insert(rightl, x.r);
                 sortbyr.insert(x.u, x.rightl, x.d, x.r, x.id});
             }else{
                 //Case 3.2
                 auto y = sortbyr.lower_bound({-1, -1, -1, x.l, -1});
                 while(y != sortbyr.end()){
                     //Here, we should deal with all overlaps! That's why my previous submissions WA on test15
                     auto [u2, l2, d2, r2, id2] = *y;
                     //Here l2 <= l because we sort Ci by l. So sortbyr only contains elements whose left endpoint <= l!
                     //By lower_bound, we have r2 >= x.l
                     ans[id2].erase({u2, l2, d2, r2, id2}); //We erase it from our answer
                     sortbyr.erase(y++);
                     ans[x.id].insert({j+1, x.l, j+1, x.r, x.id}); //We never shrink the splitted ones
                     rs.insert(x.l, x.r); //Although [l, r] overlaps with [l2, r2], range set will merge them automatically!
                     if(l2 <= l-1){ //Be careful! r2 may <= r, so y after shrinking may be empty!! 
                         ans[id2].insert({u2, l2, d2, x.l-1, id2});
                         sortbyr.insert({u2, l2, d2, x.l-1, id2});
                     }
                 }
             }//Case 3.2
         }//Case 3
    }//for
}

Finally, we need to output the answer, for this part please refer to the code. Note that due to the implementation, we may insert two parts of bricks for . I mean, for , the implementation might insert both and into , so we need to merge them manually, that is dirty work.

Here is an advertisement for CFStress: Although my previous submission WA on case5 of test15, CFStress could still find a very small counterexample in a very short time! As mentioned here, My debugging ability is really poor, so I don't use CFStress very frequently, as I often debug myself to improve my debugging ability. However, CFStress has saved me many times from insomnia. Thanks, variety-jones!