> h= len(D)-1
> while(D[h]>6*w):#this stops as D[0]=0
> h-=1
The part quoted above makes the algorithm O(n^2) instead of O(nk). (n = number
of ants, k = max height of stack).
We may think that O(nk) and O(n^2) are similar (so do I). But we are wrong.
Instead, for W <= 10^9 we can obtain the result k <= 139. (For the minimal
possible weights, use W_1 = 1, W_(n+1) = CEILING(SUM(W_1 .. W_n) / 6)).
So by using a O(n^2) implementation that part of the code will run 700x slower
if n=100000.
To fix this, you can:
(1) Use binary search instead.
(2) Perform a sequential search, but start from h=0 instead.
(3) Or start from h = maximum of previous height, like what Xiongqi did.
And also, using len(D) or max(..., ...) in the loop appears to be a fatal
mistake in python 3. Apparently these functions are very slow. I'm sure that in
C++ both functions are non-issues.
I'm not sure if the use of arbitrary sized int in Python 3 makes things worse.
Anyway, here's my optimized code after a few tries. Compare with Xiongqi's to
see the difference.
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
dsize = len(D)
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= 0
while(h < dsize and D[h] <= 6*w):
h+=1
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):
if D[h2 + 1] > D[h2] + w:
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()
On Saturday, May 5, 2018 at 1:49:48 PM UTC, [email protected] wrote:
> 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/e41be100-50de-4593-abdf-2633a6ab5b1a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
