Regular expression problem
Terry Reedy
tjreedy at udel.edu
Mon Mar 11 21:23:21 CET 2013
On 3/11/2013 2:30 PM, Serhiy Storchaka wrote:
> On 11.03.13 04:06, Terry Reedy wrote:
>> On 3/10/2013 1:42 PM, mukesh tiwari wrote:
>>> Hello all
>>> I am trying to solve this problem[1]
>>> [1] http://www.spoj.com/problems/MAIN12C/
>>
>> As I remember, and as it still appears, this site severely penalizes
>> Python solvers by using the same time limit for all languages. Thus, a
>> 'slow' python program may work correctly but the site will not let you
>> know.
>
> I'm sure the time limits are enough to solve most (if not all) of
> problems. Actually all submitted solutions on Python for this problem
> run from 0.47 to 0.61 seconds (http://www.spoj.com/ranks/MAIN12C/).
You do not see the solutions that timed out. I suppose you are pointing
to the fact that for this problem there are solutions close to but under
the time limit. However, algorithm running times are not evenly
distributed. Suppose, for instance) there is a correct O(n**2) solution
and a correct O(n) solution and that the ones listed are the O(n)
solutions. Then the Python O(n**2) solutions could easily take 10x
longer to run and time out, while equivalent C solutions do not.
Mukesh is not the first to post here a reasonable looking solution for
that site that he could not judge because the test quite and refused to
answer. I point out again that he was 'happy' to have a faster but
incorrect program, even though it might have been a regression from his
original.
--
Terry Jan Reedy
More information about the Python-list
mailing list