HC12  Card Game
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 spaceseparated 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.
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 Output: Case #1: 30 Case #2: 400 Case #3: 103 Case #4: 1122 Case #5: 2621483
hide comments
yaseenmollik:
20210602 03:40:47
Combinatorics and some Modular Arithmetics! Ac in one go! Last edit: 20210602 03:40:59 

adarshgaur:
20210104 19:47:25
Easily got a 0.02s AC. 

codephilic:
20201003 15:48:52
I got AC(0.06) after 4WA because of long long int nice problem!! 

scolar_fuad:
20200706 07:18:34
really nice problem .. Last edit: 20200706 11:58:00 

Shaily Mittal:
20130215 20:09:20
Please check my code, submission id8693041, it is working correctly for all the test cases, still wa.. :( 

What Does The Fox Say?:
20130215 19:35:54
SIGKILL = maybe your program runs out of memory 

Nipun Poddar:
20130214 09:10:15
what may be reason for SIGKILL ???


Ranker:
20130208 21:25:19
What causes a SIGKILL??


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130206 20:22:58
wow, It's possible to reach 0.04s... :O That's superfast algo... I give up at 0.07s... First I use mergesort(0.08s, 1.8MB of memory), and then I try timsort(0.07s, 1.9MB of memory).. and I don't know how to become faster than that... I think timsort is the second fastest possible sorting algorithm(source wikipedia: http://en.wikipedia.org/wiki/Timsort#Performance).. But I think I'm wrong.. 0.04s is possible, and I don't know how.. Congratulations, Mitch, Francky, and Ehor Nechiporenko... You're awesome programmer :) 

Archit Mittal:
20130206 18:37:46
can u plz check submission id8666572 
Added by:  abdelkarim 
Date:  20130202 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Facebook Hacker Cup 2013 Round 1 