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

[Ian Kelly]

On Sun, Jun 1, 2008 at 7:25 AM, Shriphani <shriphanip at gmail.com> wrote:
> 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.