Facebook Hacker Cup 2013, Round 1, Problem 1

February 15, 2013

Round 1 of the Facebook Hacker Cup 2013 is now complete. In today’s exercise we look at Problem 1:

CARD GAME (20 points)

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 ≤ 10000 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 1000000007.

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] ≤ 2000000000, 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 1000000007.

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

Your task is to write a program that solves the Facebook problem given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

7 Responses to “Facebook Hacker Cup 2013, Round 1, Problem 1”

  1. […] today’s Programming Praxis exercise, our goal is to solve the first problem of the 2013 Facebook hacker […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/15/programming-praxis-facebook-hacker-cup-2013-round-1-problem-1/ for a version with comments):

    import Data.List
    
    facts :: [Integer]
    facts = scanl (*) 1 [1..]
    
    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))
    
  3. Paul said

    A Python version. The gmpy library is used for speed.

    import gmpy
    
    def sumup(arr, k):
        arr.sort(reverse=True)
        n = len(arr)
        return sum(ai * gmpy.bincoef(n - 1 - i, k - 1)
            for i, ai in enumerate(arr[:n - k + 1])) % 1000000007
    
  4. razvan said

    Here’s my Java solution:

    package cardgame;
    
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * This class solves the card game problem from Facebook Hacker Cup 2013 round 1.
     * http://programmingpraxis.com/2013/02/15/facebook-hacker-cup-2013-round-1-problem-1/
     *
     */
    public class CardGame {
    
    	private static final int MOD_FACTOR = 1000000007;
    	private int[][] decks;
    	private int[] handSizes;
    
    	/**
    	 * Main method. Expects one command-line argument: the name of the input file.
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		if(args.length > 0) {
    			try {
    				CardGame cg = new CardGame();
    				cg.parseFile(args[0]);
    				int[] strengths = cg.totalHandStrengths();
    				for(int i=0; i<strengths.length; i++) {
    					System.out.println("Case #" + (i + 1) +": " + strengths[i]);
    				}
    			} catch (FileNotFoundException e) {
    				System.out.println("File not found");
    			}
    		} else {
    			System.out.println("Supply file name as argument");
    		}
    
    	}
    
    	/**
    	 * This method parses the input file. 
    	 * The input's format is described in the problem statement.
    	 * @param fileName name of input file
    	 * @throws FileNotFoundException
    	 */
    	public void parseFile(String fileName) throws FileNotFoundException {
    		Scanner sc;
    		sc = new Scanner(new File(fileName));
    		int t = sc.nextInt();
    		decks = new int[t][];
    		handSizes = new int[t];
    		for(int i=0; i<t; i++) {
    			int n = sc.nextInt();
    			handSizes[i] = sc.nextInt();
    			decks[i] = new int[n];
    			for(int j=0; j<n; j++) {
    				decks[i][j] = sc.nextInt();
    			}
    		}
    	}
    	
    	/**
    	 * This method computes the total strength of all hands 
    	 * for each (hand, hand size) pair in the input file.
    	 */
    	public int[] totalHandStrengths() {
    		int [] strengths = new int[decks.length];
    		for(int i=0; i<decks.length; i++) {
    			Arrays.sort(decks[i]);
    			strengths[i] = handStrengths(decks[i], handSizes[i], decks[i].length);
    		}
    		return strengths;
    	}
    
    	/**
    	 * This method computes the total hand strength for the first n cards in deck, where hands
    	 * have size k.
    	 * @param deck The deck of cards. This is assumed to be sorted.
    	 * @param k    The size of a hand of cards.
    	 * @param n    The number of cards in the deck.
    	 * @return     Integer representing sum of scores of hands in deck.
    	 */
    	private int handStrengths(int[] deck, int k, int n) {
    		if (k == n) {
    			return deck[n-1];
    		}
    		// Make as many k-tuples you can that include the maximum card
    		// Then, remove maximum and recurse.
    		return (deck[n-1] * choose(n-1, k-1) + handStrengths(deck, k, n-1)) % MOD_FACTOR;
    	}
    
    	/**
    	 * This method computes n choose k.
    	 * (How many subsets of size k there are in a set of size n)
    	 */
    	private int choose(int n, int k) {
    		int answer = 1;
    		for(int i=n-k+1; i<=n; i++) {
    			answer = answer * i;
    		}
    		for(int i=1; i<=k; i++) {
    			answer /= i;
    		}
    		return answer;
    	}
    }
    
  5. Luke said

    Easier to fill out 10001 rows of Pascal’s triangle, nCr is the rth column of the nth row.

  6. brooknovak said

    Her is a solution in C#. As it hunts for combos of sets with size = k, it tracks the max as it goes, and additively computes the final sum.

    public class DeckSums
    {
    	private long totalSum;
    	private int[] strengths;
    	private int k;
    
    	public DeckSums(int[] strengths, int k) {
    		this.strengths = strengths;
    		this.k = k;
    		totalSum = 0;
    	}
    
    	public int ComputeDeckSums() {
    		FindComboSums (0, -1, 0);
    		return (int)totalSum;
    	}
    
    	private void FindComboSums(int n, int max, int len) {
    		// Base case: dont both attempting to find combinations any further since from
    		// this point we cannot reach a length of k
    		if (len + (strengths.Length - n) < k)
    			return;
    
    		for (int i = n; i < strengths.Length; i++) {
    			int val = strengths [i];
    			int newMax = val > max ? val : max;
    			if (len + 1 == k) {
    				totalSum += newMax;
    				totalSum %= 1000000007;
    			} else {
    				FindComboSums (i + 1, newMax, len + 1);
    			}
    		}
    	}
    }
    

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

Follow

Get every new post delivered to your Inbox.

Join 644 other followers

%d bloggers like this: