<p><strong>A closely related problem is strongly NP-hard.</strong></p>

<p>Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.</p>

<blockquote>
  <p>Is it possible to pack $n$ squares of given widths $w_1, w_2, \dots, w_n$ into a larger square of width $W$?</p>
</blockquote>

<p>I misread the original question as a generalization of the following decision problem:</p>

<blockquote>
  <p>Is it possible to pack $n$ rectangles with given areas $a_1, a_2, \dots, a_n$ into a $H\times W$ rectangle?</p>
</blockquote>

<p>The first problem can be reduced to the second as follows: Squares with widths $w_1,\dots,w_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w_1^2, \dots, w_n^2$ into a $W\times W$ rectangle uses precisely $4\sum_i w_i$ units of ink.  (Proof: The minimum-perimeter rectangle with any given area is a square.)</p>

<p><strong>However, this reduction does <em>not</em> imply that the actual posted question is NP-hard.</strong></p>

<ol>
<li>Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin.  <a href="http://www.sciencedirect.com/science/article/pii/074373159090019L" rel="nofollow">Packing squares into a square.</a>  <em>J. Parallel and Distributed Computing</em> 10(3):271–275, 1990.</li>
</ol>

CC BY-SA 3.0
2013-04-07T21:00:21.650Z
@JeffE: but in the OP's question the areas of the rectangles are not given (there is only a bigger/smaller constraint  according to the corresponding $a_i, a_j$). But perhaps I misinterpreted it ?!?
Marzio De Biasi
CC BY-SA 3.0
2013-04-08T00:45:50.813Z
Hmm.  I interpreted $a_i$ as the _area_ of the $i$th rectangle — otherwise why use the letter $a$?  But maybe it only means the _area rank_ of the $i$th rectangle.
Jeffε
CC BY-SA 3.0
2013-04-08T06:08:11.897Z
Yes, the problem is actually about area ranks, rather than area.
Suresh Venkat
CC BY-SA 3.0
2013-04-08T09:47:04.253Z
Correct, the relations between the $a_x$ yields area rank, not area. Does your reduction still hold?
Alexandre
CC BY-SA 3.0
2013-04-07T20:45:17.483Z
2013-04-09T04:44:09.343Z
2013-04-09T04:44:09.343Z
Jeffε
<p><em>this is only a sketch of an idea. Not sure if it yields an optimal solution.</em></p>

<p>Following my comment above, the only parameter that matters is $n$, the number of rectangles. Since it isn't clear whether strict inequality matters, I'll assume that areas can be equal even if the numbers aren't, but that reverse ordering is prohibited. </p>

<p>It seems that a lower bound for the problem is $2n$, assuming you're drawing on a grid (otherwise by @JeffE's comment, the problem doesn't make sense). This is implied by the claim that each new rectangle needs at least 2 units of ink (amortized), because it can be associated with (say) its lower right hand corner, which needs to extend nontrivially. </p>

<p>Here's a scheme that yields this bound upto terms that vanish with $n$. WLOG assume that $H &lt; W$ and $n &lt; WH$. If $n = 2$, then the only solution is to draw a line of length $H$ dividing the rectangle into two parts, and it doesn't matter where you draw it. </p>

<p>Suppose now that $n &lt; H+1$. Then draw the length $H$ line to create a strip of unit "width", and then repeatedly subdivide that strip to get the desired number of pieces. It's not hard to see that the total ink used is roughly $H + n-2$. As $n$ increases, create more unit width strips and subdivide them. A quick calculation shows that as $n$ increases, you pay roughly $2H$ for each "full" strip and the last strip is negligible, yielding the bound. </p>

<p>I suspect that (a) this is not optimal and (b) this doesn't quite capture the spirit of what you need. But it does answer the question as stated. </p>

CC BY-SA 3.0
2013-04-09T13:52:19.933Z
_each new rectangle needs at least 2 units of ink (amortized)_ — As I read the problem, the cost is the sum of the perimeters of the rectangles.  In particular, if the boundaries of two rectangles overlap, you have to pay for the length of that overlap twice.  So each new rectangle needs at least **four** units of ink.
Jeffε
CC BY-SA 3.0
2013-04-09T14:53:49.900Z
@JɛﬀE: Correct!
Alexandre
CC BY-SA 3.0
2013-04-09T15:36:17.927Z
I see. that doesn't change the argument, because the upper bound calculation didn't overcount ink. However, @Alexandre's earlier comment renders this answer invalid, since my solution doesnt guarantee distinct area sizes - there may be a way to perturb it, but that would break the claim on asymptotic optimality.
Suresh Venkat
CC BY-SA 3.0
2013-04-09T20:48:47.190Z
@SureshVenkat: Sorry about my earlier comment. It was incorrect. I will revise your solution and comment asap.
Alexandre
CC BY-SA 3.0
2013-04-08T06:43:24.657Z
2013-04-08T06:43:24.657Z
Suresh Venkat
<p>Following Suresh's observation that the problem consists of splitting the W x H rectangle into N rectangles, using as little ink as possible, I experimented with some things.</p>

