Sunday, May 4, 2008

Programming competitions

I've just returned from Vinnica, where complex olympiad in mathematics, physics and informatics was held. I was working in mathematical jury, but it was also interesting to observe the «informatical part» of olympiad. There was two competitions: individual and command one.

What I dislike about those competitions (but as far as I understood, this is common, at least for Ukraine):

  1. There's a strong limitation on language: it's either Pascal (Borland or Free Pascal) or C/C++ (Borland C or GNU C++). I don't think that many pupils know other languages, but on the other hand this discourages pupils to learn other languages. Otherwise pupils would certainly get interested in languages where you don't need to manage dynamically allocated memory or implement bignums by hand.
  2. There's a limitation on execution time of your solution. Yes, execution time of your program compiled with some (unknown) compiler with some (unknown) flags and run on some (unknown) hardware.
    But ok, let's suppose that participant can roughly predict his execution time. How much time does he get? When one pupil asked jury, he got answer «twice the time of the author's solution». Unknown! And no, participants cannot even test their work until competition ends (to find out whether they satisfy the time limitations).

The best form of programming competitions I've ever seen is the one used in Project Euler.

It would be also interesting to hold the «programming tournament» in the form similar to physics tournament. What can be discussed is mathematical proof of correctness, O-big asymptotics, optimizations etc.


Aldanur said...

At least they won't get frustrated at the ACM ICPC finals where nobody knows the time limits either.

Roman Cheplyaka said...

Yep, that was the main argument of jury: "this rule is used in national olympiad/ICPC/other_trendy_contest".
Why are they so scared to do better?
I didn't take part in any of them, so maybe I'm wrong, but then they could find more convincing arguments.

caezar said...


Dan Mysak said...

Unfortunatelly, the form used in the Project Euler suffers from shortcomings too. On the one hand, it’s unable to check the correctness of competitor’s source code (e.g. for tricky particular cases) — that’s what a mathematician should be worried about. And on the other hand it approves solutions for which it takes hours to compute a simple thing — that’s not practical.

I think they should limit the time so that a competitor is sure his solution will be approved. For example, right linear time solution will be surely approved if the time limit is 1 second and the test cases’ values are below 10 000.

Roman Cheplyaka said...

Ok, I agree on "tricky particular cases", although you should understand that no test suite can verify the correctness of competitor’s source code, so from mathematician's point of view these two forms are equally bad :)

Concerning time limits: PE's problems usually deal with large data sets, so if your solution is suboptimal, it can take months or even years to finish.

Finally, there is no connection between asymptotics, values below 10 000 and time (in seconds), although your statement may be practically true.
PE's problem (with values about 10^8) test asymptotics much better.