hi All

this weekend was on of the most fun filled problem solving weekend ever. All the three problems in the Online Round one were difficult in one way or the other. I only solved the first problem, that too in a language I was coding for the first time, glad to know the solution is correct!

Reading the first problem statement, the Card Game Problem I could almost immediately judge there was a pattern within the given problem sets. The only problem here was not the problem itself, but the language I love the most ( offcourse it is PHP!... ) the limitations given would generate numbers as large as >10^13 and I very well knew, working on the WAMP stack (32-bit) would just not solve it, and at the same time, LAMP stack might do it, but it would be too long.

Since I was already working on Aptana, there was no better option to use ruby or python, because of the inbuilt support. Due to many other factors I inclined towards python and wrote my first ever problem solver code. It may not be optimized but it works to solve the problem set in less than 2 secs.

Without boring you further, the problem set was as follows:

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.

Sample 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

Sample Output:

Case #1: 30
Case #2: 400
Case #3: 103
Case #4: 1122
Case #5: 2621483

Solution:

well the problem statement takes time to understand, but definitely there is pattern, and you can see it sometime, later, it took me quite sometime to figure this out, I already could make out several relations with combinatorics, nCr and all.

later I realized the pseudo algorithm can be like:

sort array desc
total = 0
while (n-i) is not k{
    total = total + (a[n-i] * [n-i]C[k-1])
}

so writing this code in PHP works, but fails on large data sets. Finally the code in python I wrote becomes:

import gmpy2

file        = open("card_game.txt")
o_file      = open("output.txt",'w')
testcases   = int(file.readline())
current     = 0

while current < testcases:
    current = current + 1
    data_nk = file.readline().split()
    n       = int(data_nk[0])
    k       = int(data_nk[1])
    vals    = [int(i) for i in file.readline().split()]
    vals.sort()
    total   = 0
    i       = 0
    while (n-i) >= k:
        i       = i + 1
        cval    = vals.pop()
        total   = total + (cval * gmpy2.comb((n-i), (k-1)))
        if total > 1000000007:
            total   = total % 1000000007
    o_file.write("Case #%s: "%current)
    o_file.write("%s"%total)
    if current < testcases:
        o_file.write("\n")

I use the gmp library available for almost all languages, in Python it is gmpy2 package. This code has scope for a lot of improvement. Please update me regarding this, would love to hear it from you.

Also, the rank that has been awarded to me is 2129 so I am pretty much happy with this.

Cheers!