So I became a bit obsessed yesterday tying to get this to pass. Late last
night, I finally got a solution that barely passed. My solution inverts the
order of the two variables vs. your solution (stack height vs. "first i" ants).
My key function is shown below.
def solve(inp) :
(n,w) = inp
w6 = [6*x for x in w]
dp = list(itertools.accumulate(w,min))
for stackSize in range(2,n+1) :
olddp = [1e99] + dp[:n]
candidates = [ 1e99 if x6 < odp else x + odp for x,x6,odp in
zip(w,w6,olddp) ]
dp = list(itertools.accumulate(candidates,min))
if dp[-1] == 1e99 : return "%d" % (stackSize-1)
return "%d" % n
The performance key was to try to accomplish work that was normally done in
"inner" loops with itertools.accumulate or list comprehensions.
I would be very curious as to why the problem posers selected a time limit that
made it very hard to make python solutions pass. Is there really a competing
"inferior" algorithm that required these limits for C++?
More generally, Code Jam has a tradition with being quite tolerant of a wide
range of programming solutions (with historical 4/8 minute limits). With the
loss of the "multiprocessing" trick python trick for parallelism, and with
these tight time limits (perhaps without good reason?), I'm afraid that python
will be at a significant disadvantage vs. the past.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/8d808d8f-be39-4f39-85e2-004f43c8ba70%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
