rahulpadhy's blog

Clues on a Binary Path
By rahulpadhy, history, 8 years ago, In English

Can anyone please explain the approach to this question ? The editorial is not clear.. If possible, can you mention about any other approach ? Here's the link: https://www.hackerrank.com/contests/hourrank-14/challenges/clues-on-a-binary-path

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where you don't understand? Let me know..

Brute Force i.e. simple DFS will give TLE. Here we need to use "Meet in the middle" problem solving technique. !

It is simple. Do "Depth Limited Search" from each node with depth l/2. You can do this recursively or iteratively with stack or queue. [ In the sample code they used queue ]. And keep track of the path.

Now see if 2 states collide then there is a solution ! You can do this by brute-forcing on the path and see if this path is valid. :)

[ The sample code that they have provided also seems weird to me. ]

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial is needlessly complicated. It is actually very easy to do it in O(N * D * 2^D).

For each path so far we store which nodes we can end such a path on: therefore in dp[pathlength][pathmask] we store a bitmask of what nodes we can end on. We can two long longs to store this bitmask as N <= 90.

We also keep a bitmask for edge[node][colour] which is a bitmask of all nodes which you can reach from node with a edge with that colour.

Then, for each state transition, we can update the appropriate values in O(1) by doing OR on the bitmasks of nodes.

Code with AC on Hackerrank: http://ideone.com/bTTrha

→ Reply