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
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 151 |
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
Name |
---|
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. ]
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
Great solution! Thanks alot :)