Range Minimum Query
Range Minimum Query
+ 0 comments O(N log N + M log N ) time is enough. No fancy Segment Trees required! Fancy Maps are enough.
+ 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 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!
+ 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)) } } }
[deleted] + 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
Sort 14 Discussions, By:
Please Login in order to post a comment