Software Programming

Kunuk Nykjaer

Facebook Hacker Cup 2013 Round 1 Solution part 1

leave a comment »


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
}
Advertisements

Written by kunuk Nykjaer

February 3, 2013 at 11:24 pm

Posted in Algorithm, Csharp

Tagged with ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: