<p>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).</p>

<p>It definitely feels like this argument can be pushed even further... </p>

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

<p><em>Lower bound</em>. 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}$.</p>

CC BY-SA 3.0
2015-02-08T04:42:06.727Z
2015-02-08T05:04:58.407Z
2015-02-08T05:04:58.407Z
Sariel Har-Peled
<blockquote>
  <p>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.</p>
</blockquote>

<p>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...</p>

<p>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).</p>

<hr>

<p>Solution: <br />
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. <br />
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}}$.</p>

<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.</p>

<p>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$.</p>

<pre><code>set A[i] = 2*(i+1)
for i in (1, 1KK) :
    while j &lt;= 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
</code></pre>

<p>If we have this table, we can easily answer to above question. And rest of algorithm is easy. <br />
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 &lt; \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 &gt; 10^6$ we are assuming that such pair of rectangles is incorrect and we are taking the next value of $x_1$.<br />
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.</p>

<p>Pseudocode (skipping all special cases, and small input):</p>

<pre><code>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
</code></pre>

<p>My live <a href="http://pastebin.com/c9VPL5dH" rel="nofollow"><strong>C++ code</strong></a> (100/100 points). <br />
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}$?</p>

<p>Thank you for any advices!</p>

<hr>

<p>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 &gt; 14$).</p>

