# 103 – Stacking Boxes (Dynamic Programming Method) – UVa Tutorial

In my previous post I wrote about solving the Stacking Boxes problem using graphs. In this post I will write about a simpler method that utilizes dynamic programming that solves the same problem with half the amount of code.

I will assume you have read my previous post on using graphs, though you haven’t you can check it out here: 103 – Stacking Boxes (Graph Method) – UVa Tutorial. I will refer longest increasing subsequence as LIS and dynamic programming as dp.

## On the O(n^2) LIS Dynamic Programming Solution

In using dynamic programming there are 2 variants of the algorithm: one solves in O(n^2) and another in O(n*log n), the later of which replaces the inner loop in the former algorithm with a binary search using an algorithm called Patience Sorting. I will be using the simpler, quadratic time variant. I won’t attempt to explain the algorithm in detail, but there are plenty of resources out there to help you wrap your head round it:

1. Tushar Roy’s step by step of the algorithm (youtube video)
2. Geeksforgeeks article
3. Bo Qian’s youtube video (with C++ code)
4. Article on Algorithmist (succinct, though can be tough to understand).

The first 2 resource will only find the length of the LIS, though that process is the heart of the algorithm. Once you can find that, getting the sequence itself is not that hard.

## A Generic LIS Implementation

The code here is based off a stackoverflow answer.

```template<typename T>
deque<T> find_lis(const vector<T> &a,
function<bool(const T &, const T &)> comp = [&](const T &a, const T &b)->bool { return a < b; })
{
int maxLength = 1, bestEnd = 0;

vector<int> DP(a.size(), 1);
vector<int> prev(a.size(), -1);

for (int i = 1; i < a.size(); i++) { for (int j = i - 1; j >= 0; j--) {
if (DP[j] + 1 > DP[i] && comp(a[j], a[i])) {
DP[i] = DP[j] + 1;
prev[i] = j;
}
}

if (DP[i] > maxLength) {
bestEnd = i;
maxLength = DP[i];
}
}

deque<T> lis;
for (int i = bestEnd; i != -1; i = prev[i]) {
lis.push_front(a[i]);
}

return lis;
}
```

Using the function itself is pretty straightforward. You pass a vector that contains your sequence and it spits out the LIS as a deque. Here’s a github gist that test drives this function. You also have an option to modify the comparator, which in the gist is used to change the LIS algorithm to find the longest decreasing subsequence.

## Solution Explanation

Once you understood what the LIS algorithm is doing, the rest is pretty much a no brainer. Once you sort the boxes and its dimensions, you can find the LIS is about 5 lines of code:

```auto comp = [&](const Box *a, const Box *b)->bool { return canFit(a, b); };
auto lis = find_lis<Box*>(boxes, comp);

cout << lis.size() << endl;
for (auto b : lis) cout << b->id << " ";
cout << endl;
```

The only thing you need to customize here is the comparator; you will get the LIS based on whether the boxes will fit into each other. I handle this will a simple lambda function comp which I input inside find_lis. The canFit function is the exact same function in the graph method solution.

# 103 – Stacking Boxes (Graph Method) – UVa Tutorial

I am excited. Stacking Boxes has had me mystified over almost a year (my last failed submission was 5 Dec 2014). I have Googled and Googled but could not solve it… until now.

Perhaps you noticed that I placed in the title “Graph Method”. That is because there are 2 ways to solve this problem: either by using dynamic programming (or dp for short) or graphs. I will be writing about the graph method, which is, according to algorithmist, the more complex solution. I have not studied dp in depth, so I decided I will try graphs first. Perhaps in a future post I will look into dp and decide if it really is the simpler solution.

NOTE: If you have no knowledge about graph theory, check out Algorithms by Robert Sedgewick and Kevin Wayne. In addition to the book, they have a website and a Coursera online course (Graphs are in part II). The algorithms I will talk about references from this book. I refer it here as the Princeton Algorithms book.

Let’s begin.

## Explaining the Problem

Given a bunch of boxes of n dimensions, find a longest sequence such that you are able to fit a box inside a box for all boxes in that sequence. The boxes can be flipped, turned, contorted in order to fit inside another box, so you don’t have to follow the order of the dimensions they provide.

