Regular expression problem

[Terry Reedy]

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