### Ripatti's blog

By Ripatti, 10 years ago, translation,

Introduction
After Codeforces Beta Round #11 several participants expressed a wish to read something about problems similar to problem D of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.

In some sense this article may be regarded as a tutorial for the problem D from Beta Round #11.

In this article quite well-known algorithms are considered: the search for optimal Hamiltonian walks and cycles, finding their number, check for existence and something more. The so-called "dynamic programming over subsets" is used. This method requires exponential time and memory and therefore can be used only if the graph is very small - typically 20 vertices or less.

DP over subsets
Consider a set of elements numbered from 0 to N - 1. Each subset of this set can be encoded by a sequence of N bits (we will call this sequence "a mask"). The i-th element belongs to the subset if and only if the i-th bit of the mask equals 1. For instance, the mask 00010011 means that the subset of the set [0... 7] consists of elements 0, 1 and 4. There are totally 2N masks, and so 2N subsets. Each mask is in fact an integer number written in binary notation.

The method is to assign a value to each mask (and, therefore, to each subset) and compute the values for new masks using already computed values. As a rule, to find the value for a subset A we remove an element in every possible way and use values for obtained subsets A'1, A'2, ... , A'k to compute the value for A. This means that the values for Ai' must have been computed already, so we need to establish an ordering in which masks will be considered. It's easy to see that the natural ordering will do: go over masks in increasing order of corresponding numbers.

We will use the following notation:
(a?b: c) - returns b if a holds, or c otherwise.
The elements of our set will be vertices of the graph. For the sake of simplicity we'll assume that the graph is undirected. Modification of the algorithms for directed graphs is left as an exercise for the reader.

1. Search for the shortest Hamiltonian walk
Let the graph G = (V, E) have n vertices, and each edge have a weight d(i, j). We want to find a Hamiltonian walk for which the sum of weights of its edges is minimal.

Let dp[mask][i] be the length of the shortest Hamiltonian walk in the subgraph generated by vertices in mask, that ends in the vertex i.

The DP can be calculated by the following formulas:
dp[mask][i] = ∞ in other cases.

Now the desired minimal length is . If pmin = ∞, then there is no Hamiltonian walk in the graph. Otherwise it's easy to recover the walk itself. Let the minimal walk end in the vertex i. Then the vertex j ≠ i, for which , is the previous vertex in the path. Now remove i from the set and find the vertex previous to j in the same way. Continuing this process until only one vertex is left, we'll find the whole Hamiltonian walk.

This solution requires O(2nn) of memory and O(2nn2) of time.

2. Finding the number of Hamiltonian walks
Let the graph G = (V, E) be unweighted. We'll modify the previous algorithm. Let dp[mask][i] be the number of Hamiltonian walks on the subset mask, which end in the vertex i. The DP is rewritten in the following way:
dp[mask][i] = 0 in other cases.

This solution requires O(2nn) of memory and O(2nn2) of time.

3. Finding the number of simple paths
Calculate the DP from the previous paragraph. The answer is . The coefficient 1 / 2 is required because each simple path is considered twice - in both directions. Also note that only paths of positive length are taken into account. You can add n zero-length paths, of course.

This solution requires O(2nn) of memory and O(2nn2) of time.

4. Check for existence of Hamiltonian walk
We can use solution 2 replacing the sum with bitwise OR. dp[mask][i] will contain a boolean value - whether there exists a Hamiltonian walk over the subset mask which ends in the vertex i. DP is the following:
dp[mask][i] = 0 in other cases.

This solution, like solution 2, requires O(2nn) of memory and O(2nn2) of time. It can be improved in the following way.

Let dp'[mask] be the mask of the subset consisting of those vertices j for which there exists a Hamiltonian walk over the subset mask ending in j. In other words, we 'compress' the previous DP: dp'[mask] equals . For the graph G write out n masks Mi, which give the subset of vertices incident to the vertex i. That is, .

