Thank you, everyone for the advice. I modified my code to apply the % 100003 throughout and I also added a cache for the binomials. This improved the running time for the large set to ~ 30 seconds! Much better. :)
However, I found in my tests that the recursive definition of the choose function was actually *slower*. Using the factorial version the running time was 32 seconds, but when I tried the recursive version it took 62 seconds. I assume that is because the overhead of the recursive functions in python is too much? (Compared to the factorial library function which is implemented in C I suspect). -- 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.
