Editorial for TLE '16 Contest 4 P2 - Shepherding
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 by
to find a minimum-perimeter rectangle with an area that is at least
.
Time complexity:
For 70% of the points, let a rectangle's dimension be a value between to
. Then the other dimension can be calculated by division and rounding up. If the other dimension is equal to or less than
, then this rectangle will fit in the grid and should be considered as a possible answer.
Time complexity: , although an optimization allows for
In another approach, we make another key observation, which is that the sheep should all fit in the smallest rectangle or
rectangle, if possible. The proof is as follows:
Suppose we have a rectangle with dimensions and
,
. If we increase
by
, then the area increases by
. If we increase
by
, the area increases by
. Since
, it is always better to increase
by
in order to maximize area. This is true even if the area needs to be increased multiple times.
If there is only sheep, only a unit square (
by
square) is sufficient to surround the sheep with minimum perimeter. Now, suppose we have a square with dimensions
by
. If we increase one dimension once, the most optimal solution is to form a rectangle with dimensions
by
. If we repeat this process, we will form a square with dimensions
by
. From this, we show by induction that the optimal rectangle (fits the most area with minimal perimeter) is in the form of
or
.
Be wary that if a square with a side length has less area than
, it is not possible to form a larger square, and thus, the width of the desired rectangle should be equal to
.
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 .
Time complexity:
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 by using the square root function. Suppose that this square has dimensions
by
. We then must check if the rectangle with dimensions
by
has an area of at least
as well. Be careful to check if this rectangle does not fit in the
by
grid.
Time complexity:
Comments