Help needed in Solving Graph Problem.

Revision en1, by aditya_sheth, 2020-07-22 17:01:03

Can someone please help me solve this problem. I came up with the following observations:

1) the first bit of the binary number should be 1.

2) we can think of each binary prefix(modulo n) as a node of the graph. So finally we need to find a hamiltonian cycle starting at 0 and ending at 0 where each node has an outgoing edge to the nodes (2*node)%n and (2*node+1)%n.

I am unable to progress further.

Tags #graph theory, codeforces::gym

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English aditya_sheth 2020-07-23 09:01:08 38 Tiny change: 's further.' -> 's further. Any help/hint will be really helpful.'
en1 English aditya_sheth 2020-07-22 17:01:03 495 Initial revision (published)