473,289 Members | 1,842 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,289 software developers and data experts.

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

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
2 2840
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Peter Salzman | last post by:
Hi all, Newish PHP programmer here. I wrote a form select class to help reduce code clutter, but I don't think the effort was worth it. I was hoping to post my attempt and get some ideas from...
6
by: qwweeeit | last post by:
Hi all, when I was young I programmed in an interpreted language that allowed to modify itself. Also Python can (writing and running a module, in-line): fNew =open("newModule.py",'w') lNew=...
16
by: gorda | last post by:
Hello, I am playing around with operator overloading and inheritence, specifically overloading the + operator in the base class and its derived class. The structure is simple: the base class...
143
by: suri | last post by:
Hello I downloaded glibc and tried looking for the code that implements the sine function i couldnt find the file. i went to the math directory and found math.h.. i guess that needs to be...
1
by: ErnieJ | last post by:
I a have a .net application which displays the results of a database query on a form in graphical format (i.e. charts and maps). This application is launched from another legacy Windows...
26
by: vlsidesign | last post by:
I am a newbie and going through "The C programming language" by Kernighan & Richie on my own time (I'm not a programmer but I want to learn because it can save me time in my normal job, and it is...
13
by: Hendrik van Rooyen | last post by:
Hi, I would like to do the following as one atomic operation: 1) Append an item to a list 2) Set a Boolean indicator It would be almost like getting and holding the GIL, to prevent a...
39
by: Gilles Ganault | last post by:
Hello, I'm no LAMP expert, and a friend of mine is running a site which is a bit overloaded. Before upgrading, he'd like to make sure there's no easy way to improve efficiency. A couple of...
2
by: Shriphani | last post by:
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...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.