Fork me on BitBucket

Facebook Hacker Cup 2013

Hacker Cup kicked off this weekend with a 72 hour qualification round. The grand prize is 10K and cash prizes go down to 25th place! (+ flights for the top 25 to FBHQ). With over 10,000 competitors there were many interesting solutions and pitfalls people ran into. The qualification round ran smoothly although people (including myself) are "disgruntled" with how long it takes facebook to confirm results. (People expect instant gratification these days :P )

The least solved problem was Find The Min. A lot of people couldn't get the solution within the 6 minute time limit because they tried using a O(n) solution or an O(k^2) solution. Below is my O(K) solution that many will be interested to see. It uses c[num] to keep track of which numbers have been used recently and are unavailable. Any number that is "freed" is appended as the next min if it is smaller than the previously found min, otherwise the next smallest available number is found and appended. We only need to find the first few minimums because they start repeating after a while.

__author__ = 'robert'

from itertools import count
from collections import Counter

data = open("in3b.txt")
cases = int(next(data))

for case in range(1, cases + 1):
    n, k = map(int, next(data).split())
    a, b, c, r = map(int, next(data).split())
    known = [a]
    for i in range(k - 1):
        known.append((b * known[-1] + c) % r)
    c = Counter(known)
    finder = (i for i in count(0) if not c[i])
    found = next(finder)
    c[found] += 1
    for j in range(k + 1):
        freed = known[j]
        c[freed] -= 1
        if c[freed] == 0 and freed < found:
            c[freed] += 1
            found = next(finder)
            c[found] += 1
    remainder = n % (k + 1)
    if n < len(known):
        ans = known[n - 1]
        ans = known[(k + 1) + remainder - 1]
    print "Case #{0}: {1}".format(case, ans)

page divider

Random Quote