By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,660 Members | 1,105 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,660 IT Pros & Developers. It's quick & easy.

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

P: n/a
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
Jun 1 '08 #1
Share this Question
Share on Google+
2 Replies


P: n/a
On Jun 1, 10:25*am, Shriphani <shripha...@gmail.comwrote:
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.
Jun 1 '08 #2

P: n/a
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.
Jun 1 '08 #3

This discussion thread is closed

Replies have been disabled for this discussion.