# 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