May 2007
1 / 6
May 2007
Dec 2010
cycy
May '07

Hello,

I have implemented an algorithm, with Python, for resolving DISUBSTR problem, which is quite efficient.
For example for the string 'A'*1000 (the maximum size) it takes 0.85s on my computer.
But It still gets an exceed runtime limit (whichn is 1s).
So I really do think that this problem is impossible with Python!

Is it not possible to modulate the time limit with the language?

Don't worry, I still appreciate SPOJ site because it is the only one where it is possible to write program in the best language ... python smile

Regards

  • created

    May '07

  • last reply

    Dec '10
  • 5

    replies

  • 244

    views

  • 4

    users

  • 1

    link

noix
May '07

Maybe you've got a faster PC than PIII 700MHz? stuck_out_tongue

There have been many discussions about it, but I believe it's impossible to do this in a fair way.
In SPOJ, all languages are equal smile

TripleM_sof
May '07

I wouldn't say its impossible.
I'm sure its quite easy to increase the time limit to 5 seconds while still making sure solutions with an algorithm that is too slow fail.

I mean, what are the chances that there'll be a difference between an O(n) and O(n log n) algorithm at 1 second, but not at 5 seconds with a big input size?

Unless the problem is entirely designed to be solved by terrible optimizations rather than the right algorithm without optimizations. Then its a bad problem.

noix
May '07

I know it can be done somehow, but I don't think it would be fair.
How can you tell "how fast is some language"? Is Java faster than C#? C or Pascal? C++ or Ocaml or Perl? ...By what factors?
Languages (interpreters/compilers) have their strengths and weaknesses!

Instead, problemsetters are encouraged to provide big input/output data.
At least in theory, with data big enough, it should be possible to specify a time limit that is ok for all sensible solutions with expected asympthotical complexity.

cycy
May '07

In this case you should restrict language for some specific problems.
For example, you should say DISTRUB is only possible for JAVA,C,PASCAL ... (within the time limit).
This would people avoid to spend too much time on a problem.
Because it is quite frustrating to always get a TLE even if you have find the best algorithm.

3 years later

Suggested Topics

Want to read more? Browse other topics in Python or view latest topics.