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?

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!

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))
    }
  }
}

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