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