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?