2
$\begingroup$

Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (stated in my own words) is as follows:

In each testcase you are given N (6 <= N <= 10) sticks.

Each stick has length L (1 <= L <= 20) provided. The lengths are represented by space separated integers.

Print the maximum area that can be created by forming a rectangle from these sticks.

Example input:

1 // testcase count

6 // number of sticks

1 1 2 2 3 1 // lengths

I have managed to solve this problem using brute-force method (which's complexity I didn't dare estimate), stacking multiple for loops and lots of if conditional statements.

However, I believe there must be some algorithm that would be suitable for this kind of a problem - there usually is one smart solution in those algorithm puzzles.

I tried to think of a solution for the past few days and didn't come to any meaningful conclussion.

I would greatly appreciate any suggestions - I don't need no code or ready solutions, only a hint about whether there is some algorithm that could be used here to make the solution more elegant, and with better computational complexity than a simple brute force.

EDIT

You are supposed to form 4 edges of a rectangle. Sticks can be stacked on top of each other to form a longer stick. Eg.

  • a1 = 2+2
  • a2 = 3+1
  • b1 = 1
  • b2 = 1
  • a*b = 4

The problem is to maximise the value of a*b.

$\endgroup$
  • $\begingroup$ Good question, I didn't quite precise that. Your assumption is correct. More precisely, we can stack sticks on top of each other to form a longer stick. Eg.(a1=2+2, a2=3+1, b1 = 1, b2 =1, ab = 4) $\endgroup$ – Epion Nov 14 '18 at 20:37
  • 1
    $\begingroup$ The problem is likely NP-complete (see bin packing/subset sum/partition problem), but might be solvable in pseudo-polynomial time, so a very effective solution is out the window. $\endgroup$ – Pål GD Nov 14 '18 at 20:59
  • $\begingroup$ Would you care to pay due credit to the original source of the problem? $\endgroup$ – Apass.Jack Nov 14 '18 at 22:28
0
$\begingroup$

Unfortunately this problem is NP-hard, so no computer scientist knows (or is admitting that they know! :-P) a way to solve it in time polynomial in the number of sticks. Don't feel bad about using brute-force here -- it's essentially the best you can do.

First, let's reframe the rectangle problem as a decision problem, that is, a problem to which the answer is either YES or NO:

Rectangle: Given a multiset $Y = (y_1, \dots, y_m)$ of stick lengths and an area threshold $k$, is it possible to build a rectangle from the sticks in $Y$ having area at least $k$?

Squares are optimal solutions when they exist

Before getting into the reduction, we will need a property about what a maximal solution to the Rectangle problem looks like. Under the constraint that $a+b=c$, $ab$ is maximised precisely when $a=b$, i.e., squares have uniquely maximum area among all rectangles of fixed perimeter. You can verify this by substituting $b=c-a$ into $ab$ and then differentiating w.r.t. $a$: the derivative becomes zero at $a=c/2=b$, and this is clearly a maximum since the coefficient of the $a^2$ term is negative. The practical significance of this fact is: If and only if it is possible to partition the stick lengths into 4 equal-size subsets, then the maximum-size area achievable is $s^2/16$, where $s$ is the sum of all stick lengths.

Reduction from Partition

I'll show this is NP-hard by reducing the NP-hard problem Partition to it. In Partition, we are given a multiset of $n$ integers $X=(x_1, \dots, x_n)$, and our task is to partition this multiset into two parts having equal sum.

Given an instance $X=(x_1, \dots, x_n)$ of Partition, with total sum $t=\sum x_i$, we construct an instance $Y = (y_1, \dots, y_{n+2})$ of Rectangle by taking each $x_i$ as a stick length $y_i$, and adding two more "big" sticks, $y_{n+1}$ and $y_{n+2}$, both of length $t/2$. (That is, $m=n+2$.) Finally, we set $k$ to $t^2/4$.

If the answer to the constructed Rectangle problem instance is YES, then by the maximal-square property, it must be possible to partition $Y$ into four equal-sum parts, each having sum $t/2$. Let $(A, B, C, D)$ be such a partition. Two of these four multisets must each contain a "big" stick and nothing else, since the big sticks have to go somewhere, and combining one of them with any other sticks would mean that one side exceeds $t/2$, meaning that some other side must fall short of $t/2$, meaning that the rectangle is not square and thus of size strictly less than $t^2/4$ -- a contradiction. Remove these two big sticks, leaving two remaining multisets of sticks, which must also be of equal sum (that is, also $t/2$): these two multisets represent a valid partition of the original $X$ into two equal-sum parts, showing that the answer to the original Partition instance is also YES in this case.

In the other direction, if the answer to the original Partition problem is YES, meaning that there is a way to partition $X$ into two equal-sum parts $U$ and $V$, then clearly the answer to the constructed Rectangle problem instance is also YES: We could simply use the four multisets $U$, $V$, $\{y_{n+1}\}$ and $\{y_{n+2}\}$.

Since a YES to either problem instance implies a YES to the other, it must also be that a NO to either instance implies a NO to the other: in other words, the answers to both problems are always the same. And since the Rectangle problem instance can be constructed in polynomial time from the Partition instance, any algorithm that can solve Rectangle in polynomial time could also be used as a subroutine to solve Partition (any, by extension, every other NP-hard problem) in polynomial time. Since Partition is an NP-hard problem, this implies that Rectangle is too.

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