q-3.coffee

###
  q-3.coffee
  Facebook Hacker Cup Qualifications - Problem 3
###

# takes in two strings of input, and returns the nth value of m
f = (input1, input2) ->
  # parse the input strings to get the variable values
  split = input1.split ' '
  n = Number split[0]
  k = Number split[1]
  split = input2.split ' '
  a = Number split[0]
  b = Number split[1]
  c = Number split[2]
  r = Number split[3]

  # create m and initialize it with known values using the given formula
  m = [a]
  m[i] = (b * m[i-1] + c) % r for i in [1...k]

  # create a hash so we can quickly lookup which values are already used
  mHash = {}
  mHash[v] = (mHash[v] or 0)+1 for v in m

  # find the minimum value, insert it into m, repeat
  # the trick here that makes this fast (even with big numbers) is that
  #   we only need to do this up to m[(k+1)*2], not m[n-1] (the naive way),
  #   because after m[k], the values just repeat
  min = 0
  prevMin = -1
  for i in [k..((k+1)*2)]
    j = min
    while true
      if not mHash[j]? or mHash[j] <= 0
        mHash[j] = (mHash[j] or 0)+1
        m[i] = j
        min = j
        break
      j++
    if prevMin != -1
      min = prevMinv
      prevMin = -1
    mHash[m[i-k]]--
    if m[i-k] < min
      prevMin = min
      min = m[i-k]

  # this value will be the same as m[n-1]
  return m[((n-1) % (k+1)) + k + 1]


# read input file, convert it to an array of strings
fs = require 'fs'
filename = process.argv[2]
text = fs.readFileSync filename, 'utf8'
lines = text.split '\r\n'
t = Number lines[0]
input = lines.slice 1

# run the cases in separate processes for paralellization
fork = require('child_process').fork
if not process.argv[3]?
  cpus = require('os').cpus().length
  processes = []
  outputs = []
  done = 0

  for i in [0...t]
    spawn = ->
      $i = i
      processes[$i] = fork 'q-3.js', [filename, $i]
      processes[$i].on 'message', (message) ->
        outputs[$i] = message
        done++
        if done == t
          console.log "Case ##{Number(i)+1}: #{v}" for v,i in outputs

    spawn()

else
  # process input and write to stdout
  i = Number process.argv[3]
  process.send f input[i*2], input[i*2+1]
  process.exit()