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. Functional Programming
  3. Functional Structures
  4. Range Minimum Query
  5. Discussions

Range Minimum Query

Problem
Submissions
Leaderboard
Discussions

Sort 14 Discussions, By:

votes

Please Login in order to post a comment

  • maqusss
    5 years ago+ 0 comments

    O(N log N + M log N ) time is enough. No fancy Segment Trees required! Fancy Maps are enough.

    1|
    Permalink
  • codeonwort
    6 years ago+ 0 comments

    Before asnwering queries I constructed a segment tree. It's really, really weird, but the tree is not fully evaluated on Hackerrank server.

    main = do
        [n,m] <- getInts                -- a custom parser function
        nums <- getInts
        let segTree = buildTree nums n  -- here is the problem
        replicateM_ m $ do
            range <- getInts
            print $ query segTree range
    

    This code gave me TLE on test 05 ~ 07. But this code works perfectly well in my computer, taking only 0.3 seconds.

    I forced segTree to be fully evaluated before answering queries:

    import Control.Exception
    
    main = do
        [n,m] <- getInts
        nums <- getInts
        let segTree = buildTree nums n
        evaluate segTree                  -- here
        replicateM_ m $ do
            range <- getInts
            print $ query segTree range
    

    Suddenly it passes all tests. It means segTree was not fully evaluated, causing severe performance down. But the same code works fast in my computer. So, what's wrong? Is it caused by difference of compiler settings, or compiler versions?

    1|
    Permalink
  • hugh_gleaves
    6 years ago+ 1 comment

    There's a nasty problem with many of these challenges; thay all assume something about stdin/stdout and unless we know what that is it's tricky to satisfy the tests.

    I have a solution that runs locally the output of which matches exactly what the test says it should be yet the test fails (there are exceptions and nothing written to stdout).

    Im using F# on Windows - if I run under Visual Studio debug and paste the input to the app's consoles I see it write the correct results to the same console.

    Clearly when run on Hackerrank's system the code is seeing different data to when I run locally; but because I have no idea what the app is seeing I can't reproduce and debug it.

    This has happened on several other challenges, far more effort into getting the IO to work as expected than in the actual problem itself.

    It would be far better if we were simply given two filenames rather than the idiosynchractic stdin/stdout.

    UPDATE:

    I just reran the app and specified < input.txt > output.txt as the command line (so it's truly doing file IO not console) and again I get the correct output here...

    I had similar fiddling around with SuperDigit but that eventually ran and passed all tests, I'm using similar IO code for this challenge but hitting a brick wall - I can't spend hours trying to second guess what's going on!

    1|
    Permalink
  • lili_sun_zju
    3 years ago+ 0 comments

    Hi, I have got a WA at case #4. But I check every output of my code with the answer, they are the same. Can someone know what happened?

    Here is my code

    object Solution {
    
     def dpSolver(A:Array[Int], query:Array[Array[Int]] ):Unit = {
        val dp = Array.fill(A.length, A.length)(Int.MaxValue)
        for{i <- A.indices} dp(i)(i) = A(i)
        for{
          i <- A.indices
          j <- i + 1 until A.length
        }
          dp(i)(j) =  A(j) min dp(i)(j-1)
        query foreach {case Array(i,j) => println(dp(i)(j))}
      }
    
      def readArray():Array[Int] = readLine.split(' ').map(_.toInt)
      def main(args: Array[String]) {
        readArray match {
          case Array(n, m) => dpSolver( readArray, Array.fill(m)(readArray))
        }
      }
    }
    
    0|
    Permalink
  • [deleted] 4 years ago+ 0 comments

    Maybe this'll be helpful for those using haskell who have issues with time limits and reading input. This is my go to for reading a bunch of ints:

    import qualified Data.ByteString.Char8 as B
    import Data.List (unfoldr)
    import Data.Char (isSpace)
    
    ints = unfoldr (B.readInt . B.dropWhile isSpace) 
    
    solve (n:xs) = error "some solution to a hackerrank problem"
    main = solve =<< ints <$> B.getContents
    
    0|
    Permalink
Load more conversations

Need Help?


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