Topic for a turing contest!

[Token]

Hey everyone, i would like to start a contest but i was talking to tony and he said i would get more submissions if i had a theme, what would you people like to see for this contest theme, please give me some ideas

[thegoose]

Approximation algorithms for NP-complete problems (sort of like the IPSC)

[Token]

what are those? could somone please elaborate?

[thegoose]

Basically, NP complete problems are problems such that no efficient (polynomial time) solving algorithms have been found.
The approximation algorithms for such problems are usually very intuitive and nice (usually a simple strategy that performs much better than the back-tracking algorithms). I think this would be a good idea because this type of problems requires the least programming background and the most intuition.
An example of such a problem is found on the following link:
http://olympiads.win.tue.nl/ioi/ioi2003/contest/day1/reverse/reverse.pdf
solution:
http://olympiads.win.tue.nl/ioi/ioi2003/contest/day1/reverse/data-reverse.pdf
This is a hard problem if you don't see the idea but if you see it, the solution becomes obvious. As a sidenote, somebody in my class who never took computer science managed to get 100/100 on it while I only got 49/100 when I first did it.

[Aidin Kashigar]

lol. i think you'd get way more submission by dropping the turing thingy and opening it up to all languages.

As far as the theme goes, the typical Farmer John and his wonderful, yet computer-deprived, cows (in USACO contests) seems to work well with lots of people.

[Token]

the thing with that is that it will be hard to compare the programs against each other, because its easier to do certian things in certian programming languages whereas others it is harder

[Tony]

Token wrote:

its easier to do certian things in certian programming languages whereas others it is harder

well that's part of programming. A skillful programmer will know which language to better approach those certain parts with. Most applications are made in more than one language. Personally I combine two for my work projects.

[thegoose]

Token wrote:

the thing with that is that it will be hard to compare the programs against each other, because its easier to do certian things in certian programming languages whereas others it is harder

That's why I think it would be a good idea to make the problems output-only. i.e. you give out the input files, you ask for the output files rather than the program.
Also, there is already a student-run contest (DWITE II, very original name), we currently have me, Aidin and Simon making the problems (and 2 other consultants) with the next contest being somewhere near the end of March. If you guys would like to contribute, please contact one of us.