CC BY-SA 3.0
2015-02-07T01:45:32.223Z
1. Given the area $\alpha$, factoring $\alpha$ will help you find the integer rectangle whose perimeter is smallest.  2. I suspect the large rectangle will be approximately square.  (For instance, if $x_1,y_1$ is the large rectangle, maybe you could enumerate pairs $(x_1,y_1)$ in order of increasing value of $x_1-y_1$, and stop long before you've enumerated all pairs.)  3. You can also formulate this as the problem of minimizing $a+c$ such that $a^2-b^2+c^2-d^2=\mathcal{P}$ and $0\le b < a$, $0 \le d<c$.  (Take $a=(x_1+y_2)/2$, $b=(x_1-y_1)/2$, etc.)  Does any of this help?
D.W.
CC BY-SA 3.0
2015-02-07T02:33:13.737Z
@D.W. 1. I was thinking about it, but it is too slow if we have to check lot of areas. Even in my code is function 'best_perimeter', which works analogously in $\mathrm{O}(\sqrt{\mathcal{P}'})$. It works very fast, for $\mathcal{P}' \approx 10^{18}$ too, but inadequately for lot of numbers. 2. I'm not sure, if I understood, but if, I'm not sure if it will be helpful. Generating all pairs and sorting will kill our computing time (through constant). 3. It looks interesting. I need time to think about it (here is 3:30 a.m.), If I get something I'll describe it. Thank you  for you suggestions.
Tacet
CC BY-SA 3.0
2015-02-07T06:59:03.803Z
You can enumerate pairs $(x_1,y_1)$ in order of increasing value of $x_1-y_1$ without generating all possible pairs and sorting them.
D.W.
CC BY-SA 3.0
2015-02-07T13:44:27.157Z
If the problem were to find only one rectangle instead of two, then this would be as hard as factoring. I see little chance for the problem to be easier with two rectangles, though I don't see a direct reduction.
domotorp
CC BY-SA 3.0
2015-02-07T15:16:44.650Z
@domotorp: but factoring *xy* is easy if you have a small bound on $|x-y|$. And here you probably do (assuming primes are reasonably randomly distributed).
Peter Shor 
CC BY-SA 3.0
2015-02-07T16:01:45.303Z
@domotorp This solution supposedly is correct and have less calculations than factoring $\mathcal{P}$. $10^6$ preprocessed values in $\sum_{i=2}^{10^6}\frac{10^6}{i} \approx 10^7$ operations, and $10^6$ for each question is much less than $\sqrt{\mathcal{P}}$ for $\mathcal{P} \approx 10^{18}$. So if it is absolutely correct, that problem has to be easier.
Tacet
CC BY-SA 3.0
2015-02-07T19:51:04.347Z
I'm voting to close this question as off-topic because it appears to be a high-school mathematics question, not a research-level question in theoretical computer science.  I suggest migration to math.SE.
Jeffε
CC BY-SA 3.0
2015-02-07T19:59:08.353Z
@J: I think it is on topic, related to the complexity of factoring, though the motivation is indeed a high-school problem.
domotorp
CC BY-SA 3.0
2015-02-07T20:35:43.210Z
Is it true that for any $n$ there are $n-\log n\le x,y\le n+\log n$ such that $0\le n-xy\le \log n$? If yes, then we know that there is always a solution whose perimeter is at most $2\sqrt n + \log^2 n$ and we can use an effective brute force search to find it.
domotorp
CC BY-SA 3.0
2015-02-07T21:37:22.153Z
@domotorp I don't think it may be true. For minimal $x,y$, $n \geq 3 \Rightarrow n - xy < 0$. Did you think about $x,y$ such that $ \sqrt{n} - \log n \leq x, y \leq \sqrt{n} + \log n$? But I still don't get, what that can give us. What here is $n$?
Tacet
CC BY-SA 3.0
2015-02-07T21:50:21.120Z
@JɛﬀE I wasn't sure where should I post my question, I was thinkin about math.SE and cs.SE but I came to the conclusion that here will be better place, cause on mathSE question should be limited to prove: $$(\forall \mathcal{P})(\exists x_1 \in \left[\sqrt{\mathcal{P}} - 10^6; \sqrt{\mathcal{P}})\right)(\exists x_2,y_2)(y_1 = \lfloor\frac{\mathcal{P}}{x_1} \rfloor)$$
eventually changing $10^6$ to $G$ and asking about value of $G$ and I have no proof and 
mathematical reasoning, furthermore this question is more extensive. However, I understand you, if I misjudged my question, sorry.
Tacet
CC BY-SA 3.0
2015-02-07T22:11:54.057Z
Sorry, indeed I meant $\sqrt n$ in that inequality and you should use it for $\mathcal P=n$ (not sure why you picked such a strange variable). Then it would be useful as if for the sides $x,y$ of none of the rectangles $n-\log^2 n\le x,y\le n+\log^2$ holds, then the sum of the perimeters is necessarily more than $2\sqrt n + \log^2 n$, thus we don't have to search outside this range.
domotorp
CC BY-SA 3.0
2015-02-08T12:37:53.557Z
I think this is clearly on-topic. Maybe it came from a high-school programming competition, but there are interesting number-theoretic issues related to this.
Peter Shor 
<ds.algorithms><nt.number-theory>
Two rectangles whose sum of areas is given
Tacet
# Two rectangles whose sum of areas is given

(Asked by: username_0 on 2015-02-07)

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$).

**Tags:** ds.algorithms, nt.number-theory

> **Comments:**
> **username_1**: 1. Given the area $\alpha$, factoring $\alpha$ will help you find the integer rectangle whose perimeter is smallest.  2. I suspect the large rectangle will be approximately square.  (For instance, if $x_1,y_1$ is the large rectangle, maybe you could enumerate pairs $(x_1,y_1)$ in order of increasing value of $x_1-y_1$, and stop long before you've enumerated all pairs.)  3. You can also formulate this as the problem of minimizing $a+c$ such that $a^2-b^2+c^2-d^2=\mathcal{P}$ and $0\le b < a$, $0 \le d<c$.  (Take $a=(x_1+y_2)/2$, $b=(x_1-y_1)/2$, etc.)  Does any of this help?  
> **username_0**: @username_1 1. I was thinking about it, but it is too slow if we have to check lot of areas. Even in my code is function 'best_perimeter', which works analogously in $\mathrm{O}(\sqrt{\mathcal{P}'})$. It works very fast, for $\mathcal{P}' \approx 10^{18}$ too, but inadequately for lot of numbers. 2. I'm not sure, if I understood, but if, I'm not sure if it will be helpful. Generating all pairs and sorting will kill our computing time (through constant). 3. It looks interesting. I need time to think about it (here is 3:30 a.m.), If I get something I'll describe it. Thank you  for you suggestions.  
> **username_1**: You can enumerate pairs $(x_1,y_1)$ in order of increasing value of $x_1-y_1$ without generating all possible pairs and sorting them.  
> **username_2**: If the problem were to find only one rectangle instead of two, then this would be as hard as factoring. I see little chance for the problem to be easier with two rectangles, though I don't see a direct reduction.  
> **username_3**: @username_2: but factoring *xy* is easy if you have a small bound on $|x-y|$. And here you probably do (assuming primes are reasonably randomly distributed).  
> **username_0**: @username_2 This solution supposedly is correct and have less calculations than factoring $\mathcal{P}$. $10^6$ preprocessed values in $\sum_{i=2}^{10^6}\frac{10^6}{i} \approx 10^7$ operations, and $10^6$ for each question is much less than $\sqrt{\mathcal{P}}$ for $\mathcal{P} \approx 10^{18}$. So if it is absolutely correct, that problem has to be easier.  
> **username_4**: I'm voting to close this question as off-topic because it appears to be a high-school mathematics question, not a research-level question in theoretical computer science.  I suggest migration to math.SE.  
> **username_2**: @J: I think it is on topic, related to the complexity of factoring, though the motivation is indeed a high-school problem.  
> **username_2**: Is it true that for any $n$ there are $n-\log n\le x,y\le n+\log n$ such that $0\le n-xy\le \log n$? If yes, then we know that there is always a solution whose perimeter is at most $2\sqrt n + \log^2 n$ and we can use an effective brute force search to find it.  
> **username_0**: @username_2 I don't think it may be true. For minimal $x,y$, $n \geq 3 \Rightarrow n - xy < 0$. Did you think about $x,y$ such that $ \sqrt{n} - \log n \leq x, y \leq \sqrt{n} + \log n$? But I still don't get, what that can give us. What here is $n$?  
> **username_0**: @JɛﬀE I wasn't sure where should I post my question, I was thinkin about math.SE and cs.SE but I came to the conclusion that here will be better place, cause on mathSE question should be limited to prove: $$(\forall \mathcal{P})(\exists x_1 \in \left[\sqrt{\mathcal{P}} - 10^6; \sqrt{\mathcal{P}})\right)(\exists x_2,y_2)(y_1 = \lfloor\frac{\mathcal{P}}{x_1} \rfloor)$$ eventually changing $10^6$ to $G$ and asking about value of $G$ and I have no proof and  mathematical reasoning, furthermore this question is more extensive. However, I understand you, if I misjudged my question, sorry.  
> **username_2**: Sorry, indeed I meant $\sqrt n$ in that inequality and you should use it for $\mathcal P=n$ (not sure why you picked such a strange variable). Then it would be useful as if for the sides $x,y$ of none of the rectangles $n-\log^2 n\le x,y\le n+\log^2$ holds, then the sum of the perimeters is necessarily more than $2\sqrt n + \log^2 n$, thus we don't have to search outside this range.  
> **username_3**: I think this is clearly on-topic. Maybe it came from a high-school programming competition, but there are interesting number-theoretic issues related to this.  

---

## 1 answers

### Answer by username_5 on 2015-02-08. Score: 4 | Accepted answer

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}$.


---

