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!

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

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?

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

I am getting timeout for test cases 5, 6, 7. When I debugged with the inputs I've seen that my timeout occurs while creating the Segmentation Tree.

I have been looking into the code for 2 days and I still could not figure out what is the cause of this.

You can find my tree construction code below. Any help is appreciated.

def makeTree(ll:List[Int], l:Int, r:Int): Tree[Int] = {   
        if (r==l) {
            Leaf(ll(l), l, r)
        }
        else {
            var left = makeTree(ll, l, (l+r)/2)
            var right = makeTree(ll, (l+r)/2+1, r)
            //println(l,r,List(left.value, right.value).min)
            Node(left, right, List(left.value, right.value).min, l, r)
        }               
    }

ll is the input array. Leaf and Node needs no explainations I believe.

I am getting timeout for test cases 5, 6, 7. When I debugged with the inputs I've seen that my timeout occurs while creating the Segment Tree.

I have been looking into the code for 2 days and I still could not figure out what is the cause of this.

You can find my tree construction code below. Any help is appreciated.

def makeTree(ll:List[Int], l:Int, r:Int): Tree[Int] = {   
        if (r==l) {
            Leaf(ll(l), l, r)
        }
        else {
            var left = makeTree(ll, l, (l+r)/2)
            var right = makeTree(ll, (l+r)/2+1, r)
            
            Node(left, right, List(left.value, right.value).min, l, r)
        }               
    }

ll is the input array. Leaf and Node needs no explainations I believe.

I am having a rather bizarre issue. On my computer, when I run on testcase #4 it runs quickly when compiled with no optimizations or even interpreted. However when I compile with -O2 it slows to a crawl. Any ideas? I am using ghc 7.10.2 and my most recent submission is at https://www.hackerrank.com/challenges/range-minimum-query/submissions/code/14985614

I have written RMQ in logn algorithm for each query in scala, but I still have "Terminated due to timeout" for three last test cases. Any suggestions?

Hi, after submitting a seemingly endless amount of attempts to solve this problem I was finally able to do it without timing out. Trying to solve it, I quickly realized that there was no problem with my data structure (segment tree), but with the way the input was parsed. The problem always appeared in test #4-7 where the time consumption suddently did not scale with the amount of input. Test #3 took about 0.07 seconds to solve, but #4 took 2.5 seconds and the rest just timed out. What is confusing me is that this huge increase did not occur own my own computer, but only on the Hackerrank server.

Here is one example of code that exhibited this behaviour (excluding code for the actual problem):

import Control.Monad (replicateM_, forM_, mapM_)
import Data.Vector as V hiding (map, zip, forM_, mapM_)
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as C

int :: C.ByteString -> Int
int = fst . fromJust . C.readInt

main :: IO ()
main = do 
    [s, t] <- fmap (map int . C.split ' ') C.getLine :: IO [Int]
    vec <- fmap (V.fromList . map int . C.split ' ') C.getLine :: IO (Vector Int)
    let tree = buildTree vec (s-1)
    forM_ [1..t] `$ const $` do
      [l,u] <- fmap (map int . C.split ' ') C.getLine :: IO [Int]
      print $ getMin l u tree

And here is the code that finally did not time out:

import Control.Monad (replicateM_, forM_, mapM_)
import Data.Vector as V hiding (map, zip, forM_, mapM_, take)
import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as C

int :: C.ByteString -> Int
int = fst . fromJust . C.readInt

main :: IO ()
main = do 
    (x:xx:xs) <- C.lines `fmap` C.getContents
    let [s,t] = map int (C.split ' ' x)
        vec = V.fromList . map int . C.split ' ' $ xx
        tree = buildTree vec (s-1)
    mapM_ (\[l,u] -> print `$ getMin l u tree) (map (map int) . map (C.split ' ') . take t $` xs)

Could someone please explain why this big difference in performace occurs and also why it only happens on the Hackerrank server and not locally.

I have written codes in 3 different approaches but just cannot pass all the test cases. How are OCaml codes compiled and test? ocamlopt a.ml or ocamlc a.ml.