Discussion on Range Minimum Query Challenge

Sort 14 Discussions, By:

3 years ago+ 0 comments

Could you please add Python as a possible programming language?

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

[deleted] 5 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

6 years ago+ 0 comments

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.

6 years ago+ 0 comments

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.

Load more conversations