SPOJ, Problem Code: sumtrian, Reducing time taken to solve.

[Shriphani]

Hi,

I was trying to solve the sumtrian problem in the SPOJ problem set
( https://www.spoj.pl/problems/SUMTRIAN/ ) and this is the solution I
submitted: http://pastebin.ca/1035867

The result was, "Your solution from 2008-06-01 15:13:06 to problem
SUMTRIAN, written in Python,
has exceeded the allowed time limit."

I suspect that the first portion of my solution which looks at the
input, figures out the number of triangles and forms a list that
contains lists containing each row of the triangle, is wrong. I am not
too sure how to optimize it. I would appreciate help.

Thanks,
Shriphani Palakodety

[Henrique Dante de Almeida]

On Jun 1, 10:25*am, Shriphani <[e-mail]:

Hi,

I was trying to solve the sumtrian problem in the SPOJ problem set
(https://www.spoj.pl/problems/SUMTRIAN/) and this is the solution I
submitted:http://pastebin.ca/1035867

The result was, "Your solution from 2008-06-01 15:13:06 to problem
SUMTRIAN, written in Python,
has exceeded the allowed time limit."

I suspect that the first portion of my solution which looks at the
input, figures out the number of triangles and forms a list that
contains lists containing each row of the triangle, is wrong. I am not
too sure how to optimize it. I would appreciate help.

Thanks,
Shriphani Palakodety

First, you have to write a correct algorithm. Notice that your code
doesn't correctly calculates the given sample input. Later, think
about optimization.

[Ian Kelly]

On Sun, Jun 1, 2008 at 7:25 AM, Shriphani <sh********@gmail.comwrote:

I was trying to solve the sumtrian problem in the SPOJ problem set
( https://www.spoj.pl/problems/SUMTRIAN/ ) and this is the solution I
submitted: http://pastebin.ca/1035867

The result was, "Your solution from 2008-06-01 15:13:06 to problem
SUMTRIAN, written in Python,
has exceeded the allowed time limit."

I suspect that the first portion of my solution which looks at the
input, figures out the number of triangles and forms a list that
contains lists containing each row of the triangle, is wrong. I am not
too sure how to optimize it. I would appreciate help.

Since you asked, I went and tried the problem myself and managed to
get a solution accepted with a bit of work. Here are my suggestions
with regard to your code:

* You absolutely need to use psyco for this problem. The accepted
solutions have memory usage of 36M+, which on SPOJ is a sure sign that
psyco was used, and they're already just a hair under the time limit.

* Instead of guessing "it's probably the input step", why don't you
profile your code so that you *know* where the bottlenecks are?

* Use xrange instead of range in for loops, and certainly don't use
while loops for iteration.

* max is quite slow for comparing only two things. It's faster to
compare the two things yourself. Since this line may be executed
millions of times, the difference could be quite significant.