I have no idea what language is that, but I assume its using some big integer data type which makes slow, but you don't have to do % 100003 at the end
using this two properties of modular arithmetic the values never grow big (x + y) % M == (x % M + y % M) % M (x * y) % M == (x % M * y % M) % M for the choose, it wont work as is, if it is still slow you can use a choose of the form choose(n,k) = chose(n-1,k-1) + choose(n-1,k) you can apply modular arithmetic to that formulation, and even cache. I'll let you figure out the base cases. Carlos Guía On Sat, May 22, 2010 at 9:18 PM, 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]<google-code%[email protected]> > . > For more options, visit this group at > http://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.
