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

Правка en27, от div4only, 2023-01-18 09:17:02

Problem: Rectangle Shrinking

Part 1: Notations

$$$x$$$: A brick. $$$x_i$$$ denotes the part of $$$x$$$ belonging to the $$$i$$$-th floor. For example, if $$$x.u=1,\,x.d=2$$$, then $$$x_1.u=x_1.d=1$$$, $$$x_2.u=x_2.d=2$$$, and $$$x_1.l=x_2.l=x.l$$$, $$$x_1.r=x_2.r=x.r$$$.

$$$A_i,\,i=1,2$$$: The set of bricks whose $$$u=d=i$$$.

$$$B$$$: The set of bricks whose $$$u=1,\,d=2$$$.

$$$\texttt{Remove}$$$: Remove a brick $$$x$$$.

$$$\texttt{Shrink}$$$: Shrink a brick $$$x$$$ to another non-empty brick.

$$$\texttt{Keep}$$$: Keep a brick $$$x$$$ unchanged.

Note that in our solution we may operate on a part of brick. For example, for a brick $$$x \in B$$$, we may $$$\texttt{Keep}\,x_1$$$ while $$$\texttt{Remove}\,x_2$$$.

Part 2: Idea

$$$\texttt{Shrink}$$$ing $$$x \in B$$$ is troublesome. If you shrink $$$x_1$$$, you have to shrink $$$x_2$$$ in the same way, i.e., $$$x_1$$$ has to be aligned with $$$x_2$$$. So is there a solution that only performs $$$\texttt{Remove}$$$ and $$$\texttt{Keep}$$$ on every $$$x \in B$$$? But that is impossible, because the bricks $$$x, y \in B$$$ may overlap themselves even with considering $$$A$$$. So what if $$$B$$$ are pairwise non-overlapping (because we could perform some pre-$$$\texttt{Shrink}$$$ and pre-$$$\texttt{Remove}$$$ to make $$$B$$$ pairwise non-overlapping)? [Pre-computation]

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

$$$C_i := A_i \cup \{x_i \mid x \in B \}$$$.

For example, if

$$$A_1 = \{[u=1, d=1, l=2, r=5], [u=1, d=1, l=7, r=10]\}$$$,

$$$B=\{[u=1, d=2, l=2, r=2], [u=1, d=2, l=4, r=7]\}$$$, then

$$$C_1 = \{[u=1, d=1, l=2, r=2], [u=1, d=1, l=2, r=5], [u=1, d=1, l=4, r=7], [u=1, d=1, l=7, r=10]\}$$$.

We sort $$$C_i$$$ w.r.t $$$l$$$, and traverse $$$C_i$$$ like $$$\texttt{for(auto x: C_i)}$$$.

Case 1 ($$$\texttt{Keep}$$$): If $$$x$$$ is not overlapping now, then we add $$$x$$$ to the answer, no matter if $$$x$$$ is from $$$A_i$$$ or not.

Case 2 ($$$\texttt{Remove}$$$): If $$$x$$$ is fully contained in the union of other rectangles, then we always remove $$$x$$$, no matter if $$$x$$$ is from $$$A_i$$$ or not.

$$$\texttt{Keep}$$$ and $$$\texttt{Remove}$$$ are relatively easier, no matter $$$x \in A_i$$$ or $$$x \in \{x_i \mid x \in B \}$$$.

Case 3 ($$$\texttt{Shrink}$$$): If $$$x$$$ is partially overlapping with other bricks.

Case 3.1: If $$$x \in A_i$$$: $$$\texttt{Shrink} x$$$. Move the $$$x.l$$$ to the right to avoid overlapping.

Case 3.2: If $$$x \in \{x_i \mid x \in B \}$$$: $$$\texttt{Shrink}$$$ all bricks that overlap with $$$x$$$ by moving their right endpoints (i.e., *.r), to the left.

It is guaranteed in Case 3.2 that every brick overlapping with $$$x$$$ is from $$$A_i$$$ because we have already performed pre-calculations in $$$B$$$ to make them non-overlapping. The complexity is not an issue, by amortized analysis, each $$$x \in A_i$$$ will do $$$\texttt{Remove}$$$ at most once and $$$\texttt{Remove}+\texttt{Shrink}$$$ 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 $$$\texttt{std::set}$$$. 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) $$$\texttt{Insert(l, r)}$$$: Insert an interval $$$[l, r]$$$.

(2) $$$\texttt{covered_by(l, r)}$$$: Return an interval covering $$$[l, r]$$$, if not exists, returning $$$(-\infty, \infty)$$$.

(3) $$$\texttt{covered(l, r)}$$$: Return a bool variable indication whether interval $$$[l, r]$$$ is fully covered.

(4) $$$\texttt{right(x)}$$$: Return $$$\min \{y|y \geq x, y \text{ is not covered}\}$$$. Note that API could calculate the $$$\texttt{mex}$$$, so it is also useful for calculating the Sprague-Grundy (SG) number. SG number is irrelevant to our topic.

(5) $$$\texttt{left(x)}$$$ (added by me): Return $$$\max \{y|y \leq x, y \text{ is not covered}\}$$$.

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

(6) $$$\texttt{Erase(l, r)}$$$: Erase $$$[l, r]$$$. That may lead to interval splitting, for example, if we erase $$$[2, 3]$$$ from $$$[1, 4]$$$, we get two intervals remaining: $$$[1, 1]$$$ and $$$[4, 4]$$$.

(7) $$$\texttt{size}$$$: Get the size of intervals.

(8) $$$\texttt{dump}$$$: 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 $$$C_i$$$ from each floor independently? We need another set that is sorted by $$$r$$$ in the ascending order, let's call it $$$\texttt{sortbyr}$$$, to maintain rectangles in $$$A_i \subseteq C_i$$$. If Case 3.2 happens, we need to find such $$$y \in \texttt{sortbyr}$$$ quickly by $$$\texttt{sortbyr.lower_bound(x.l)}$$$, i.e., find an interval $$$y \in A_i$$$ quickly, using binary search, such that the right endpoint of $$$y$$$ ($$$y.r$$$) is greater or equal than $$$x.l$$$. Note that when we find such an $$$y$$$, you need to iterate to the end of $$$\texttt{sortbyr}$$$, 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){
                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
}

In the above implementation, it is not possible that $$$\texttt{!lcovered && rcovered}$$$, otherwise $$$[l, r]$$$ is covered by some $$$[l_1, r_1]$$$ which $$$l_1 > l$$$. But we have already sorted $$$C_i$$$ by $$$l$$$. And, if $$$l$$$ and $$$r$$$ are both covered, we just ignore and \texttt{Remove} this segment.

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 $$$b \in B$$$. I mean, for $$$x = \{1, l, 2, r, id\} \in B$$$, the implementation might insert both $$$\{1, l, 1, r, id\}$$$ and $$$\{2, l, 2, r, id\}$$$ into $$$ans[id]$$$, 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!

Теги range-set, binary-search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en28 Английский div4only 2023-01-19 10:07:25 11
en27 Английский div4only 2023-01-18 09:17:02 8 Tiny change: 'Idea**\n\nI think $\texttt{S' -> 'Idea**\n\n$\texttt{S'
en26 Английский div4only 2023-01-18 09:13:15 0 (published)
en25 Английский div4only 2023-01-18 09:12:44 308 (saved to drafts)
en24 Английский div4only 2023-01-18 07:43:04 62 (published)
en23 Английский div4only 2023-01-18 07:37:35 947
en22 Английский div4only 2023-01-18 07:26:22 1518
en21 Английский div4only 2023-01-18 07:16:13 1038
en20 Английский div4only 2023-01-18 07:05:57 359
en19 Английский div4only 2023-01-18 07:01:15 575
en18 Английский div4only 2023-01-18 06:52:37 715
en17 Английский div4only 2023-01-18 06:45:27 415
en16 Английский div4only 2023-01-18 06:40:31 289
en15 Английский div4only 2023-01-18 06:37:21 175
en14 Английский div4only 2023-01-18 06:33:17 392
en13 Английский div4only 2023-01-18 06:28:14 54
en12 Английский div4only 2023-01-18 06:26:31 133
en11 Английский div4only 2023-01-18 06:13:39 2 Tiny change: '\in A_i$: \texttt{Shrink} $x$. Move t' -> '\in A_i$: $\texttt{Shrink} x$. Move t'
en10 Английский div4only 2023-01-18 06:13:00 695
en9 Английский div4only 2023-01-18 06:06:09 24
en8 Английский div4only 2023-01-18 06:05:37 81
en7 Английский div4only 2023-01-18 06:02:02 271
en6 Английский div4only 2023-01-18 05:57:36 345
en5 Английский div4only 2023-01-18 05:51:57 287
en4 Английский div4only 2023-01-18 05:49:42 499
en3 Английский div4only 2023-01-18 05:45:33 779
en2 Английский div4only 2023-01-18 05:45:13 779
en1 Английский div4only 2023-01-18 05:36:49 304 Initial revision (saved to drafts)