DP will be rewritten in the following way:
dp'[mask] = 0 in other cases.

Pay special attention to the expression . The first part of the expression is the subset of vertices j, for which there exists a Hamiltonian walk over the subset mask minus vertex i, ending in j. The second part of the expression is the set of vertices incident to i. If these subsets have non-empty intersection (their bitwise AND is non-zero), then it's easy to see that there exists a Hamiltonian walk in mask ending in the vertex i.

The final test is to compare dp[2n - 1] to 0.

This solution uses O(2n) of memory and O(2nn) of time.

5. Finding the shortest Hamiltonian cycle
Since we don't care at which vertex the cycle starts, assume that it starts at 0. Now use solution 1 for the subset of vertices, changing the formulas in the following way:
dp[1][0] = 0;
, if i > 0, bit(0, mask) = 1 and bit(i, mask) = 1;
dp[mask][i] = ∞ in other cases.

So dp[mask][i] contains the length of the shortest Hamiltonian walk over the subset mask, starting at 0 and ending at i.

The required minimum is calculated by the formula . If it equals , there is no Hamiltonian cycle. Otherwise the Hamiltonian cycle can be restored by a method similar to solution 1.

6. Finding the number of Hamiltonian cycles
Using ideas from solutions 5 and 2 one can derive a DP calculating the number of Hamiltonian cycles requiring O(2nn2) of time and O(2nn) of memory.

7. Finding the number of simple cycles
Let dp[mask][i] be the number of Hamiltonian walks over the subset mask, starting at the vertex first(mask) and ending at the vertex i. DP looks like this:

This solution requres O(2nn2) of time and O(2nn) of memory.

8. Checking for existence of Hamiltonian cycle
We can modify solution 5 and, using the trick from solution 4, obtain an algorithm requiring O(2nn) of time and O(2n) of memory.

Exercises
CFBR11D
CCTOOLS

P.S. This article may be extended and fixed in future. The author would be grateful for supplementing the Exercises section and for pointing out any mistakes and inaccuracies.

• +22

 10 years ago, # |   +3 http://www.spoj.pl/problems/ASSIGN/For example
•  10 years ago, # ^ |   0 спасибо, задача очень понравилась)) действительно, дп по подмножествам, только вот без графов и маршрутов в них. поэтому пока не знаю, стоит добавлять ее в статью или нет.пусть пока повисит тут. потом, возможно, добавлю. возможно в новый раздел:)
 10 years ago, # |   0 Nice tutorial. You could also add an explanation on how to count hamiltonian circuits on a grid of size n x m with (n <= 7 and m <= 10^9) for example which is also fairly classical.
•  10 years ago, # ^ |   +1 Counting hamiltonian circuits on a grid is quite different from problems which was viewed there. In article I view foremost masks over subsets and paths in graphs. But in your problem motzkin words and matrix multiplication are used:)Maybe I will view your problem in fiture article:)
•  2 years ago, # ^ |   -23 instead of just writing formulas for dp you should have explained what these formulas means and how you derive on that. like this one :: https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/
•  2 years ago, # ^ |   -23 only formulas nothing else ... you should have explained in more details how things are working ... not good editorial
•  10 years ago, # ^ |   0 CouDo you have a reference to such a problem?
•  10 years ago, # ^ |   0 http://www.cs.ust.hk/mjg_lib/Library/Kwong_Ham_94.pdfit is very old paper:)
•  10 years ago, # ^ |   0 If the size of grid is 12*12 . Can we use DP over Subsets
•  10 years ago, # ^ |   0 Top  up
 10 years ago, # |   0 http://www.codechef.com/problems/TOOLSis an example problem for part 5.
•  10 years ago, # ^ |   0 Thanx! Very nice problem)) I added it.
 » 6 years ago, # |   0 Could you please further explain the recurrence in the first example (finding a shortest Hamiltonian walk)?
