## Facebook Hacker Cup 2013 Round 1 Solution part 1

## Card Game

References:

FB hacker cup

Analysis

John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.

**Problem**

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.

**Input**

The first line contains the number of test cases T, where 1 ≤ T ≤ 25

Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2 000 000 000, which describe the array a.

**Output**

For test case i, numbered from 1 to T, output “Case #i: “, followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1 000 000 007.

**Example**

For **a = [3, 6, 2, 8]** and **N = 4** and **K = 3**, the maximal numbers among all triples are **6, 8, 8, 8** and the sum is **30**.

**Example input**

`5`

4 3

3 6 2 8

5 2

10 20 30 40 50

6 4

0 1 2 3 5 8

2 2

1069 1122

10 5

10386 10257 10432 10087 10381 10035 10167 10206 10347 10088

**Example output**

`Case #1: 30`

Case #2: 400

Case #3: 103

Case #4: 1122

Case #5: 2621483

**Solution by Facebook**

reference:

The was the simplest problem in the competition with a 60% of success rate. For a given an array a of n distinct integers, we need to print the sum of maximum values among all possible subsets with k elements. The final number should be computed modulo MOD=1000000007, which is a prime number. First we should sort all numbers, such that a [1] < a [2] < ... < a [n]. Let's see in how many times the number a [i] appears as the maximum number in some subsets, provided that i >= k. From all numbers less than a [i] we can choose any k - 1, which is exactly equal to bin [i - 1][k - 1] where bin [n][k] is a binomial coefficient (see http://en.wikipedia.org/wiki/Binomial_coefficient). Therefore, the final solution is the sum of a [i] * bin [i - 1][k - 1], where i goes from k to n, and we need to compute all binomial coefficients bin [k - 1][k - 1], ..., bin [n - 1][k - 1]. That can be done in many ways. The simplest way is to precompute all binomial coefficient using simple recurrent formula bin [0][0] = 1; for (n = 1; n < MAXN; n++) { bin [n][0] = 1; bin [n][n] = 1; for (k = 1; k < n; k++) { bin [n][k] = bin [n - 1][k] + bin [n - 1][k - 1]; if (bin [n][k] >= MOD) { bin [n][k] -= MOD; } } } qsort (a, n, sizeof(long), compare); sol = 0; for (int i = k - 1; i < n; i++) { sol += ((long long) (a [i] % MOD)) * bin [i][k - 1]; sol = sol % MOD; } Note that we are not using % operator in the calculation of the binomial coefficient, as subtraction is much faster. The overall time complexity is O (n log n) for sorting and O (n^2) for computing the binomial coefficients. Another way is to use recurrent formula bin [n + 1][k] = ((n + 1) / (n + 1 - k)) * bin [n][k] and use Big Integer arithmetics involving division. As this might be too slow, these values can be precomputed modulo MOD and stored in a temporary file as the table is independent of the actual input and thus needs to be computed only once. Since MOD is a prime number and use calculate the inverse of the number (n + 1 - k) using Extended Eucledian algorithm (see http://en.wikipedia.org/wiki/Modular_multiplicative_inverse) and multiply with the inverse instead of dividing. This yields on O(n log n) solution. By direct definition bin [n][k] = n! / (n - k)! k!, one can iterate through all prime numbers p less than or equal to n, and calculate the power of p in bin [n][k] using the formula a (n, k) = [n / p] + [n / p^2] + [n / p^3] + ... for the maximum power of p dividing the factorial n!. The most common mistakes were because competitors did not test the edge cases when k = 1 or k = n, and forgot to define bin [0][0] = 1. Another mistake was not storing the result in a 64-bit integer when multiplying two numbers.

**Program.cs**

using System; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; /// <summary> /// Author: Kunuk Nykjaer /// </summary> class Program { static void Main(string[] args) { var sw = new Stopwatch(); sw.Start(); var lines = ReadFile("input.txt"); Run(lines.ToList()); sw.Stop(); Console.WriteLine("Elapsed: {0}", sw.Elapsed.ToString()); Console.WriteLine("press exit.. "); Console.ReadKey(); } static void Run(IList<string> lines) { var result = new List<string>(); var nb = 1; for (var i = 1; i < lines.Count; i += 2) { if (string.IsNullOrWhiteSpace(lines[i])) continue; if (lines[i].StartsWith("#")) continue; var one = lines[i].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries); var two = lines[i + 1].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries); var n = int.Parse(one[0]); var k = int.Parse(one[1]); var numbers = two.Select(int.Parse).ToList(); numbers = numbers.OrderByDescending(x => x).ToList(); var r = Algo(k, numbers); result.Add(string.Format("Case #{0}: {1}", nb++, r)); } WriteFile(result); } static class Binomial { public static long C(long n, long k) { // n! / (k! * (n-k)!) if (n < k) return 0; if (k == 0 || n == 1) return 1; if (n == k) return 1; // This function is less efficient, but is more likely to not overflow when N and K are large. // Taken from: http://blog.plover.com/math/choose.html // long r = 1; long d; if (k > n) return 0; for (d = 1; d <= k; d++) { r *= n--; r /= d; } return r; } } static long Algo(int k, IList<int> numbers) { const long modulus = 1000000007; long sum = 0; for (var i = 0; i < numbers.Count - 1; i++) { long a = numbers[i]; var b = Binomial.C(numbers.Count - 1 - i, k - 1); sum = (sum + ((a * b) % modulus)) % modulus; } sum = sum % modulus; return sum; } #region ** File static IEnumerable<string> ReadFile(string path) { var list = new List<string>(); try { using (var reader = new StreamReader(path, true)) { var line = reader.ReadLine(); while (line != null) { list.Add(line); line = reader.ReadLine(); } } } catch { throw; } return list.ToArray(); } static bool WriteFile(IEnumerable<string> lines) { var fileInfo = new FileInfo("output.txt"); try { using (StreamWriter sw = fileInfo.CreateText()) { foreach (var line in lines) sw.WriteLine(line); } return true; } catch { throw; } } #endregion File }

## Leave a Reply