## Editorial for TLE '16 Contest 4 P2 - Shepherding

**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:

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