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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Range Minimum Query
You are viewing a single comment's thread. Return to all comments →
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):
And here is the code that finally did not time out:
Could someone please explain why this big difference in performace occurs and also why it only happens on the Hackerrank server and not locally.