# Clues on a Binary Path

# Clues on a Binary Path

+ 0 comments **Here is Clues on a Binary Path problem solution**- https://programs.programmingoneonone.com/2021/07/hackerrank-clues-on-a-binary-path-problem-solution.html

+ 0 comments I does not understand the problem can anyone explain it clearly, what is it

+ 0 comments Why does my last case does not get submitted? 524288

+ 0 comments interesting problem, had a lot of fun micro-optimizing it, though with that said it really should be marked advanced, overall neither I nor the editorial could reduce the time complexity to 2^d or lower, i.e. constant overhead; the best I got was a factor of ceil(n/w) where w is the largest machine word in bits while the editorial is at n; note that the editorial has little to no micro-optimizations, as such the likelyhood of actually passing all the testscases without compile optimization flags is very low, its still a good start, good luck.

+ 0 comments Dynamic programming (or memoization) and indeterminism!

If we suppose n_ways(A, d) to be a function that returns the total number of distinct ways in distance d from ANY house in a set A, we can compute it recursively:

`n_ways(A, d) = n_ways(reach(A, 0), d-1) + n_ways(reach(A, 1), d-1)`

where reach(A, c) gives the set of all houses that can be reached from ANY house in A with given clue (c = 0 or 1).

Then, memoizing n_ways() based on different A and d can boost the performance.

Sort 7 Discussions, By:

Please Login in order to post a comment