TLE in FAST 2!

shailu_sof 2012-06-26 10:01:36 UTC #1

removed

plz somebody help....nd wht is the reason of tle....plz help

daft_wullie 2012-06-26 10:51:47 UTC #2

Think about your algo. It is not necessary to calculate all the powers and sum them. Closed-form expression exists for power series'.
Daft

francky 2012-06-26 11:41:40 UTC #3

You should use memoization:
If we are asking
5
17
17
17
17
17

You're doing 5× the job.

Or better, you can use a list construction
[a0, a1, a2, a3, ... an]
How to construct fast the next term ?
Build all needed terms, and then answer questions.

daft_wullie 2012-06-26 13:35:31 UTC #4

So it is common to "ask the same question more than once" (repeat the same input data) in SPOJ test cases? Up to know I neglected memoisation if it was possible to handle the the problem non-recursive.

shailu_sof 2012-06-27 07:27:23 UTC #5

pre-calculating all the values also gives TLE...nd with memoization also tle....
here is my code for memoization..plz help

removed

gorlum0_sof 2012-06-27 07:50:27 UTC #6

It's not about what is common and not. Just look at the problem constraints.

francky 2012-06-27 11:01:18 UTC #7

OK, but ...

Doing exponnetion for each term is too costly.
How to compute a_(n+1) directly from a_n ?

daft_wullie 2012-06-27 11:15:05 UTC #8

you're doing the modulo twice where it is necessary only once
dont do .append() 501 times, use [0]*501
use import sys ... sys.stdout.write(string)

this should help, although I did not measure the effect of every single action. My code got ACC without memoization.

shailu_sof 2012-06-27 12:57:20 UTC #9

As u suggested i made out the changes but still it gives TLE

removed

daft_wullie 2012-06-27 13:39:43 UTC #10

You only used the first part of this hint. 'print' is costly, too. It can be replaced by sys.stdout.write() / .writelines() after converting your result into string.

francky 2012-06-27 13:52:16 UTC #11

Don't do that !!!!!!

k=int(((2**(n+1))-1))

Don't use **, neither pow, just a poor * and -

shailu_sof 2012-06-27 13:56:25 UTC #12

i changed it but still tle....plz help this is troubling me now....

removed

daft_wullie 2012-06-27 14:00:44 UTC #13

Generally it is a very good idea to avoid ** and pow. But in this special case I suppose that python optimizes the powers of 2. I didn't find a significant difference between 2**n and 1<

2**500  0.457705020905
1<<500  0.457556009293

shailu_sof 2012-06-27 14:01:06 UTC #14

@Francky
i changed dat to

 removed

but still tle.....

shailu_sof 2012-06-27 14:24:54 UTC #15

thanx daft_wullie and francky...in this also changing code to python 2.5 gives ACC but plz also do tell me why python 3.1 is slow....

francky 2012-06-27 15:40:36 UTC #16

Python 3.1 is slower on spoj because:
1) start timing for the interpreter is 0.11s vs 0.02s for python2.7, or 0.03s for python2.5,
2) python3.1 as slow de/en/coding to unicode reading and writing, even if the input is not unicode.
3) more, 2) has a bigger memory cost...
4) other few things are faster or slower, it makes few diffrences.

=====
For the future :
Python 3.2 will still have slow unicode de/en/coding IO, but
Python3.3 will be quite as fast as Python2.7, the de/en/coding will be transparent.
Info here.

I hope Python3.3 will be quickly adopted as fast as possible.

daft_wullie 2012-06-27 16:10:53 UTC #17

Would it be possible to have a posting like this as a "sticky" post? To help persons new to python optimization within SPOJ? Perhaps francky wouldn't have to answer same questions frequently