Editorial for VMSS '15 #1 - Senpai, Help Me

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

The question asks us to create the rectangle with the shortest perimeter that has an area of exactly $A$ ~A~ and with integer side lengths.

Some of you may know the equation $(a+b)(a-b) = a^2-b^2$ ~(a+b)(a-b) = a^2-b^2~. This proves that in order to optimize perimeter length to area, we want $b$ ~b~ to be as low as possible, thus the square is the most efficient rectangle perimeter to area wise. Now obviously not every area has integer square root side lengths, so we want to get it as close to the square root as possible.

To start off, let's suppose $n = \sqrt A$ ~n = \sqrt A~, and keep decrementing $n$ ~n~ until $A / n$ ~A / n~ is an integer. In other words, $A$ ~A~ is divisible by $n$ ~n~. To check for divisibility in $\mathcal O(1)$ ~\mathcal O(1)~ time, we will use the modulo (%) operator.

Final complexity: $\mathcal O(\sqrt A)$ ~\mathcal O(\sqrt A)~

Comments

There are no comments at the moment.