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.

UPDATE: The dynamic programming variant is the solution is up, and it solves in half the amount of code!

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++) {
    g.addEdge(new Edge(0, i, 0));
    g.addEdge(new Edge(i, k+1, 0));
}

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.

digraph-illustration

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:

shortest-path-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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s