Implementation of the solution to the third problem of the qualification round of the 2013 Facebook Hacker Cup

findmin.scala

import scala.io.Source
import java.io.PrintWriter
import scala.collection.mutable.Queue
import scala.collection.mutable.BitSet

object findmin extends App {
  
  def rfm(j: Int, n: Int, k: Int, m: Queue[Int], csm:BitSet): Int = {
    if (j==n) m.last
    else if (j > 2*k){
      m += csm.head
      m( (k+(n-j)-1) % (k+1) )
    } 
    else {
      val min = csm.head
      val out = m.dequeue
      m += min
      if (m.contains(out)) rfm(j+1, n, k, m , csm -= min )
      else rfm(j+1, n, k, m , (csm += out) -= min )
    }
  }
  
  def complement(m:Queue[Int], k:Int): BitSet = {
    var c = BitSet.empty
    for ( i <- k to 0 by -1 ) c += i
    for ( e <- m ) c -= e
    c
  }

  def genFirstK(k: Int, a: Int, b: Int, c: Int, r: Int): Queue[Int] = {
    val m = new Array[Int](k)
    m(0) = a
    for (val i <- 1 until k) m(i) = ((b.toLong*m(i-1).toLong+c.toLong)%r.toLong).toInt
    Queue.empty[Int] ++= m
  }
  
  def findMin(n:Int, k:Int, a:Int, b:Int, c:Int, r:Int): Int = {
    val m = genFirstK(k,a,b,c,r)
    val csm = complement(m,k)
    rfm(k,n,k,m,csm)
  }
  
  def consolidate(dp: List[String], acc: List[String]): List[String] = {
    if (dp.isEmpty) acc
    else consolidate(dp drop 2, acc :+ dp(0)++" "+dp(1))
  }
  
  def dispatchSolving(s: String): Long = {
    val tokens = s.split(' ') map (_.toInt)
    findMin(tokens(0),tokens(1),tokens(2),tokens(3),tokens(4),tokens(5))
  }
  
  val input = Source.fromFile("input")
  val output = new PrintWriter("output")
  
  val lines = input.getLines.toList
  val n = (lines take 1)(0).toInt
  val problem_strings = lines drop 1
  val problems = consolidate(problem_strings,List())
  
  val startTime = System.currentTimeMillis
  val results = (problems.par map dispatchSolving).toList
  val elapsedTime = System.currentTimeMillis - startTime
  
  println("Elapsed Time: " + elapsedTime/60000 + "m " + (elapsedTime%60000)/1000 + "s " + elapsedTime%1000 + "ms" );
  
  val lp = ( (1 to n).toList,problems,results ).zipped.toList map { case (n, problem, result) => output.println("Case #" + n + ": " + result) }
  
  input.close
  output.close
}