A Random Walk Through Idea Space: Facebook Hacker Cup 2013

This year I did the Facebook Hacker Cup again. I didn’t do as well as last year, only getting to the first round and solving just one problem. It was interesting and fun though. I was in position 1952 of about 10,000 with 877 people solving more problems than me. Lots of people solved just the 3rd question, I wish I had a go at it, next time I’ll be sure to look at them all.

Qualification Round For the qualifier I was in Leeds so didn’t have much time to look at it but solved the first in a few mins as I had most of the ‘plumbing’ (ie taking their input and spitting out a file in the correct format) from last year.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it. The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase 'F’ is exactly as beautiful as lowercase 'f’, for example.) You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

(def letters
  (set "abcdefghijklmnopqrstuvwxyz"))

;; If you don't know clojure it might be interesting that sets are functions of their elements
;; and return either nil or the element, so can be used as predicates

(defn counts [s]
  (frequencies (filter letters (str/lower-case s))))

;; Here we filter the string for letters we care about (after lowercasing it)
;; and create a map of the characters to there count in the string

;; eg (counts "Good luck in the Facebook Hacker Cup this year!")
;; {\a 3, \b 1, \c 4, \d 1, \e 4, \f 1, \g 1, \h 3, \i 2, \k 3, \l 1, \n 1, \o 4, \p 1, \r 2, \s 1, \t 2, \u 2, \y 1}

(defn beauty [s]
  (reduce + (map *
                 (reverse (sort (vals (counts s))))
                 (iterate dec 26))))

;; To make the score as big as possible you want the most frequent letter to be worth 26
;; then each one descending by frequency is work 25, 24 etc
;; (reverse (sort (vals (counts s)))) it the frequencies in descending order
;; (iterate dec 26) is 26, 25, 24 etc
;; we multiply each and then add them

Round 1 I had the evening cleared from about 8pm (it launched 6PM GMT, so I probably lost before I started anyway after seeing how rapidly others did them!)

You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

Easy! 1-liner in clojure.

(defn sum-max-of-subsets [cards k]
  (reduce + (map #(apply max %) (comb/combinations cards k))))

(however it does not scale to the size of the input)

My basic idea to make it faster was using a bit of combinatorics. If the deck is 1,5,7,11… with a hand size (k) of 3 then 1 and 5 will never be the max, 7 will be in the hand [1,5,7] and 11 will be the max of [1,5,11] [1,7,11] and [5,7,11], in general the nth card will be maximum $$n-1\choose k$$ “n-1 choose k” times, so the problem becomes easier, loop thorough the elements finding out how many times it would be the maximum. See here if that does not make sense.

(def factorial
  (memoize (fn [n]
             (reduce *' (range 1 (inc n))))))

(defn nCks [k]
  (let [fac (factorial k)]
    (map #(/ % fac)
         (reductions (fn [acc n]
                       (* acc (/ n (- n k))))
                     fac
                     (iterate inc (inc k))))))

(defn sum-max-of-subsets [cards k]
  (let [sorted (drop (dec k) (sort cards))
        nck (nCks (dec k))]
    (mod (reduce +'
                 (map * sorted nck))
         1000000007)))

(defn bigparse [s]
  (bigint (Integer. s)))

(defn parse-input [line1 line2]
  (let [k (bigparse (second (str/split line1 #"\s+")))
        cards (map bigparse (str/split line2 #"\s+"))
        ]
    (sum-max-of-subsets cards k)))

The final speedup (probably not necessary) was as k is fixed we dont need to calculate nCk every time so I used the Multiplicative Formula for calculating it to get a new value for $$ n\choose k $$ from $$ n-1\choose k $$ by multiplying by n and dividing by n-k each time (what I have called nCks in the code)

For the other problem I groped around the next day trying to solve it, thought 'this looks perfect for core.logic’ then proceeded to procrastinate and watch The Shield and eat bacon. I am OK with this.

Code is of course on github

Menu