Editorial for TLE '16 Contest 4 P2 - Shepherding

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.

Author: ZQFMGB12

This is a somewhat tricky math problem. There are two key observations necessary to solve this problem fully. The first is that the perimeter of a rectangle with a rectangular corner missing is equal to the perimeter of the original rectangle.

For 40% of the points, we try every single possible rectangle dimension that is no greater than R by C to find a minimum-perimeter rectangle with an area that is at least K.

Time complexity: \mathcal{O}(RC)

For 70% of the points, let a rectangle's dimension be a value between 1 to R. Then the other dimension can be calculated by division and rounding up. If the other dimension is equal to or less than C, then this rectangle will fit in the grid and should be considered as a possible answer.

Time complexity: \mathcal{O}(R), although an optimization allows for \mathcal{O}(\min(R,C))

In another approach, we make another key observation, which is that the sheep should all fit in the smallest s\cdot s rectangle or s\cdot (s+1) rectangle, if possible. The proof is as follows:

Suppose we have a rectangle with dimensions w and l, w \le l. If we increase w by 1, then the area increases by 1\cdot l. If we increase l by 1, the area increases by 1\cdot w. Since w \le l, it is always better to increase w by 1 in order to maximize area. This is true even if the area needs to be increased multiple times.

If there is only 1 sheep, only a unit square (1 by 1 square) is sufficient to surround the sheep with minimum perimeter. Now, suppose we have a square with dimensions k by k. If we increase one dimension once, the most optimal solution is to form a rectangle with dimensions k by k+1. If we repeat this process, we will form a square with dimensions k+1 by k+1. From this, we show by induction that the optimal rectangle (fits the most area with minimal perimeter) is in the form of s\cdot s or s\cdot (s+1).

Be wary that if a square with a side length \min(R,C) has less area than K, it is not possible to form a larger square, and thus, the width of the desired rectangle should be equal to \min(R,C).

For 70% of the points, we follow this proof by starting from a unit square and gradually increasing the sides one at a time until the area of the rectangle is at least K.

Time complexity: \mathcal{O}(\min(R,C))

For 100% of the points, we optimize the proof shown above. We find the dimensions of the smallest square with an area of at least K by using the square root function. Suppose that this square has dimensions x by x. We then must check if the rectangle with dimensions x by x-1 has an area of at least K as well. Be careful to check if this rectangle does not fit in the R by C grid.

Time complexity: \mathcal{O}(1)


There are no comments at the moment.