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

510C – Fox And Names – CodeForces Tutorial

Understanding the Problem

Given a list of words, modify the order of the alphabets such that the words are sorted in lexicographical (alphabetical) order. We compare based on the left most position of the each word, but should there not exist one (i.e. “care” and “careful”) the shortest short is the lesser. This meant that if there is a sequence like “aaaaaaa” preceding “aaa”, it is invalid.

To help better understand this problem, I created a small program that assigns a value of 0 to 25 to the alphabetical sequence given and outputs the values bellow a word. Bellow is a sample run of one of the given pretests using the default alphabetical sequence:

$ ./permTester abcdefghijklmnopqrstuvwxyz < input1.txt
car
2 0 17
care
2 0 17 4
careful
2 0 17 4 5 20 11
carefully
2 0 17 4 5 20 11 11 24
becarefuldontforgetsomething
1 4 2 0 17 4 5 20 11 3 14 13 19 5 14 17 6 4 19 18 14 12 4 19 7 8 13 6
otherwiseyouwillbehacked
14 19 7 4 17 22 8 18 4 24 14 20 22 8 11 11 1 4 7 0 2 10 4 3
goodluck
6 14 14 3 11 20 2 10

Now with a sequence that puts the list of words in lexicographic order:

$ ./permTester acbdefhijklmnogpqrstuvwxyz < input1.txt
car
1 0 17
care
1 0 17 4
careful
1 0 17 4 5 20 10
carefully
1 0 17 4 5 20 10 10 24
becarefuldontforgetsomething
2 4 1 0 17 4 5 20 10 3 13 12 19 5 13 17 14 4 19 18 13 11 4 19 6 7 12 14
otherwiseyouwillbehacked
13 19 6 4 17 22 7 18 4 24 13 20 22 7 10 10 2 4 6 0 1 9 4 3
goodluck
14 13 13 3 10 20 1 9

So now you should get an idea of what the question wants.

Explaining the 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.

So the main hint from the provided tutorial was:

It is actually the classic topological order question

You then model the question as a precedence-constrained scheduling problem. From the Princeton Algorithms book:

Given a set of jobs to be completed, with precedence constraints that specify that certain jobs have to be completed before certain jobs are begun, how can we schedule the jobs such that are all completed while still respecting the constraints?

Our “jobs” here are the alphabets a-z. For example, given a sequence of words “tourist”, “petr” and “wjmzbmr”, you will have a chain t->p->w. If there a sequence like “qac”, “qab” and “zab”, you will have 2 chains c->b and q->z. There can be many chains, and these chains can connect to each other. 

I usually have some print messages to assist in debugging my code. The part where it adds the precedence constraints (or edges) you can uncomment to see how it is making those decisions:

compare qac and qab
c precedes b
compare qab and zab
q precedes z

Detecting whether a sequence of words is “Impossible” is as simple as detecting whether there are any cycles in a directed graph, for example in the 2nd example input:

2015-10-26 13_34_43-Graph Creator

The cycles present are s->o->s and t->p->w->y->v->s->r->t. It is not important to find the cycles, just whether or not one exists. You can achieve this by tracing the nodes of every recursive call a node traverses in a DFS. If within a recursive call of a node it traverses itself, there is a cycle. Here is the code for cycle detection; you pass a DiGraph and you check the boolean hasCycle:

class DiCycle
{
public:
	DiCycle(const DiGraph &g) : hasCycle(false)
	{
		for (int i = 0; i < g.getSize(); ++i) {
			onStack.push_back(false);
			marked.push_back(false);
		}
		
		for (int i = 0; i < g.getSize(); ++i) {
			if (!marked[i] && !hasCycle) dfs(g, i);
		}
	}
	
	bool hasCycle;
	
private:
	void dfs(const DiGraph &g, const int &v)
	{
		if (hasCycle) return;
		
		onStack[v] = true;
		marked[v] = true;
		
		for (const auto &w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			} else if (onStack[w]) {
				hasCycle = true;
				return;
			}
		}
		
		onStack[v] = false;
	}
	
	vector<bool> onStack;
	vector<bool> marked;
};

The algorithm above traces the DFS using a vector of booleans onStack (recursion uses a stack internally), where the indices of the vector correspond to the graph nodes.

The DiGraph here used is an adjacency set.

Once you validate that the digraph has no cycles (or a DAG; Directed Acyclic Graph), the topological order is as simple as finding the reverse post order of the DAG:

class Topological 
{
public:
	Topological(const DiGraph &g)
	{
		for (int i = 0; i < g.getSize(); ++i) {
			marked.push_back(false);
		}
		
		for (int u = 0; u < g.getSize(); ++u) {
			if (!marked[u]) dfs(g, u);
		}
	}

	deque<char> order; // used as stack
	
private:
	void dfs(const DiGraph &g, const int &v)
	{
		marked[v] = true;
		
		for (const auto &w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			}
		}
		
		order.push_front(ALPHABETS[v]);
	}

	vector<bool> marked;
};

I used a deque here over the STL stack because stack doesn’t expose iterators for me to loop through. Also, stack actually uses a deque internally.

So, in the end we do DFS (Depth First Search) twice on the digraph; first pass to check for cycles, and second pass to get the topological order. Here’s the summary:

int main()
{
	DiGraph g(ALPHABETS.size());
	
	/** --code for adding edges removed for brevity-- **/
	
	DiCycle cycle(g);
	
	if (cycle.hasCycle) {
		cout << "Impossible";
		return 0;
	}
	
	Topological topo(g);
	
	for (const auto &c : topo.order) cout << c;
}

It may surprise you that the output tends to be in the reverse order of the alphabets (cause the alphabets are added in order to a stack), but rest assured it is still a valid answer.