Задача по двумерной упаковке от Dropbox

Компания Dropbox опубликовала головоломки для потенциальных кандидатов на работу. Свои решения для тестовых задач просьба высылать на jobs@dropbox.com. Как сказано на сайте, с авторами этих писем «нам есть о чём поговорить».

Первая задача — алгоритм двумерной упаковки объектов. Нужно разместить прямоугольники заданной длины и высоты на минимальной площади. На входе перечень объектов с указанием длины и ширины (целые числа), на выходе функция должна выдавать площадь минимального прямоугольника, куда они помещаются. Объекты можно поворачивать на 90°. Дополнительные бонусные очки выдаются за визуализацию средствами stderr.
Пример начальных условий:

3
8 8
4 3
3 4

Результат:

88

Визуализация (stderr):

11x8:
+ - - - - - - + + - + 
|             | |   | 
|             | |   | 
|             | + - + 
|             | + - + 
|             | |   | 
|             | |   | 
+ - - - - - - + + - + 

8x11:
+ - - - - - - + 
|             |
|             | 
|             | 
|             | 
|             | 
|             | 
+ - - - - - - + 
+ - - + + - - + 
|     | |     | 
+ - - + + - - + 

11x8:
+ - + + - - - - - - + 
|   | |             | 
|   | |             | 
+ - + |             | 
+ - + |             | 
|   | |             | 
|   | |             | 
+ - + + - - - - - - + 

8x11:
+ - - + + - - + 
|     | |     | 
+ - - + + - - + 
+ - - - - - - + 
|             | 
|             | 
|             | 
|             | 
|             | 
|             | 
+ - - - - - - + 

Кстати, кое-кто уже попробовал решить эту задачу: см. результат. Другие идеи здесь (PDF).

Вторая задача — алгоритм обработки событий в файловой системе Dropbox. На входе вам дают список событий типа ADD/DEL с указанием времени UNIX, путём к файлу и хэшем контента. Нужно привести их в удобочитаемый вид на английском языке. Как сообщается, здесь нет идеального решения, зато существует несколько способов интерпретации. Судить будут по скорости работы алгоритма, красоте вывода, обработке неоднозначных событий и т.д. Пример ниже является корректным, но результат не выглядит user-friendly.

Пример начальных условий:

6
ADD 1282352346 /test -
ADD 1282353016 /test/1.txt f2fa762f
DEL 1282354012 /test -
DEL 1282354012 /test/1.txt f2fa762f
ADD 1282354013 /test2 -
ADD 1282354013 /test2/1.txt f2fa762f

Результат:

Added dir /test.
Added file /test/1.txt.
Renamed dir /test -> /test2.