Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41089

Re: Regular expression problem

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Regular expression problem mukesh tiwari <mukeshtiwari.iiitm@gmail.com> - 2013-03-10 10:42 -0700
  Re: Regular expression problem Chris Angelico <rosuav@gmail.com> - 2013-03-11 04:59 +1100
    Re: Regular expression problem mukesh tiwari <mukeshtiwari.iiitm@gmail.com> - 2013-03-10 11:05 -0700
    Re: Regular expression problem mukesh tiwari <mukeshtiwari.iiitm@gmail.com> - 2013-03-10 11:05 -0700
  Re: Regular expression problem Chris Angelico <rosuav@gmail.com> - 2013-03-11 05:08 +1100
    Re: Regular expression problem mukesh tiwari <mukeshtiwari.iiitm@gmail.com> - 2013-03-10 11:48 -0700
      Re: Regular expression problem Chris Angelico <rosuav@gmail.com> - 2013-03-11 05:57 +1100
    Re: Regular expression problem mukesh tiwari <mukeshtiwari.iiitm@gmail.com> - 2013-03-10 11:48 -0700
  Re: Regular expression problem Terry Reedy <tjreedy@udel.edu> - 2013-03-10 22:06 -0400
    Re: Regular expression problem jmfauth <wxjmfauth@gmail.com> - 2013-03-11 02:28 -0700
      Re: Regular expression problem Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-03-11 10:19 +0000
      Re: Regular expression problem rusi <rustompmody@gmail.com> - 2013-03-11 06:18 -0700
      On topic, please [Was:Re: Regular expression problem] Ned Deily <nad@acm.org> - 2013-03-11 11:13 -0700
  Re: Regular expression problem Serhiy Storchaka <storchaka@gmail.com> - 2013-03-11 20:30 +0200
  Re: Regular expression problem Terry Reedy <tjreedy@udel.edu> - 2013-03-11 16:23 -0400

csiph-web