• Problem Statement: https://community.topcoder.com/stat?c=problem_statement&pm=14667
• Dr. Plank's Lab Writeup: http://web.eecs.utk.edu/~plank/plank/classes/cs494/494/labs/Lab-6-RainbowGraph/

This guide is huge. I know. If you want to skip to a certain part, feel free to click any of the sections from here:

1. Synopsis
2. Table of Contents
3. What is RainbowGraph?
4. bitDP: Counting Hamiltonian Paths the better way
5. Step 1: Check if a Hamiltonian Path exists
6. Step 2: The modifications for success
7. Step 3: From testing to counting
8. Speeding it up even more
9. Other advice (for Topcoder)
10. Conclusion

RainbowGraph is a graph problem that has you counting up the number of possible paths that go through the entire graph. There are a few things to this that make it a worthy coding challenge:

• Every vertex must be visited exactly once.
• Every vertex has a colour assigned to it. When you reach a colour in the graph, you must visit all vertices of the same colour before you can go to one of another colour.
• There can be 10 vertices that have a specific colour, and there can be 10 maximum possible colours. 100 vertices total.

Here is an example of what a graph might look like for this problem:
120 possible paths...

As it turns out, the paths we are looking for actually has a name. We call these paths Hamiltonian Paths, where they visit every vertex exactly once. The "colour" aspect means that the typical DFS method of traversing the entire graph and counting paths will not work on this problem.

Solving RainbowGraph suddenly changes from being a simple DFS problem, to being a two-step problem where:

1. You have to solve sub-graphs of vertices of each colour, finding the number of possible paths between all vertices in them.
2. Compute the number of possible combinations from all vertices in one colour to another.

This guide will focus mainly on the first part. Dr. Plank's guide on the second half is pretty much as efficient as it gets. This can be done via a very carefully programmed DFS. However, for TopCoder, using DFS will make your program too slow to pass the system test.

Since the solution involving DFS can take much longer than 2 seconds (even on UTK's Hydra machines), we have to resort to other algorithms that do not involve traversing the graph as often.

"But Clara, why is DFS so slow?"

You are traversing every possible combination in the graph from every node to every other node naively. This results in too many function calls. It has a running time of O(N!).

Introducing bitDP

There is a technique to do this more efficiently, called bitDP (Bit Dynamic Programming), which uses a slightly modified version of the Held-Karp algorithm [Wikipedia] to give the number of possible Hamiltonian Paths for every vertex in a graph.

The best part? It's O(2^N × N²), which is an improvement over O(N!). It also eliminates recursion. There is only a single function call.

A Proof of Concept

First, let me show you that this does work, before I go in depth on how to implement it.

Consider the following graph of 4 vertices and 5 edges (Assume they are all the same colour): Construct the Adjacency Matrix for the graph:

Vertex/Mask	0	1	2	3
0	0	1	1	0
1	1	0	1	1
2	1	1	0	1
3	0	1	1	0

On paper, you can figure out how many hamiltonian paths there are from each vertex to another. Let's look at the number of hamiltonian paths from the first vertex to every other one:

• 0 -> 0: 0 paths (It can't go to itself)
• 0 -> 1: 1 path (0231).
• 0 -> 2: 1 path (0132).
• 0 -> 3: 2 paths (0123 0213).

Alright. Now let's try it with our secret weapon. The Y axis is the vertex, and the X axis is the mask. In theory, we will have the number of possible paths from vertex 1 to T at bitDP[T][2^N - 1], where N is the number of vertices in the graph (4).

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	0	1
2	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	1
3	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	2

Hey look at that! The final column has the number of paths to each vertex from the first one. This method can be configured to go from any vertex we wish to ALL vertices in the graph!

So before I explain how to implement this method, it's important to understand the original algorithm. The original algorithm simply tells us whether a Hamiltonian path exists in a graph. It doesn't tell us how many there are. HackerEarth has a page on it actually. So a shoutout to them.

Setup

We will need two 2D arrays for this. Let's use the same graph from before: Setup the adjacency matrix, sized N × N:

Vertex/Mask	0	1	2	3
0	0	1	1	0
1	1	0	1	1
2	1	1	0	1
3	0	1	1	0

Then, set up the dp array. This one is sized a little differently, being N × 2^N. This is formatted so the Y-axis is the vertex, and the X-axis is the bitmask. I'll get to that.

For now, set all values to 0. Then, for the N vertices in the graph, set dp[i][2ⁱ] to 1.

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

So this is where we are going to consider how the bitmasks truly work. If you have counted in binary before, you should know that 2^N combinations of bits can be stored in N bits. The graph has 4 vertices. So there are 16 possible combinations, and we are counting "i" from 0000 to 1111.

The Algorithm

Now let's fill this table in. Loop through all masks (0 to 2^N), and for each mask, loop through each vertex (0 to N). In C++, it should look as follows:

for (int i = 0; i < (1 << N); i++) {
	for (int j = 0; j < N; j++) {
		/* Code */
	}
}

Next, check if the j^th bit is set to 1. If so, inside the second loop, let's loop through all of the vertices again (0 to N) with the variable "k".

In C++, you can check if the j^th bit is is set to 1 in i by using if ((i & (1 << j))) { }.

Inside the third loop, you are going to set dp[j][i] to 1 if the following applies:

• The k^th bit is set to 1 in i
• Vertex k can go to Vertex j

By the end of the 3 loops, the table will be filled with values. If any of the bits in the last column are 1, the graph has a Hamiltonian path!

Working out a column

Now let's work out a column. We have to work from left to right, but the first 3 aren't going to change. Let's do 3. If i is 3, then it's binary representation is 0011. This means it accounts for when vertices 1 and 2 have been visited.

Loop j from 0 to N (4).

• i = 3.
  • j = 0. 3 AND 1 = 1. Loop k from 0 to N (4).
    • k = 0. The first bit in i (3) is 1. Vertex 0 can't go to Vertex 0. Nothing changes.
    • k = 1. The second bit in i (3) is 1. Vertex 1 can go to Vertex 0. dp[3][0] becomes 1.
    • k = 2. The third bit in i (3) is 0. Nothing changes.
    • k = 3. The fourth bit in i (3) is 0. Nothing changes.
  • j = 1. 3 AND 2 = 1. Loop k from 0 to N (4).
    • k = 0. The first bit in i (3) is 1. Vertex 0 can go to Vertex 1. dp[3][1] becomes 1.
    • k = 1. The second bit in i (3) is 1. Vertex 1 can't go to Vertex 1. Nothing changes.
    • k = 2. The third bit in i (3) is 0. Nothing changes.
    • k = 3. The fourth bit in i (3) is 0. Nothing changes.
  • j = 2. 3 AND 4 = 0. We skip this vertex.
  • j = 3. 3 AND 8 = 0. We skip this vertex.

Now that dp has been adjusted to account for column 3, the table should now look like this:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

I've highlighted the new additions in red. Now we just have to do columns 4 through 2^N...

Final answer

Here is the finished table.

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	1	1
2	0	0	0	0	1	1	1	1	0	0	0	0	1	0	1	1
3	0	0	0	0	0	0	0	0	1	0	1	1	1	1	1	1

Remember, if any cell in the last column is 1, the graph has a Hamiltonian path. In this case, all 4 cells are 1. It definitely has at least one.

Observations

The idea of bitDP here is to tell whether a path exists with certain vertices visited. The mask, as mentioned earlier, goes from 0x0 (0000) to 0xF (1111). When we look at a mask, we look at which bits are set to 1. Those are the vertices we visited for that path. Hence why 0xF consists of paths that involve all 4 vertices being visited. Furthermore, the Y-axis, being the vertex tells whether there is a path that exists that ends with that vertex.

Example

Take the mask at 0x7 for example. 7 in binary is 0111, hence the first 3 vertices are visited but the fourth one is left unvisited.

Vertex/Mask	...	7	...
0	...	1	...
1	...	1	...
2	...	1	...
3	...	0	...

Let's look at the third row (Vertex 2) of mask 7. It's set to 1. That means there is a possible path that has only vertices 0, 1, and 2 that also ends at vertex 2. Based on the table, we can also conclude there are possible paths that involve those same vertices that end at vertex 0 and vertex 1.

Step 1 was the easy part. We now have a way to check if there is a Hamiltonian path in O(2^N × N²) time. There are a few observations to make with the algorithm in step 1 that can hint us toward success:

• In dp[X][2^N - 1], where X is any vertex from 0 to N, you can tell if there is a Hamiltonian path if any of these are set to 1. But it also tells whether there exists a Hamiltonian path that ends at vertex X. For example, if dp[1][2^N - 1] is 1, then there exists a Hamiltonian path that ends at the second vertex.
• Getting the ending vertex is a property of the previous algorithm. It is possible to get the starting vertex though. And this is exactly what we want.

Procedure

Let's get the starting vertex. This will result in a O(2^N × N³) loop instead of O(2^N × N²) from earlier.

Make the following changes from Step 1:

• Instead of making a single dp matrix of [N][2^N] size, make N of them, or make it into a 3D array of dp[N][N][2^N].
• Set all values to 0. Then, for the N vertices in the graph, set dp[i][i][2ⁱ] to 1.

The initial dp matrix will look like this:

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

Wow! That's a lot. Now let's run the algorithm from Step 1 on all N of the new DP array.

Final Result

After calling the algorithm on all N vertices, we will get this:

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

"Ok Clara this is a bit much. What's the point?"

Well it's a bit much to do by hand, I agree there. But take a look at the last column of each of the entries. We're now able to tell whether a Hamiltonian path exists from a starting vertex to an ending vertex via simply checking the dp array via dp[start][end][2^N - 1]!

Let's say I wanted to know if there existed a Hamiltonian path where the starting vertex is Vertex 0, and the ending one is Vertex 3. Now we just have to check dp[0][3][2^N - 1]. And yes, it's 1.

The stage is set for the final modification.

Step 2 improved on the idea on generating a dp matrix that tells whether or not a Hamiltonian path exists. The problem with RainbowGraph is that we don't really care if it exists or not. We want the number of paths that exist from every vertex to every other vertex. Unfortunately, we cannot just expand the array one more time to do this. Instead, we will have to make adjustments to the algorithm to force it to count instead of simply setting dp[X][Y][MASK] to 1.

Fortunately, we can do this in a single line. Assuming i is the current mask, j is the destination vertex, and k is the source vertex... In the most inner loop, instead of setting dp[j][i] to 1, take its current value and add dp[k][i ^ (1 << j)].

The results look pretty promising... It's the correct answer!

dp[0] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 2
dp[1] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
dp[2] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
dp[3] =	Vertex/Mask 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 2 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

If you are following Dr. Plank's lab writeup for implementation, you can convert the DP array into NP easily by setting NP[i][j] to DP[i][j][(1 << N) - 1].

Results

Now it's time to compare bitDP to DFS. These tests were run on UTK's Arc machines, with an Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz. Both programs are compiled without optimisation. The results are quite pleasing...

Here's the full graph. You can barely see the bitDP performance time here. It's nearly flatlining compared to DFS! Let's adjust the vertical axis a little bit. Graphs from 1 to 100 vertices were generated. The tests are averaged from 10 runs of each program. Note the jumps at N = 10, 20, ..., 100. These are from the second part where we have to traverse from each vertex to one that connects with another colour.

The tester uses case_gen, a graph generator I wrote as a brutal stress test for RainbowGraph's first part. You can download the C file for it here. Graphs generated have the maximum possible edges among neighbours of the same colour in each graph. Only one vertex connects with another vertex of a different colour. This is done intentionally, as we are only trying to stress the DFS/bitDP part of the program.

Surprisingly, this wasn't enough to pass the system test. I get around 67/70 test cases correct. The others hit the 2 second timeout. Oddly, if I ran the system test multiple times, I end up missing random cases. So I must be barely over the 2 second limit. Let's fix that.

There are ways to speed this algorithm up. While it will still be O(2^N × N³) time, we can still eliminate some computations.

Hear me out. Here's the current algorithm we have:

For each vertex (source = 0 .. N)...
	For each mask (i = 0 .. 2N)...
		For each vertex (j = 0 .. N)...
			For each vertex (k = 0 .. N)...
				If the jth bit is set to 1 in i, and we can go from vertex j to k...
					dp[source][j][i] += dp[source][k][i ^ (1 << j)]

Method 1: Skipping some loops

There are a few ways to cut out a lot of the clutter in the loops:

• Right after assigning i, check if the source^th bit is set in i. If not, skip the mask and move to the next one.
• Right after assigning j, check if the j^th bit is set in i. If not, skip vertex j and move to the next one.

Method 2: Abuse properties of bitDP

There is one more thing we can do to eliminate 2^N - 1 steps as well. Take a look at the graph. I've highlighted the cells in red that can be eliminated:

Vertex/Mask	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	1	1
2	0	0	0	0	1	1	1	1	0	0	0	0	1	0	1	1
3	0	0	0	0	0	0	0	0	1	0	1	1	1	1	1	1

These cells are guaranteed to be 0. And it increases exponentially with each vertex, since the first one in each row is set at 2^N. Furthermore, we can actually start the loop at 1 since the first column is guaranteed to always be 0.

What happens when we make these changes? Well... And that was enough to pass the system test on Topcoder.

As you may have noticed, passing the system test on Topcoder is not easy. My implementation barely passes. Here are other programming tips you may find useful to help speed up your program, even if slightly:

• Do not use vector.size() in for loops. Actually, do not use any STL container's .size() function in loops. Instead, call it once and store the value in an unsigned int.
  • This is deceivingly effective. Back when I implemented the DFS method, caching all of the size calls made my program 1/3x faster (a few seconds!).
  • Why is it bad? The containers do not store the size natively. Normally it's a subtract operation such as this:
    Code (C++)

    _M_end - _M_begin

• Don't use data structures in situations where you don't really have to. In RainbowGraph, we are given limits such as 10 vertices per colour, and 10 colours max. You can skip creating a vector, calling push_back (or resize) completely by just making an array that can hold the theoretical max.
  • Why? Who knows what functions like .insert() or .push_back() are doing behind the scenes (besides what they should be doing). I don't care either. But a guarantee is that the entire process with a single array being made is faster.
• If you're using recursion, do not call the function again if you don't have to. Have checks in place prior to the function call, and skip it if you can.

I like a good challenge. And this one certainly was able to satisfy that. Overall, when you loop bitDP around the number of colours in the graph, the algorithm becomes O(2^N × N⁴). But, it's way faster than the previous approach.

It also takes advantage of the Topcoder problem constraints. Notably, I'm glad that there's only 10 vertices that belong in each colour group! The size of the DP array grows exponentially. For instance, if 22 were allowed then the DP array would use around 1.677 GB!

I'm not sure if Topcoder had their hardware change or if they simply made time limits much more strict (someone should let me know). But, I'm glad that I passed that system test. I hope this guide helps others out on it too.