Programming Praxis

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

1. Facebook Hacker Cup 2013, Round 1, Problem 1 | My Blog said

   February 15, 2013 at 9:06 AM

   […] Pages: 1 2 […]
2. Programming Praxis – Facebook Hacker Cup 2013, Round 1, Problem 1 « Bonsai Code said

   February 15, 2013 at 11:01 AM

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

   February 15, 2013 at 11:01 AM

   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))
   
4. Paul said

   February 15, 2013 at 2:39 PM

   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
   
5. razvan said

   February 16, 2013 at 1:53 PM

   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.
    * https://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;
   	}
   }
   
6. Luke said

   March 3, 2013 at 9:37 PM

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

   June 18, 2013 at 5:03 PM

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