In today’s Programming Praxis exercise, our goal is to solve the first problem of the 2013 Facebook hacker cup, which is to give the sum of the highest values of all possible subsequences of length k of a given list of integers. Let’s get started, shall we?
A quick import:
For this problem, we’re going to need to calculate a lot of binomial coefficients, i.e. the amount of ways to choose k out of n items. This involves calculating factorials. The trivial way to do this in Haskell is to use product [1..n], but that’s not very efficient when you need to calculate many different factorials. So instead we create a lazy lookup table of all factorials, so that we save a lot of duplicated effort.
facts :: [Integer]
facts = scanl (*) 1 [1..]
The brute force way to solve the problem would be to simply enumerate all possible subsequences and sum their maximums. Unfortunately there are a LOT of combinations once you get to the maximum number of 10000 possible values (just printing 10000 choose 5000 takes several terminal screens), so clearly that’s not going to work. Instead, we can solve the problem in O(n) by realizing that each number will be the highest in every combination with lower numbers, e.g. the highest number will occur (n-1) choose (k-1) times, the second highest (n-2) choose (k-2) times, etc. Since the answer needs to be given modulo 1000000007, we do this at every step in order to keep the total down.
facebook :: Int -> [Int] -> Integer
facebook size = foldr (\(i,x) a -> mod (a + x * choose (size-1) i) 1000000007) 0 .
drop (size - 1) . zip [0..] . map fromIntegral . sort where
choose k n = div (facts!!n) (facts!!k * facts!!(n-k))
Some test cases to see if everything is working properly:
main :: IO ()
main = do print $ facebook 3 [3,6,2,8] == 30
print $ facebook 2 [10,20,30,40,50] == 400
print $ facebook 4 [0,1,2,3,5,8] == 103
print $ facebook 2 [1069,1122] == 1122
print $ facebook 5 [10386,10257,10432,10087,10381
,10035,10167,10206,10347,10088] == 2621483
print $ facebook 1 [3,4] == 7
print $ facebook 3 [3,4,5] == 5
print $ facebook 5000 [1..10000]
The worst-case scenario, 5000 cards and 10000 numbers, takes just under 5 seconds. Since there’s a maximum of 25 test cases, the total time should be about two minutes at most. Not too bad.