problem https://www.codechef.com/problems/RGPVR103
Can anyone explain in detail that hoe the answer is coming (n/4)*(n/2-n/4)
Well
First thing, when N is odd, last still is irrelevent, because we won’t be able to use that last stick to make rectangle. So just set N = N-1 if N is odd.
Now, N is even.
Second thing, now N is the perimeter of required. So, the problem is reduced to => Find rectangle with Maximum area and given perimeter N.
We know from basic maths that to maximize area while not exceeding perimeter limit, we need to make length and breadth as near equal as possible. but we cannot break stick.
So, following cases arise.
When N is a multiple of 4 => In this case, we can always make a square with side N/4 and thus, answer will be (N/4)*(N/4).
When N is not a multiple of 4 => In this case, we cannot make a square, so we make length as N/4. and breadth as N/2 - N/4.
Take an example, say N = 14.
length = N/4 = 3 (Integer division).
breadth = N/2 - N/4 = 7-3 = 4.
This way, length and breadth are as near equal as possible, thus, maximizing the area.
1 Like