Two rectangles whose sum of areas is given

Question

Given is $\mathcal{P} \in \mathbb{Z}$. Are sought two rectangles which edges have integer, positive value and sum of their areas is $\mathcal{P}$. Find this two rectangles, if you know that sum of their perimeters is the smallest possible. If there are many possible answers, find any of them.

This question was on pre-olympic polish computer science workshops and I'm looking good, well proven solution. Below I put solution, which received maximal number of points, I believe it will help, but it is illogical (a little bit) and no one knows, why it works...

Task has limitation $\mathcal{P} \leq 10^{18}$ and was at most ten questions per actuation, but I'm interested in general solution. We had 256MB of memory and not more than 1.5 second to answer at ten questions (and pre-process).

---

Solution:
We are looking for $x_1, x_2, y_1, y_2 \in \mathbb{Z}$, such that $x_1\cdot y_1+x_2\cdot y_2 = \mathcal{P}$ and sum $x_1+x_2+y_1+y_2$ is minimal.
Let start from small observation, one of rectangles will be very small, second will be very big. If both were similar, sum will be $2 \cdot 4\sqrt{\frac{\mathcal{P}}{2}} = 4\sqrt{2\mathcal{P}}$, otherwise it is $4\sqrt{\mathcal{P}}$ from big one and something near zero from second, so sum is near $4\sqrt{\mathcal{P}}$.

In our algorithm, we will choose the largest rectangle (and big implicate small) and we will check if it is best, so far. So, we want answer question "best perimeter for area $\mathcal{P}'$" in $\mathrm{O}(1)$ time, where $\mathcal{P}'$ is small.

We can (in $\mathrm{O}(n \lg n)$ time) pre-process table $A[2..10^6]$, in which $A_i$ is best (smallest) perimeter of rectangle with area $i$.

set A[i] = 2*(i+1)
for i in (1, 1KK) :
    while j <= 1KK : 
        A[j] = min(A[j], 2*(i, j/i))
            #it is well to keep i, j/i value for best perimeter in B table
        j += i

If we have this table, we can easily answer to above question. And rest of algorithm is easy.
If $\mathcal{P}$ is small, we are using just brute-force. Otherwise we are checking all $x_1$ in range $[\sqrt{\mathcal{P}} - 10^6; \sqrt{\mathcal{P}})$, as $y_1$ we are taking biggest integer, such that $x_1\cdot y_1 < \mathcal{P}$. Now $x_2y_2$ is imposed. We are taking $x_2, y_2$ from $B$ table. $(x_2, y_2) = B_{\mathcal{P} - x_1y_1}$. If $\mathcal{P} - x_1y_1 > 10^6$ we are assuming that such pair of rectangles is incorrect and we are taking the next value of $x_1$.
If we aren't, we will calculate best second triangle in $\mathrm{O}(\sqrt{\mathcal{P}'})$, we receive TLE (Time Limit Exceeded). Unfortunately we have no time for it.

Pseudocode (skipping all special cases, and small input):

def fun(P) :
answer = inf
for i in range(sqrt(P)-1KK, sqrt(P)) :
    j = floor(P/i)
    perimeter = i + j + best_perimeter(P - (i*j))
    answer = min(answer, perimeter)
      #we have to keep somewhere size of edges of best rectangles
return answer

My live C++ code (100/100 points).
I don't fully believe in this solution. I will be glad, if someone share with me good, correct, well proved solution. Is here any good solution for any range of $\mathcal{P}$?

Thank you for any advices!

---

Example: If $\mathcal{P} = 6$, then $(x_1,y_1,x_2,y_2) = (2,2,1,2)$ is correct answer (perimeter is $14$) and $(5,1,1,1)$ is incorrect ($5 \cdot 1 + 1 \cdot 1 = 6 = \mathcal{P}$, but perimeter is equal to $16 > 14$).

Answer 1

Assume all integers involved are even. This can be ensured by multiplying $P$ by 4. Here is an idea that should speed up the search. Let $p = \left\lceil\sqrt{P}\right\rceil$. If $p*p = P$ we are done. Otherwise, let $k$ be the minimum such that $\alpha =p*p-k*k \leq P$. If $\alpha=P$, we are done as $(p-k)\times(p+k)$ is the desired solution with perimeter $$4p$$. Otherwise, clearly $1 \leq k^2 \leq 4p$ (otherwise, $p$ would be smaller). But this implies that $k \leq c*P^{1/4}$, where $c$ is some small constant. This implies that $P - \alpha \leq c'*P^{1/4}$. Thus, the solution with rectangles $$(p-k)\times(p+k) \text{ and } 1\times(P-\alpha)$$ has perimeter $4p + O(P^{1/4})$. Since $4(p-1)$ is a lower bound on the solution by the argument below (intuitively, the isoperemeteric inequality), this implies that search range is only of size $O(P^{1/4})$ (as far as the overall perimeter is concerned).

It definitely feels like this argument can be pushed even further...

And Jeff is right - this is not necessarily too interesting as far as pure theory. But it is fun...

Lower bound. Observe that if the two rectangles are $x_1\times y_1$ and $x_2\times y_2$, then the rectangle $(x_1+x_2)\times(y_1+y_2)$ must have area larger than $P$. But then, the minimum perimeter rectangle of a given area is a square. This implies that $2(x_1+x_2+y_1+y_2) \geq 4\sqrt{P}$.