I missed this question during the competition because I mis-read it - doh!
Then after I figured out what it was asking I came up with a solution that
solves the small case but it runs too slow on the large set. What
optimization I am missing?
def XchooseN(x,n):
return factorial(x) / ( factorial(n) * factorial(x-n) )
cache = {}
def solve(N, K):
global cache
if K < 1: return 0
if K == 1 or K == 2: return 1
if (K == (N-1)): return 1
if (N,K) in cache: return cache[(N,K)]
r = sum((solve(K,Kp) * XchooseN(N-K-1,K-Kp-1) for Kp in
xrange(2*K-N, K)))
cache[(N,K)] = r
return r
if __name__ == '__main__':
while test_case < test_case_count:
r = sum((solve(N,K) for K in xrange(1,N)))
print "Case #%d: %s" % (test_case, r % 100003)
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
