Software Programming

Kunuk Nykjaer

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 ```

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();

Run(lines.ToList());

sw.Stop();
Console.WriteLine("Elapsed: {0}", sw.Elapsed.ToString());
Console.WriteLine("press exit.. ");
}

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);
}

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

{
var list = new List<string>();
try
{
{
while (line != null)
{
}
}
}
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
}
```