PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given a n dimensional hypercube centred at origin with node to node distance equals 2 and edges are between only those nodes whose square of euclidean distance is greater or equal to d. And we have to find a Hamiltonian path in this modified hypercube graph G’=(V, E’).
EXPLANATION:
First of all, lets consider the easy case of d<4. In this case we don’t have any edges, as the nodes are at a distance of 2 units ( note that d is square of euclidean distance ). When d \geq 4, we will have all the edges that are by default should be present in hypercube along with some other edges depending upon d. But in fact we don’t need those additional edges because every n(>1) dimensional hypercube has a Hamiltonian path. We can prove this by induction on n. The full proof and some other details of hypercube is given here.
Now we know that if d \geq 4, then there exists a Hamiltonian cycle in hypercube. The only problem is to find one. Recall the encoding of vertices of hypercube (given in the link above), in which each node of n dimensional hypercube is encoded as a bit string of length n and with an edge between vertices x and y if and only if x and y differ in exactly one bit position. For example, when n=2, V={00, 01, 10, 11} and E={(00, 01), (01, 11), (11, 10), (10, 00)} which denotes a square.
Now the interesting point to note is, if we enumerate all the n bit numbers in Gray code sequence we essentially get a Hamiltonian cycle and vice versa. Generating Gray code sequence is very simple. Just take two copies of all n-1 bits numbers in Gray code sequence, reverse one of them, add prefix 0 and 1 to old and reversed one respectively and concatenate. For example if we have to generate a Gray code sequence of 3 bit numbers. Take two copies of 2 bit numbers in Gray code sequence { (00, 01, 11, 10) , (00, 01, 11, 10) }, reverse one of them { (00, 01, 11, 10) , (10, 11, 01, 00) } and now add prefix 0 and 1 accordingly and then concatenate to get { (000, 001, 011, 010, 110, 111, 101, 100) }.
At this point we already have a Hamiltonian cycle, only step which is left is printing the path appropriately, for which we have to search for the initial vertex (starting point) and start printing the cycle from that vertex. Also note that vertices needs to be converted into the coordinate form, which is easy as ith dimension will be 1 if ith bit of vertex is 1 and ith dimension will be -1 if ith bit of vertex is 0. The time complexity of this algorithm will be T(n) = T(n-1) + 2^n = \mathcal{O}(2^n), where n is the number of vertices. This is because at every step we are making a recursive call for the Hamiltonian path of hypercube of one lower dimension and then concatenating the results in \mathcal{O}(2^n) time. For more detail refer to the editorialist code.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.