We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Clues on a Binary Path
  5. Discussions

Clues on a Binary Path

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 6 Discussions, By:

votes

Please Login in order to post a comment

  • mrseydel
    4 years ago+ 0 comments

    Case #19 seems to violate the described input format - looks like there is a line (after the first m+1) and which contains a single integer, not three.

    2|
    Permalink
  • Venkat_manikanta
    7 months ago+ 0 comments

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

    0|
    Permalink
  • Esthislove
    9 months ago+ 0 comments

    Why does my last case does not get submitted? 524288

    0|
    Permalink
  • samy_vilar
    2 years ago+ 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|
    Permalink
  • dzchoi
    4 years ago+ 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.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature