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.

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