This is my solution to the problem of Card Game, work fine for small input… but when the value of k grows (k>500 ) my code spent a lot of time.
The bottleneck it’s about the iteration to find the max in the array…
So i hope you can optimize it 😀
[sourcecode language=”python”]
import sys
import math
from collections import Counter
import re
import itertools
in_file = open(sys.argv[1],"r")
exp = in_file.read()
in_file.close()
inputFile= exp.split("\n")
index=[]
values=[]
def findsubsets(S,m):
return set(itertools.combinations(S, m))
a=[]
flavio=1
for i in range(1, len(inputFile)-1) :
values=[]
allsub=[]
if(i%2) :
# index.append(inputFile[i])
n,k=map(int,inputFile[i].split())
else :
values= map(int,inputFile[i].split())
# Optimization , not call a function
allsub=itertools.combinations(values,k)
my_sum=0
for f in allsub:
my_max=max(f)
my_sum += (my_max)
if(my_sum>=1000000007):
my_sum = my_sum -1000000007
print "Case #"+str(flavio)+": "+str(my_sum)
flavio +=1
[/sourcecode]
GitHub
https://github.com/flaviopace/FacebookHackerCup2_CardGameSolution