Skip to content

Instantly share code, notes, and snippets.

@mappum
Created January 29, 2013 07:16
Embed
What would you like to do?
###
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment