Tle fert21_0

[dursalakihoegalo]

My code produces correct results with some random inputs and runs fine in IDEONE.

Please suggest me what can be done to make it faster. Thank You

import sys
import psyco
psyco.full()
def main():
    s = sys.stdin
    t = s.readline()
    for i in s:
        n = int(i)
        if n==1: print '1'
        else:
            n-=1
            mul5 = 5**n
            strmult5 = str(mul5)
            l = len(strmult5)
            ans = '0.'
            for i in range(n-l):
                ans+='0'
            ans+=strmult5
            print ans
if __name__ == '__main__':
    main()

Is it because of large number to string conversion? Please suggest a way to make it fast.

[daft_wullie]

Hi,

it is correct that your approach to concatenate strings is quite slow (and not "pythonic" at all). Look at some documentation about the join() function.

Furthermore you might consider to optimize your algo. Calculating the power of 5 is time-consuming, too. Think about binary representations of 0.5 (or 2) and how they can be "powered"

Cheers
Daft

[dursalakihoegalo]

Thanx. I read somewhere that concatenating strings with .join is now similar to adding. But I keep forgetting that spoj uses python2.5.
Thanx. I will do it and tell if problem still exists.

[daft_wullie]

I doubt that resolving the sting concat issue will result in sufficient speed-up to get acc - I tested this and still got TLE. Most probably you will have to do more than that.

[dursalakihoegalo]

Yes. I ran the code with both the methods in ideone and saw that the adding of strings is performing better. I need to look the method of power.

Thank You.

[gorlum0_sof]

Yes. I ran the code with both the methods in ideone and saw that the adding of strings is performing better. I need to look the method of power.

Thank You.

You can also create string of zeros via multiplication: '0'*n. Expectedly much faster than manual way.

[daft_wullie]

yes, 'xyz' * n is of course the fastest method to create a string of repeating elements.

More generally, beyond repeating identical strings, join still is much faster than '+'. I ran some small tests on Python 2.7:
[bbone=python,430]
import timeit
def stringjoin1(n):
mylist = [''] * n
for i in xrange(n):
mylist[i] = '0'
return ''.join(mylist)

def stringjoin2(n):
mylist = []
for i in xrange(n):
mylist.append('0')
return ''.join(mylist)

def stringadd(n):
mystr = ''
for i in xrange(n):
mystr += '0'
return mystr

def stringfunc(n):
return '0' * n

def main():
t = timeit.Timer("stringjoin1(500)", "from main import stringjoin1")
print 'stringjoin1(500)', t.timeit(number=10000)
t = timeit.Timer("stringjoin2(500)", "from main import stringjoin2")
print 'stringjoin2(500)', t.timeit(number=10000)
t = timeit.Timer("stringadd(500)", "from main import stringadd")
print 'stringadd(500) ', t.timeit(number=10000)
t = timeit.Timer("stringfunc(500) ", "from main import stringfunc")
print 'stringfunc(500) ', t.timeit(number=10000)

if name == 'main':
main()
[/bbone]
with this results (on my machine):

stringjoin1(500) 0.633952359867
stringjoin2(500) 1.21371403349
stringadd(500)   1.44271827844
stringfunc(500)  0.00755850254711

[gorlum0_sof]

More generally, beyond repeating identical strings, join still is much faster than '+'. I ran some small tests on Python 2.7

Generally not by much. On par at least for not-so-big n with +'0'. Check show submissions above (backed by ideone).

[daft_wullie]

yes , that's right. interesting difference between IDEONE and my local Python.

P.S. Sorry for offtopic content - the speed of string concatenation is not the key issue for problem FERT21_0...

[dursalakihoegalo]

I have been trying to think and did it on pen and paper. I understand 2**n can be done by 2<<(n-1). But cannot figure out how it helps in dividing 1 but it. May I get any hint? Or is there a problem in spoj that will help me understand the trick.

Thank You.

[daft_wullie]

instead of calculating 0.5**123 you may calculate 1.0/(2**123) and that is eqivalent to 1.0/(1<

And this number can be represented in float without loss of accuracy. With this, all that remains to do is outputting a float number with the correct number of decimal digits after the period... ('%.xxxf' is your friend )

[dursalakihoegalo]

Thanx. Never new "%.xxf" is such awesome. But, I am getting NZEC with this code and in ideone it is OK.

import sys
def main():
    s = sys.stdin
    t = s.readline()
    for i in s:
        n = int(i)
        if n==1: print '1'
        else:
            n-=1
            s="%."+str(n)+"f"
            print s%(1.0/(1<<n))
if __name__ == '__main__':
    main()

[numerix]

Thanx. Never new "%.xxf" is such awesome. But, I am getting NZEC with this code and in ideone it is OK.

You checked for n>67?

[dursalakihoegalo]

@numerix: yes sir. All of them give correct answer.

ideone.com/dyRBJ

[numerix]

IDEONE uses Python 2.7. With Python 2.5/2.6 you get the following:

>>> "%.100f" %(1.0/(1<<100))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: formatted float is too long (precision too large?)

[dursalakihoegalo]

@numerix: thank you sir.

[daft_wullie]

well, it is annoying to recognize that my simple code only got accepted because it happened to be run on a python 2.7 server.

What approach is promising to be fast enough for python 2.6?

I tried a code which uses the multiply by 5 approach, convert to a string and concat this to a the correct number of leading '0'. I stored the number of necessary leading zeros in a list in my source (source length limit is quite high) but ran into the TLE, too.

any hints? Am I supposed to write a binary to decimal converter suitable for 1000 (decimal) digits?