<p>I wrote a brute-force algorithm (<strong>p_brute_force()</strong> below) and observed a recursive pattern in the solution. The answer seemed to be breaking the W x H rectangle into two rectangles, for example W - i x H and i x H, in a way that a) obeys the constraints and b) minimizes ink for the sub-rectangles.  </p>

<p>I implemented this recursion in the <strong>p()</strong> algorithm below and, hurray, it matches the brute force answers for the tests below. I couldn't run many more tests because of the exponential time of the brute-force algorithm, but p() does seem to yield an optimal solution. I will have to think about the proof optimality, but I believe this to be the answer to the Drawing Challenge. If so, $Drawing Challenge \in P$   :)</p>

<pre><code>import itertools

mem_p = {}
def p(w, h, n):
    ident = (w, h, n)
    if ident in mem_p:
        return mem_p[ident]
    if n &lt; 1 or w &lt; 1 or h &lt; 1:
        return None
    if w * h == n:
        return n * 4
    if n == 1:
        if w &lt; h:
            return None
        return 2 * (w + h)
    ink = []
    for i in xrange(1, w):
        if i &lt; h:
            continue
        try:
            ink.append(2 * (i + h) + p(w - i, h, n - 1))
        except TypeError:
            pass
    for i in xrange(1, h):
        if i &gt; w:
            continue
        try:
            ink.append(2 * (i + w) + p(w, h - i, n - 1))
        except TypeError:
            pass
    v = None
    if ink:
        v = min(ink)
    mem_p[ident] = v
    return v


def intersect(r1, r2):
    return r1[0] &lt; r2[1] and r1[1] &gt; r2[0] and r1[2] &lt; r2[3] and r1[3] &gt; r2[2]

def x_y_tuple(r):
    x1 = r[0]
    x2 = x1 + r[2]
    y1 = r[1]
    y2 = y1 + r[3]
    return (x1, x2, y1, y2)

def line_length(c):
    return sum([2 * (v[2] + v[3]) for v in c])

def p_brute_force(W, H, N):
    r = []
    for xi in range(W):
        for yi in range(H):
            # origin = (xi, yi)
            for w in range(1, W + 1 - xi):
                #for h in range(1, H + 1 - yi):
                for h in range(1, w + 1):
                    r.append((xi, yi, w, h))
    s = []
    for c in itertools.combinations(r, N):
        valid = True
        for r1, r2 in itertools.combinations(c, 2):
            if intersect(x_y_tuple(r1), x_y_tuple(r2)):
                valid = False
                break
        if valid:
            for v in c:
                if v[0] + v[2] &gt; W or v[1] + v[3] &gt; H:
                    valid = False
                    break
            if valid:
                area = sum([v[2] * v[3] for v in c])
                if not area == W * H:
                    continue
                #print 'found a valid solution'
                #print c
                #print 'ink = ', line_length(c)
                s.append(c)
    b = sorted(s, key=lambda v: line_length(v))
    if not b:
        return None
    #print 'best solution'
    #print b[0]
    #print 'ink = ', line_length(b[0])
    return line_length(b[0])

import sys
print p(100, 100, 100)
sys.exit(0)
for i in range(1, 5):
    for j in range(1, 5):
        for k in range(1, min(5, i * j)):
            a = p(i, j, k)
            b = p_brute_force(i, j, k)
            if not a == b:
                print i, j, k
                print a, b
                print 'no match'
</code></pre>

CC BY-SA 3.0
2013-04-11T15:57:56.953Z
2013-04-11T15:57:56.953Z
Alexandre
<p>I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete. </p>

<p>I created a programming challenge type description to encourage my CS friends to have a go at it.</p>

<hr>

<p>Charlie likes to draw.</p>

<p>He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$</p>

<p>For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then  $w &gt; 0, h &gt; 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.</p>

<p>If a number $a_x &gt; a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.</p>

<p>Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.</p>

<p>What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?</p>

<pre><code>Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints: 
W and H are positive integers &lt;= 1000
N is a positive integer &lt;= W * H 
ax, where 1  &lt;= x &lt;= N, is a positive integer &lt;= 1000

