Facebook Hacker Cup 2013 Round 1 Problem 1

Wow, I have to say I was at first skeptical of a 24 hour round 1 in the Facebook Hacker Cup... but these problems were quite challenging. I'm going to break this up into three posts, one for each of the problems I attempted.


The first problem was as follows...

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.

The more intuitive explanation was from the problem statement... imagine that you have N cards in a deck, each representing a different value.  You randomly select K cards to make your hand, and the strength of your hand is equal to the card with the highest value... so for instance if you had the hand (2, 4, 6, 8)... your hand would score as 8.

Now given this, you want to consider all possible hands, and figure out the average score.  More specifically, you just want the sum of all hands mod 1000000007.  To solve this problem, you are given N, K, and the array A containing all the values in the deck.

My approach was to solve the problem looking at each element of A, asking how many possible hands exist given that this card is the highest in the hand.  So imagine we have A sorted as follows, with K = 3 and N = 10....

(2, 5, 6, 8, 9, 12, 15, 17, 19, 20)

if we consider how many K=3 card hands could have 15 as the highest card, we recognize that we need to select two cards from the set to the left of 15.  So in this case, we want 2 Choose 6 to fill out the remainder of the hand ( remember that K Choose N = N!/(K!*(N-K)!) ).. so in this case there are 15 possible 3 card hands from this set where 15 is the highest card.

Generalizing this to sum all possible hands together, and taking into account we get the main part of the program looking something like this...

public String Solve(int n, int k, List a)
{
    int mod = 1000000007;
    var answer = a.OrderBy(i => i).ToList().Select((strength, i) => (combinations(i, k - 1, mod) * (strength % mod)) % mod).Sum() % mod;
    return answer.ToString();
}

The next thing to note is the nature of big numbers... factorials combined with the sizes of the data sets means that you must be capable of taking care of the modulo requirement mid calculation.  First, we recognize the large prime number provided in the problem means we can structure the answer in terms of congruent answers...  I found this cheat sheet from U.C. San Diego to brush up on rules of modular arithmetic... and the section one rules tell us that if our binomial coefficient operator produces a congruent value mod the given modulo, we can just keep modding at each step of the operation to get an equivalent answer.  I had to look up an example of fast binomial coefficient generation, since my attempts overflowed with big numbers or were inaccurate... I found my baseline on stackoverflow here.

So that was my answer to the first problem... more to come with my approaches to the other two problems.