Card Game solution: Facebook hacker cup 2013 Round1

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the first question(Carried 20 marks out of 100) for the Round 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.

Problem Statement

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:

To explain the problem in easier words, we need to get the K sets out of N cards and get the maximum number from each set and sum them up. Also as this number might be too high so they asked us to modulo the sum with 1 000 000 007.

So to solve it, first take the maximum number and count the sets in which this number will be present (i.e. C(n-1, k-1)), then take the next maximum number and count the sets in which this number will be present(except already counted sets) (i.e. C(n-2, k-1) and keep on considering next highest numbers till we get >= C(n,k) sets.

Trick is to write the combination method such that we don’t get overflow issue and keep on doing modulo by 1 000 000 007 at every stage to avoid overflow problem.

Also we are using this property of combinations to avoid multiple calculations.

C(n-1, k) = (n-k)*C(n,k)/n;

here is the java code for above proposed solution:

import java.util.ArrayList;
import java.util.Collections;


public class CardGame {

	long MODULO_BASE = 1000000007;
	
	public long getSum(int n, int k, ArrayList<Integer> input){
		Collections.sort(input);
		
		long totalNumberOfSets = (long) combination(n, k);
		long firstHeighestNumberOfSets = k*totalNumberOfSets/n;

		long sum = 0;
		long currentSetsCount = 0;
		int count = 0;
		int newN = n;
		int newK = k;
		for(int i = input.size() -1; i >=0; i--){
			count++;
			long num = input.get(i);
			long tempSetCount = 0;
			if(count == 1)		
			{
				tempSetCount = firstHeighestNumberOfSets;//(long) combination(n - count, k-1);
				newN = n-1;
				newK = k-1;
			}else{
				if(newN == 0 || newN -newK ==0){
					tempSetCount = (long) combination(n - count, k-1);
				}else{
					tempSetCount = firstHeighestNumberOfSets * (newN - newK)/newN;
					firstHeighestNumberOfSets = tempSetCount;
					newN--;
				}
			}
			
			if(currentSetsCount + tempSetCount > totalNumberOfSets){
				tempSetCount = totalNumberOfSets - currentSetsCount;
			}
			num = (num%MODULO_BASE);
			tempSetCount = (tempSetCount%MODULO_BASE);
			sum = sum + num*(tempSetCount);
			if(sum > MODULO_BASE){
				sum = sum - MODULO_BASE;
			}
			currentSetsCount += tempSetCount;
			
			if(currentSetsCount == totalNumberOfSets){
				break;
			}
		}
		
		return sum;
	}
	
	public static double combination(int n, int k){
		if(k > n-k){
			return combination(n , n-k);
		}
		double result = 1;
		
			for(int i =0; i < k; i++){
				result = result*(n - i); 
				result = result/(k -i);
			}
		return result;
	}
}

Facebook Comments