•  » » 6 years ago, # ^ |   0 For me too, please.
 » 6 years ago, # | ← Rev. 3 →   0 The following paper is potentially useful as reference:"A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, 1962. [citation, download]It contains lots of preliminary analysis and at least the DP approaches described in 1. and 5. of your post. I believe the algorithm is actually called "Held–Karp algorithm" in academic literature, but it was described independently by Bellman et al. in another paper.A list of optimal algorithms for TSP with better runtime complexity can be found here.
•  » » 4 years ago, # ^ |   0 can't open first link it requires e-mail for link sites.can u help me and give pdf file?
•  » » » 4 years ago, # ^ |   0 Took me two seconds to find another PDF source: http://people.cs.vt.edu/~gback/ICPCHandbook/book/copiesfromweb/held-karp-jsiam-1962.pdfyou're welcome.
•  » » » » 4 years ago, # ^ |   0 thanks,i am almost newbie on codeforces :d
•  » » » » 2 years ago, # ^ |   0 No link is working. Please update the links
•  » » » » » 6 months ago, # ^ |   0 in the link, replace codeforces.ru with codeforces.com.
 » 6 years ago, # |   0 In 4th section's second dp formulation second part, the condition stated is count(mask)>1 only. Isn't bit(mask, i) == 1 condition should also be included?
 » 4 years ago, # |   0 can anybody give me link to its implemented code for any of the above part. Rest I got stuck at bit masking in implementation. Thanks in advance whoever will give link.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 My solution for task D of CF beta round 11.Btw,am i the only one who can't see the solution of others in this contest?i can't even open my solution.
•  » » » 4 years ago, # ^ |   0 me too, something is wrong today, I can't open submission code, including myself, now I can only open my "official" submissions.
•  » » » » 4 years ago, # ^ |   0 Yes also just encountered this problem. Why I try to open my own solution I get "You are not allowed to view the requested page" error.
•  » » » » » 4 years ago, # ^ |   0 I actually have theory now for why this is. I think problem D might have been used in the VK Cup Finals — Trial Contest, and so they blocked solutions so we could not see submission from people in that contest.
 » 4 years ago, # | ← Rev. 2 →   +3 In first Section, consider a graph with only two vertices and one edge of weight say w then the answer computed by the process, comes to be w but expected asnwer is 2*w as for a hamiltonian walk the starting and ending vertices must be same.
 » 4 years ago, # |   -8 In the 7th section, how are those paths included in the answer where we use vertices v < first(mask). This means, if our bit representation of mask is 1101000, and we want to count no. of paths starting at first(mask)=3(3rd bit, 0-based indexing from right to left) and ending at vertex v=5(0-based indexing from right to left), how will paths like the one starting from vertex 3 to vertex 5 with vertex 0 on the way(and similar) be counted if we use the dp meaning given in section 7?
 » 3 years ago, # |   0 In a hamiltonian walk the vertices might repeat. On the other hand, in a simple path repetition of vertices is not allowed. How is it that using the same dp for ques 3 which was used for ques 2 works? Any insights would be highly appreciated.
•  » » 2 years ago, # ^ |   0 i think it is actually hamiltonian 'path' and not hamiltonian 'walk'.
 » 2 years ago, # | ← Rev. 3 →   -15 what is the meaning of in shortest hamiltonian path? why we are doing it and what we are getting from it ?
 » 2 years ago, # |   -24 bakwass editorial hai
 » 2 years ago, # |   0 Isn't checking for hamiltonian path obvious when atleast 2 nodes are attached to each other?
 » 22 months ago, # |   0 Great Post. Cleared all the doubts regarding "Hamiltonian". Thanks a lot.
 » 14 months ago, # |   -8 in problem 2, is the graph complete?
 » 11 months ago, # |   0 I think in the first two problem author is talking about Hamiltonian path, not about Hamiltonian walk. Please correct me if I am wrong. Thanks!
•  » » 7 months ago, # ^ |   0 I think so.
 » 5 months ago, # |   0 Link to HackerEarth practice problems.