Another point is to use array (2-D list) instead of dict to implement
cache. this will reduce the time complexity of cache lookup operation
from O(logN) to O(1)
Chris Carton ??:
Thank you very much!
(p.s. it's python)
On Sat, May 22, 2010 at 10:46 PM, Carlos Guia <[email protected]
<mailto:[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]
<mailto:[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]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto: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]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto: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.
--
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.
