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. Requirement
  5. Discussions

Requirement

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 16 Discussions, By:

votes

Please Login in order to post a comment

  • karoljoc
    6 years ago+ 3 comments

    Sorry, but no matter how many times I read this question I still don't have an idea what it is you want to achieve in this puzzle. Please elaborate a bit on how you came to 1000 in your sample output or maybe reword your question so that it makes more sense.

    30|
    Permalink
  • moriano
    5 years ago+ 0 comments

    After reading this question several times, I still do not understand what I am supposed to do.

    The question NEEDS rewording as it seems out I am not the only one with problems.

    I love solving challenges, but I HATE trying to decipher questions poorly asked.

    10|
    Permalink
  • taylorleebiz
    5 years ago+ 2 comments

    My interpretation, using the sample input for explanation:

    From the sample input, n=6 and m=7.

    I'm using array convention, where a[0] is left most value and a[5] is right most value.

    a[0] can be any digit from 0 to 9. Same for indices 1 through 5.

    Therefore, you can think of the possible values of a as: [0,0,0,0,0,0] all the way to [9,9,9,9,9,9].

    Another way to think about this is, we are considering the range of numbers from 0 to (10**n)-1

    The number 654321 is in this range. Does 654321 fit all m requirements? m={(1 3),(0 1),(2 4),(0 4),(2 5),(3 4),(0 2)}

    m[1] = (0 1) => requirement that value@index0 <= value@index1

    For 654321, value@index0 is 6 and value@index1 is 5.

    Therefore, requirement m[1] is not met, so 654321 is not a valid assignment.

    3|
    Permalink
  • henry_scher_job
    11 months ago+ 0 comments

    For all but 3 of the test cases, it is possible (in C) to pass essentially by counting one-by-one the valuations that satisfy the requirements without timing out; you just have to do a tiny amount of work to minimize the amount of time spent on failed valuations.

    0|
    Permalink
  • peterabbitcook
    4 years ago+ 0 comments

    I've got a recursive solution with worst case (i.e. requirements = [[0,1]]) O(10**(m-1)) that passes all but 4 of the test cases (1, 3, 6 & 7).

    1. Can anyone point me to an algorithm with better time complexity than this?
    2. Has anyone figured out a strategy to memoize tail digit runs? This has proven remarkably difficult in the cases where the loop min iterator value depends on a digit much farther back in the digits (i.e. [0,m-1] is a requirement)
    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