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

Правка en2, от div4only, 2023-01-18 05:45:13

Problem: Rectangle Shrinking

Part 1: Notations and Terminologies

$$$x$$$: Brick. $$$x_i,\,i=1,2$$$ means the part of $$$x$$$ that lies on the $$$i$$$-th floor. For example, if $$$x.u=1, x.d=2, x.l=3, x.r=4$$$, then $$$x_1.u=x_1.d=1, x_1.l=3, x_1.r=4$$$. $$$x_2.u=x_2.d=2, x_1.l=3, x_1.r=4$$$

$$$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.

\texttt{Shrink}: Decrease the size of a brick to a non-zero number.

\texttt{Keep}: Keep a brick unmoved.

Part 2: Idea

The first observation is that bricks in $$$B$$$ are difficult to handle. For example, if you \texttt{Shrink} $$$b \in B$$$ on the first floor, you have to \texttt{Shrink} $$$b$$$ on the second floor into the same shape as that on the first floor. So, there are a lot of restrictions for set $$$B$$$. Bricks in $$$A_1, A_2$$$ are much easier to handle. Therefore, the first key idea: Is there a solution that never

Теги 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)