Thank you very much! (p.s. it's python)
On Sat, May 22, 2010 at 10:46 PM, Carlos Guia <[email protected]> wrote: > 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]<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.
