HC12 - Card Game

no tags 

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

 

 

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: 2621483Example 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

 


hide comments
Shaily Mittal: 2013-02-15 20:09:20

Please check my code, submission id-8693041, it is working correctly for all the test cases, still wa.. :(

What Does The Fox Say?: 2013-02-15 19:35:54

SIGKILL = maybe your program runs out of memory

Nipun Poddar: 2013-02-14 09:10:15

what may be reason for SIGKILL ???
help plss

Ranker: 2013-02-08 21:25:19

What causes a SIGKILL??

(Tjandra Satria Gunawan)(曾毅昆): 2013-02-06 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: 2013-02-06 18:37:46

can u plz check submission id-8666572

Ehor Nechiporenko: 2013-02-06 17:42:07

Yep, @Franky, but I haven't tried one more optimization. Not the whole array should be sorted ;-)

Francky: 2013-02-06 17:42:07

It seems it could be hard to do less than 0.05s ; only r**d and s**t cost me 0.04s, ... I'll try a python shot to see if feasible.
Edit : It seems really hard to optimize a python solution to get AC, I think time limit should be increased to give a chance to python users, this will not allow 'bad' solutions in fast language to get AC. Please consider this.
@ Ehor : I'll can't follow you on this way, it's yet one of the first time I use a c++ container, ... and sorting is not my cup of tea, I let std do that. But why not try this in Python if time limit is given better. Interesting. ;-)

Edit(by abdelkarim) : now python solutions can get AC ;-) .
--ans(Francky)--> Many thanks for this little help. This give a good challenge for fastest solvers. ;-)

Last edit: 2013-02-06 18:26:27
Ehor Nechiporenko: 2013-02-06 17:42:07

Nice problem, optimized to make source the fastest)

Problem Solver: 2013-02-06 17:42:07

Really cool problem! Thank you.


Added by:abdelkarim
Date:2013-02-02
Time limit:0.245s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Facebook Hacker Cup 2013 Round 1