compute all factorials and all binomials (XchooseN) in advance. keep them in a list array, and don't call a function while running solve. calling functions in Python is a very costly operation. after making that change I've noticed a x30 improvement in running time (on my code) - no joke!
one last thing: you should make the effort to learn python 3 and advance to the new versions. you'll have much better built-in modules there. On May 23, 4:18 am, Chris Carton <[email protected]> wrote: > 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 > athttp://groups.google.com/group/google-code?hl=en. -- 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.
