Editorial for IOI '05 P1 - Garden - DMOJ: Modern Online Judge

Editorial for IOI '05 P1 - Garden

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let us call a rectangular region containing exactly $k$ ~k~ roses a $k$ ~k~-rectangle. Let us also denote by $r_{x,y}$ ~r_{x,y}~ the number of roses in the square $(x,y)$ ~(x,y)~. The problem is to find two disjoint $k$ ~k~-rectangles with minimal sum of perimeters.

The simplest solution is to consider all possible rectangular regions of the garden, and for each of them to count the number of roses inside. This way we can enumerate all $k$ ~k~-rectangles in $\mathcal O(w^3 l^3)$ ~\mathcal O(w^3 l^3)~ time. There may be up to $\mathcal O(w^2 l^2)$ ~\mathcal O(w^2 l^2)~ $k$ ~k~-rectangles in total. The second step is to consider all the pairs of $k$ ~k~-rectangles and choose the one consisting of disjoint regions with minimum sum of perimeters. Such a solution should receive about $50\%$ ~50\%~ points, despite its terrible time complexity of $\mathcal O(w^4 l^4)$ ~\mathcal O(w^4 l^4)~.

Model solution

Now we will present a number of gradual improvements, which will finally yield us the model solution. Please note, that we can optimize checking if a given rectangular region is a $k$ ~k~-rectangle. Let us denote by $R_{x,y}$ ~R_{x,y}~ the number of roses in a region, with one corner at $(1,1)$ ~(1,1)~ and the opposite one at $(x,y)$ ~(x,y)~. We can precompute all the values of $R_{x,y}$ ~R_{x,y}~ iteratively in $\mathcal O(wl)$ ~\mathcal O(wl)~ time using the following formula:

$\displaystyle R_{x,y} = \begin{cases} 0 & \text{if }x = 0\text{ or }y = 0 \\ R_{x-1,y}+R_{x,y-1}-R_{x-1,y-1}+r_{x,y} & \text{otherwise} \end{cases}$

Having this, we can express $\mathcal R(x_1,y_1,x_2,y_2)$ ~\mathcal R(x_1,y_1,x_2,y_2)~ — the number of roses in a rectangular region with corners $(x_1,y_1)$ ~(x_1,y_1)~ and $(x_2,y_2)$ ~(x_2,y_2)~ as:

$\displaystyle \mathcal R(x_1,y_1,x_2,y_2) = R_{x_2,y_2}-R_{x_2,y_1-1}-R_{x_1-1,y_2}+R_{x_1-1,y_1-1}$

This way, $\mathcal R(x_1,y_1,x_2,y_2)$ ~\mathcal R(x_1,y_1,x_2,y_2)~ can be evaluated in $\mathcal O(1)$ ~\mathcal O(1)~ time. Using the presented method, we can enumerate all $k$ ~k~-rectangles in $\mathcal O(w^2 l^2)$ ~\mathcal O(w^2 l^2)~ time. Unfortunately, this does not solve the problem of considering all pairs of $k$ ~k~-rectangles.

But fortunately, there is another method, which copes with this problem. Please observe, that if we have two disjoint rectangular regions, then there must exist either a horizontal or a vertical line such that one rectangle is above it (or respectively to the left) and the other one is below it (or respectively to the right). Hence, for each horizontal line we can find two $k$ ~k~-rectangles with the smallest perimeters, laying on the opposite sides of the line. Similar values are to be found for all vertical lines. When we have done this, we can easily compute the final result in $\mathcal O(w+l)$ ~\mathcal O(w+l)~ by considering all the possible dividing lines and choosing the result which gives us the optimal sum of perimeters.

Now we will show how to find optimal perimeters for the first case (rectangular regions above the given horizontal line). The three other cases can be solved analogously. Let us denote by $A_y$ ~A_y~ the minimal perimeter of $k$ ~k~-rectangle laying above the horizontal line with the given $y$ ~y~-coordinate, whose bottommost coordinate is greater than or equal $y$ ~y~. Let us also denote by $a_y$ ~a_y~ the minimal perimeter of the $k$ ~k~-rectangle with bottommost coordinate equal $y$ ~y~. Please note, that:

$\displaystyle A_y = \min(a_y, \dots, a_w)$

A simple way to calculate $a_i$ ~a_i~'s is to initially set them to infinity, and then update them while iterating through all $k$ ~k~-rectangles. With this improvement, our algorithm works in $\mathcal O(w^2 l^2)$ ~\mathcal O(w^2 l^2)~ time.

This is not all. Please note, that we do not need to consider all $k$ ~k~-rectangles. We can limit our considerations to those $k$ ~k~-rectangles, which do not contain any other $k$ ~k~-rectangles in their interiors. To enumerate all interesting $k$ ~k~-rectangles (and maybe some not interesting too), we consider all pairs $(y_1,y_2)$ ~(y_1,y_2)~, $1 \le y_1 \le y_2 \le w$ ~1 \le y_1 \le y_2 \le w~. For each such pair, we use a sliding window, which is a rectangle having corners at $(x_1,y_1)$ ~(x_1,y_1)~ and $(x_2,y_2)$ ~(x_2,y_2)~. At the beginning, $x_1 = x_2 = 1$ ~x_1 = x_2 = 1~. Then we repeatedly move the sliding window according to the following rules, until $x_2 > l$ ~x_2 > l~:

if there are exactly $k$ ~k~ roses in the sliding window (i.e. $\mathcal R(x_1,y_1,x_2,y_2) = k$ ~\mathcal R(x_1,y_1,x_2,y_2) = k~), then we have found a new $k$ ~k~-rectangle; after updating the four constructed sequences ( $a_i$ ~a_i~ and the three other analogous sequences), $x_1$ ~x_1~ is incremented by one,
if $\mathcal R(x_1,y_1,x_2,y_2) < k$ ~\mathcal R(x_1,y_1,x_2,y_2) < k~ then $x_2$ ~x_2~ is incremented by one, to expand the sliding window,
if $\mathcal R(x_1,y_1,x_2,y_2) > k$ ~\mathcal R(x_1,y_1,x_2,y_2) > k~ then $x_1$ ~x_1~ is incremented by one, to shrink the sliding window,

The above algorithm works in $\mathcal O(w^2 l)$ ~\mathcal O(w^2 l)~ time, and enumerates (among others) all interesting $k$ ~k~-rectangles. Of course, we can reduce its running time to $\mathcal O(wl \min(w,l))$ ~\mathcal O(wl \min(w,l))~ by adapting the direction, in which this method works.

The presented solution, with all the above optimizations, constitutes the model solution.

Comments

There are no comments at the moment.