## Gotcha’s and Observations

Perhaps a possible step you have considered is sorting the boxes and find the longest increasing subsequence (or LIS for short) from there by comparing from left to right; the most left being the smallest and the most right being the largest. Indeed sorting the boxes and its corresponding dimensions is the first step, but the start of the sequence is not necessarily the first box sorted in ascending order. Here is an example input:

```5 2
3 70
8 10
4 9
9 31
10 10```

5 boxes of 2 dimensions. And now the sorted order (the first number that is followed by a colon is the original ordering):

```1: 3 70
3: 4 9
2: 8 10
4: 9 31
5: 10 10```

In such a case the sequence cannot start from 1. The same applies that the last element of the sorted boxes isn’t necessarily the last element of the LIS (refer to the 5th box in the input above).

Notice that 5 can never preceded 4, and 4 can never precede 2 and so on. This is true for all sequences of sorted boxes: no box can precede a box before it. This way we only add the edges of the graph from top to bottom.

So imagine trying to solve this problem without graphs or dp. I actually tried listing every possible permutation and selecting the longest sequence a year ago (It was pretty bad).

## Explanation of Solution

So to put it succinctly, if you make connections in a digraph based on whether a box fits in another box, you will get yourself a directed acyclic graph (DAG for short). The longest path of this graph is the LIS of boxes that can be stacked. You find the longest path by finding the shortest path of a graph with negative edge weights.

There are no variable weights to any of the edges here, so we just set all edges connecting from one box to another as -1.

To further explain the solution I will use an example input:

```7 2
3 70
8 10
5 9
5 7
4 5
9 31
10 10```

If you sort the boxes the input would like this:

```1: 3 70
5: 4 5
4: 5 7
3: 5 9
2: 8 10
6: 9 31
7: 10 10```

Now when building the digraph, note of the property that the start and end of the sequence is not necessarily the start and end of the sorted order of boxes. Therefore in addition to the vertices representing the boxes we have 2 more vertices, source and end (this is why the graph is sized k+2 in the solution). Source connects to all boxes, and all boxes connect to end. All connections to and from these 2 vertices are of 0 weight:

```// add edges to source (start) and sink (end) vertex
for (int i = 1; i < k+1; i++) {
}
```

The line:

```g.print(); cout << endl;
```

Prints the digraph by listing all the vertices and its respective edges and edge weights as such:

```0 : 1(0) 2(0) 3(0) 4(0) 5(0) 6(0) 7(0)
1 : 8(0)
2 : 6(-1) 8(0)
3 : 2(-1) 6(-1) 7(-1) 8(0)
4 : 2(-1) 6(-1) 7(-1) 8(0)
5 : 4(-1) 3(-1) 2(-1) 6(-1) 7(-1) 8(0)
6 : 8(0)
7 : 8(0)
8 :```

I’ve went ahead to illustrate the digraph for the above input. Note that I didn’t illustrate connections from and to source and end vertices, because it would look really messy.

I then find the longest path by using the topological sort algorithm, which relaxes (you can read about edge relaxation here) all edges in topological order (reverse post order of dfs) to find the shortest path tree.

Here is the gist of the algorithm in code:

```distTo [ source ] = 0;

Topological topo(g);

for (const auto &v : topo.order) {
for (const auto ed : g.adj(v)) relax(ed);
}
```

Here is a possible tree:

Note that there are 2 possible sequences for this example (5 4 2 6 and 5 3 2 6); the algorithm will only find one, but either one is a valid answer.

## Topological Sort vs Bellman-Ford

I have looked up a solution by saicheems that solves Stacking Boxes by also using graphs, and he uses the Bellman-Ford algorithm. This is a sensible choice granted that there are negative edges, but this is a DAG; you can get away with the topological sort algorithm, which works also for digraphs with negative edges, as long as it is acyclic (Bellman-Ford takes care of cycles).

Why topological sort algorithm? Well, it is faster (and IMHO is also simpler than Bellman-Ford). Bellman-Ford solves the problem in O(E*V) whereas topological sort uses O(E+V).

Well, at least that is what is said on paper. Saicheems solution also ran in time 0.000 (I suspected something is wrong with the judge), which is no different my solution.