Output file:
A single line containing the least units of ink Charlie can use.
</code></pre>

<p>Bonus:</p>

<p>Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).</p>

<p>Sample input file:</p>

<pre><code>2 2
4
1
1
1
1
</code></pre>

<p>Sample output file:</p>

<pre><code>16
</code></pre>

<p>Sample bonus:</p>

<pre><code>-----
| | |
-----
| | |
-----
</code></pre>

<hr>

<p>As pointed out by Marzio, here's the decision problem version:</p>

<p>Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?</p>

CC BY-SA 3.0
2013-04-06T20:07:26.173Z
Just a note: you should convert it to a decision problem, i.e. "Given a $W \times H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn?"
Marzio De Biasi
CC BY-SA 3.0
2013-04-06T20:12:05.223Z
... and a question: if $a_x = a_y$ then the dimension of the two corresponding rectangles must be equal, too?
Marzio De Biasi
CC BY-SA 3.0
2013-04-06T20:32:26.327Z
Since you don't care about the actual values of the $a_i$, a simpler version of your problem is that you want to divide a $W \times H$ grid into $n$ rectangular pieces while minimizing the total length of fencing used. If you solve this, then you merely sort the resulting rectangle areas and then assign them to the input numbers (it's easier here to assume that all numbers are distinct)
Suresh Venkat
CC BY-SA 3.0
2013-04-06T23:41:13.947Z
To me, this seems more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2013-04-07T23:34:13.393Z
Without loss of generality, for all $i$, either $a_i = a_{i-1}$ or $a_i = a_{i-1} + 1$.  Right?
Jeffε
CC BY-SA 3.0
2013-04-08T00:46:58.927Z
As literally written, the correct answer is always zero.  Given any valid solution, scaling each rectangle by 50% towards its center yields another valid solution with half as much ink.
Jeffε
CC BY-SA 3.0
2013-04-08T06:52:31.407Z
@JeffE: Perhaps the rectangles must have integer size?!? ... waiting OP clarification
Marzio De Biasi
CC BY-SA 3.0
2013-04-08T09:14:06.780Z
@MarzioDeBiasi: Will add the decision problem version. No, if $a_x = a_y$, they can have rectangles of different sizes.
Alexandre
CC BY-SA 3.0
2013-04-08T09:15:48.003Z
@SureshVenkat: Very nice observation! Will comment on your answer.
Alexandre
CC BY-SA 3.0
2013-04-08T09:43:51.133Z
@JɛﬀE: No, why would that be the case? $a_i$ and $a_(i - 1)$ are both positive integers. There's no other relation.
Alexandre
CC BY-SA 3.0
2013-04-08T09:44:43.590Z
@JɛﬀE: Zero-area rectangles are not allowed. Added clarification to question.
Alexandre
CC BY-SA 3.0
2013-04-08T10:39:12.030Z
@Alexandre: now that some details are clear, you can also consider to drop the ink minimization constraint and get a "simpler???" problem: "Given a WxH paper and a list of N area ranks, can we draw all the (integer sized) rectangles on the paper? (without ink constraints)
Marzio De Biasi
CC BY-SA 3.0
2013-04-09T21:05:27.050Z
@MarzioDeBiasi: How about I add that to the question as an easier problem?
Alexandre
CC BY-SA 3.0
2013-04-10T18:18:45.847Z
@Alexandre: I didn't think about it too much; but I don't see an easy solution to the problem even if we drop the ink minimization constraint :-)
Marzio De Biasi
<cc.complexity-theory><ds.algorithms><np-hardness>
The Drawing Challenge - a problem I made up and can't solve!
Alexandre
# The Drawing Challenge - a problem I made up and can't solve!

(Asked by: username_0 on 2013-04-06)

I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete. 
I created a programming challenge type description to encourage my CS friends to have a go at it.

Charlie likes to draw.
He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$
For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then  $w > 0, h > 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.
If a number $a_x > a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.
Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.
What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?
Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints: 
W and H are positive integers <= 1000
N is a positive integer <= W * H 
ax, where 1  <= x <= N, is a positive integer <= 1000

Output file:
A single line containing the least units of ink Charlie can use.

Bonus:
Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).
Sample input file:
2 2
4
1
1
1
1

Sample output file:
16

Sample bonus:
-----
| | |
-----
| | |
-----


