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

S

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
 
H

Henrique Dante de Almeida

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.
 
I

Ian Kelly

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top