3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Feb 7 '15 at 1:45
  • 1
    $\begingroup$ @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. $\endgroup$ – Tacet Feb 7 '15 at 2:33
  • 2
    $\begingroup$ @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). $\endgroup$ – Peter Shor Feb 7 '15 at 15:16
  • 3
    $\begingroup$ 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. $\endgroup$ – Jeffε Feb 7 '15 at 19:51
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Feb 8 '15 at 12:37
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.