As pointed out by Marzio, here's the decision problem version:
Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness
> **Comments:**
> **username_1**: Just a note: you should convert it to a decision problem, i.e. "Given a $W \times H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn?"  
> **username_1**: ... and a question: if $a_x = a_y$ then the dimension of the two corresponding rectangles must be equal, too?  
> **username_2**: Since you don't care about the actual values of the $a_i$, a simpler version of your problem is that you want to divide a $W \times H$ grid into $n$ rectangular pieces while minimizing the total length of fencing used. If you solve this, then you merely sort the resulting rectangle areas and then assign them to the input numbers (it's easier here to assume that all numbers are distinct)  
> **username_3**: To me, this seems more suitable for [cs.se].  
> **username_4**: Without loss of generality, for all $i$, either $a_i = a_{i-1}$ or $a_i = a_{i-1} + 1$.  Right?  
> **username_4**: As literally written, the correct answer is always zero.  Given any valid solution, scaling each rectangle by 50% towards its center yields another valid solution with half as much ink.  
> **username_1**: @JeffE: Perhaps the rectangles must have integer size?!? ... waiting OP clarification  
> **username_0**: @MarzioDeBiasi: Will add the decision problem version. No, if $a_x = a_y$, they can have rectangles of different sizes.  
> **username_0**: @SureshVenkat: Very nice observation! Will comment on your answer.  
> **username_0**: @JɛﬀE: No, why would that be the case? $a_i$ and $a_(i - 1)$ are both positive integers. There's no other relation.  
> **username_0**: @JɛﬀE: Zero-area rectangles are not allowed. Added clarification to question.  
> **username_1**: @Alexandre: now that some details are clear, you can also consider to drop the ink minimization constraint and get a "simpler???" problem: "Given a WxH paper and a list of N area ranks, can we draw all the (integer sized) rectangles on the paper? (without ink constraints)  
> **username_0**: @MarzioDeBiasi: How about I add that to the question as an easier problem?  
> **username_1**: @Alexandre: I didn't think about it too much; but I don't see an easy solution to the problem even if we drop the ink minimization constraint :-)  

---

## 3 answers

### Answer by username_4 on 2013-04-07. Score: 4

**A closely related problem is strongly NP-hard.**

Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.

> Is it possible to pack $n$ squares of given widths $w\_1, w\_2, \dots, w\_n$ into a larger square of width $W$?

I misread the original question as a generalization of the following decision problem:

> Is it possible to pack $n$ rectangles with given areas $a\_1, a\_2, \dots, a\_n$ into a $H\times W$ rectangle?

The first problem can be reduced to the second as follows: Squares with widths $w\_1,\dots,w\_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w\_1^2, \dots, w\_n^2$ into a $W\times W$ rectangle uses precisely $4\sum\_i w\_i$ units of ink. (Proof: The minimum-perimeter rectangle with any given area is a square.)

**However, this reduction does *not* imply that the actual posted question is NP-hard.**

1. Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. [Packing squares into a square.](http://www.sciencedirect.com/science/article/pii/074373159090019L) *J. Parallel and Distributed Computing* 10(3):271–275, 1990.

> **Comments:**
> **username_1**: @JeffE: but in the OP's question the areas of the rectangles are not given (there is only a bigger/smaller constraint  according to the corresponding $a_i, a_j$). But perhaps I misinterpreted it ?!?  
> **username_4**: Hmm.  I interpreted $a_i$ as the _area_ of the $i$th rectangle — otherwise why use the letter $a$?  But maybe it only means the _area rank_ of the $i$th rectangle.  
> **username_2**: Yes, the problem is actually about area ranks, rather than area.  
> **username_0**: Correct, the relations between the $a_x$ yields area rank, not area. Does your reduction still hold?  

---

### Answer by username_2 on 2013-04-08. Score: 1

*this is only a sketch of an idea. Not sure if it yields an optimal solution.*

Following my comment above, the only parameter that matters is $n$, the number of rectangles. Since it isn't clear whether strict inequality matters, I'll assume that areas can be equal even if the numbers aren't, but that reverse ordering is prohibited.

It seems that a lower bound for the problem is $2n$, assuming you're drawing on a grid (otherwise by @JeffE's comment, the problem doesn't make sense). This is implied by the claim that each new rectangle needs at least 2 units of ink (amortized), because it can be associated with (say) its lower right hand corner, which needs to extend nontrivially.

Here's a scheme that yields this bound upto terms that vanish with $n$. WLOG assume that $H < W$ and $n < WH$. If $n = 2$, then the only solution is to draw a line of length $H$ dividing the rectangle into two parts, and it doesn't matter where you draw it.

Suppose now that $n < H+1$. Then draw the length $H$ line to create a strip of unit "width", and then repeatedly subdivide that strip to get the desired number of pieces. It's not hard to see that the total ink used is roughly $H + n-2$. As $n$ increases, create more unit width strips and subdivide them. A quick calculation shows that as $n$ increases, you pay roughly $2H$ for each "full" strip and the last strip is negligible, yielding the bound.

I suspect that (a) this is not optimal and (b) this doesn't quite capture the spirit of what you need. But it does answer the question as stated.

> **Comments:**
> **username_4**: _each new rectangle needs at least 2 units of ink (amortized)_ — As I read the problem, the cost is the sum of the perimeters of the rectangles.  In particular, if the boundaries of two rectangles overlap, you have to pay for the length of that overlap twice.  So each new rectangle needs at least **four** units of ink.  
> **username_0**: @JɛﬀE: Correct!  
> **username_2**: I see. that doesn't change the argument, because the upper bound calculation didn't overcount ink. However, @Alexandre's earlier comment renders this answer invalid, since my solution doesnt guarantee distinct area sizes - there may be a way to perturb it, but that would break the claim on asymptotic optimality.  
> **username_0**: @SureshVenkat: Sorry about my earlier comment. It was incorrect. I will revise your solution and comment asap.  

---

### Answer by username_0 on 2013-04-11. Score: 0

Following Suresh's observation that the problem consists of splitting the W x H rectangle into N rectangles, using as little ink as possible, I experimented with some things.
I wrote a brute-force algorithm (p_brute_force() below) and observed a recursive pattern in the solution. The answer seemed to be breaking the W x H rectangle into two rectangles, for example W - i x H and i x H, in a way that a) obeys the constraints and b) minimizes ink for the sub-rectangles.  
I implemented this recursion in the p() algorithm below and, hurray, it matches the brute force answers for the tests below. I couldn't run many more tests because of the exponential time of the brute-force algorithm, but p() does seem to yield an optimal solution. I will have to think about the proof optimality, but I believe this to be the answer to the Drawing Challenge. If so, $Drawing Challenge \in P$   :)
import itertools

mem_p = {}
def p(w, h, n):
    ident = (w, h, n)
    if ident in mem_p:
        return mem_p[ident]
    if n < 1 or w < 1 or h < 1:
        return None
    if w * h == n:
        return n * 4
    if n == 1:
        if w < h:
            return None
        return 2 * (w + h)
    ink = []
    for i in xrange(1, w):
        if i < h:
            continue
        try:
            ink.append(2 * (i + h) + p(w - i, h, n - 1))
        except TypeError:
            pass
    for i in xrange(1, h):
        if i > w:
            continue
        try:
            ink.append(2 * (i + w) + p(w, h - i, n - 1))
        except TypeError:
            pass
    v = None
    if ink:
        v = min(ink)
    mem_p[ident] = v
    return v


def intersect(r1, r2):
    return r1[0] < r2[1] and r1[1] > r2[0] and r1[2] < r2[3] and r1[3] > r2[2]

def x_y_tuple(r):
    x1 = r[0]
    x2 = x1 + r[2]
    y1 = r[1]
    y2 = y1 + r[3]
    return (x1, x2, y1, y2)

def line_length(c):
    return sum([2 * (v[2] + v[3]) for v in c])

def p_brute_force(W, H, N):
    r = []
    for xi in range(W):
        for yi in range(H):
            # origin = (xi, yi)
            for w in range(1, W + 1 - xi):
                #for h in range(1, H + 1 - yi):
                for h in range(1, w + 1):
                    r.append((xi, yi, w, h))
    s = []
    for c in itertools.combinations(r, N):
        valid = True
        for r1, r2 in itertools.combinations(c, 2):
            if intersect(x_y_tuple(r1), x_y_tuple(r2)):
                valid = False
                break
        if valid:
            for v in c:
                if v[0] + v[2] > W or v[1] + v[3] > H:
                    valid = False
                    break
            if valid:
                area = sum([v[2] * v[3] for v in c])
                if not area == W * H:
                    continue
                #print 'found a valid solution'
                #print c
                #print 'ink = ', line_length(c)
                s.append(c)
    b = sorted(s, key=lambda v: line_length(v))
    if not b:
        return None
    #print 'best solution'
    #print b[0]
    #print 'ink = ', line_length(b[0])
    return line_length(b[0])

import sys
print p(100, 100, 100)
sys.exit(0)
for i in range(1, 5):
    for j in range(1, 5):
        for k in range(1, min(5, i * j)):
            a = p(i, j, k)
            b = p_brute_force(i, j, k)
            if not a == b:
                print i, j, k
                print a, b
                print 'no match'


---

