The Drawing Challenge - a problem I made up and can't solve!

Question

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?

Answer 1

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. J. Parallel and Distributed Computing 10(3):271–275, 1990.

Answer 2

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.

Answer 3

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'