# Programming Praxis

A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer

## Facebook Hacker Cup 2013, Round 1, Problem 1

### February 15, 2013

The first step is to understand the problem. Consider the example with N = 4, K = 3, and a = [3, 6, 2, 8]. There are four different triples that can be formed from the input array: [3, 6, 2], [3, 6, 8], [3, 2, 8] and [6, 2, 8]. The maximums of those triples are 6, 8, 8 and 8, and the sum of the maximums is 30, which is the desired output.

In general, if we sort the array, the smallest K – 1 items in the array will never be maximums, so the desired output will be the sum of the product of each of the highest array items times the number of different ways to choose the lower items. In the example, there is 1 maximum of 6 and 3 maximums of 8, producing a sum of 30. The number of ways to choose the lower items is given by the binomial theorem, the function nCr where n is the number of items available and r is the number of items to choose. In the example, nCr(2,2)=1 is the number of ways that 3 items can be chosen from a list of 3, and nCr(3,2)=3 is the number of ways 3 items can be chosen from a list of 4. Note that, for our problem, c is K-1 and n ranges from K-1 to N-1. The nCr function can be computed as $\frac{n!}{r! (n-r)!}$ and implemented like this (nCr is normally pronounced “choose”, because it is the number of ways to choose r items out of n):

```(define (choose n r)
  (if (zero? r) 1
    (* n (/ r) (choose (- n 1) (- k 1)))))```

However, that doesn’t work for this problem because of the requirement that solutions are given modulo 1000000007; there is no division in modular arithmetic. What we can do instead is multiply by the modular inverse, and since the limit on K is 10000, we can precompute the modular inverses. Here are some convenient constants for the problem limits, a function to compute the modular inverse, a function that precomputes the 10000 needed inverses, and a function that computes the choose function:

`(define m 1000000007)`

`(define n 10000)`

```(define (inverse x m)
  (let loop ((x x) (a 0) (b m) (u 1))
    (if (positive? x)
        (let ((q (quotient b x)) (r (remainder b x)))
        (loop (modulo b x) u x (- a (* q u))))
        (if (= b 1) (modulo a m) #f))))```

```(define inv
  (let ((inverses (make-vector (+ n 1) 0)))
    (do ((x 1 (+ x 1))) ((< n x))
      (vector-set! inverses x (inverse x m)))
    (lambda (x) (vector-ref inverses x))))```

```(define (choose n k)
  (if (zero? k) 1
    (modulo (* n (inv k) (choose (- n 1) (- k 1))) m)))```

With that, the function that computes the output for a given set of inputs is simple; it uses `drop` from the Standard Prelude:

```(define (f n k as)
  (let loop ((i (- k 1)) (as (drop (- k 1) (sort < as))) (s 0))
    (if (null? as) s
      (loop (+ i 1) (cdr as) (+ s (* (choose i (- k 1)) (car as)))))))```

This just loops with i counting the number of items available to be chosen, as listing the successive maximums, and s is the accumulating sum. Here are some examples:

```> (f 4 3 '(3 6 2 8))
30
> (f 5 2 '(10 20 30 40 50))
400
> (f 6 4 '(0 1 2 3 5 8))
103
> (f 2 2 '(1069 1122))
1122
> (f 10 5 '(10386 10257 10432 10087 10381 10035 10167 10206 10347 10088))
2621483```

The Facebook problem requires some specific input and output formatting, but we’ll ignore that. You can run the program at http://programmingpraxis.codepad.org/S0qgV4pB.

### Like this:

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
6 Comments »

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

1. February 15, 2013 at 9:06 AM

[...] Pages: 1 2 [...]

2. 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

```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.
 * 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;
	}
}
```
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.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 1, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8724403381347656, "perplexity_flag": "middle"}