CUBES - Exceeded time limit with Python

islandcoder_sof 2010-04-26 21:59:24 UTC #1

I have a solution that I'm quite sure is correct, and it runs in ~.5 seconds on my workstation. When I submit this soluition, I get a result stating "time limit exceeded."

The problem https://www.spoj.pl/problems/CUBES/ states a time limit of 1 second.

So, it seems my system (a basic Dell laptop) is faster than the judge system. How can I know what speed is correct, so that I can get it to pass on my next attempt?

Thanks!!

islandcoder_sof 2010-04-29 05:16:28 UTC #2

I submitted the result as TEXT and got WA. Not a satisfying as sending in the code, but it passed, so all good.

Might be nice to have different times for different languages. Python isn't fast, but who cares. Not all programs have to shave fractions of a second.

numerix 2010-04-29 11:54:41 UTC #3

That was discussed more than once, but it seems there is no satisfying solution.

Though Python doesn't belong to the "fast languages", you can find some problemsets, where Python solutions are among the fastest solutions submitted.
And: There are hundreds of SPOJ-problemsets that can be solved with Python - for me that's enough ...

islandcoder_sof 2010-04-29 22:30:31 UTC #4

Would be for me to, Numerix. The trick is how to find these elusive problemsets. Still figuring my way around the site.

mwdaly 2010-05-04 03:30:10 UTC #5

As far as I can see at this point, you can get a good feel by going to the Best Solutions for a Problem and clicking on the Python link up there to see how many people solved the problem. If there are a half-dozen solutions or more, then IME it is a good bet that a sensible algorithm that relies on built-ins will give you WA. On the other hand, if Numerix is the only person to solve the problem, then maybe not so much. (I got burned by this last week with TUTMRBL, which Numerix says in the problem comments is "easy" to get an AC in Python but I didn't find this to be the case and Numerix is the only person who has managed it so far.) But if you do your best optimization and still get TLE then I figure it's not a huge deal, since by that time you've got an algorithm that just has to be translated into C.

Speaking of CUBES specifically, I am one of the people who got AC in Python and my twelve-line script is pretty naive. The one mild spoiler that I'd throw out there is that checking for set membership is extremely fast, and a script that depends on that gives you the performance of C combined with the readability and rapid development that is awesome about Python. But, yeah, when I tried doing SQRT2 I also learned that my processor can run circles around the judge's.