Hi,
I tried to solve the Ant tower problem 1C in Python and my large Dataset was
wrong (TIME_EXCEEDED). After looking up the Analysis, I found out that the
approach that I took was exactly the approach suggested for the large Dataset.
Thus I tried to optimize my program further so that it solves the large Dataset
and I was not able to do so.
Thus my question is whether it is at all possible to solve it in python 3?
I would also appreciate, if someone could tell me how to speed up my program
code further. This is my final program code:
import sys
T= int(sys.stdin.readline())
for Ca in range(T):
N = int(sys.stdin.readline())
W=[int(i) for i in sys.stdin.readline().split(" ")]
D=[sys.maxsize for i in range(140)]
D[0]=0 #D[i] stores the minimal weight of a tower of height i using only
the first ants
for w in W:# adding an ant
# finding the largest tower made of that ant could carry
# by monotonicity it then can carry also all smaller towers
h= len(D)-1
while(D[h]>6*w):#this stops as D[0]=0
h-=1
#If it can carry: It might be possible to create a less heavy tower of
height h2+1
for h2 in range(h,-1,-1):
D[h2+1]=min(D[h2+1],D[h2]+w)
mh=max([i for i in range(len(D)) if D[i]<sys.maxsize])
print("Case #%i: %i"%(Ca+1,mh))
sys.stdout.flush()
Thanks in advance,
Henrik/ Garfield
--
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/9d95b62f-4c0c-44fe-a7a4-278463ba2e94%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
