PraveenDhinwa's blog

Dominos
By PraveenDhinwa, 12 years ago, In English

http://mirror.codeforces.com/contest/267/problem/B

Please help me in solving this problem. For me this looks like finding a hamlitonian path in a graph which is NP complete. Any hints for solving the problem ??

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Let's consider dominoes as edges and values written on dominoes as 2 vertexes. In this case all you have to do is to find Eulerian path, that can be done in O(n+m).

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Maybe this will be helpful. ;)

→ Reply