News for hackers. Stuff that matters.
Re:The Prolog Story by barrkel on Thursday May 20, 2010 @02:17PM (#1364780)
After you've coded a bunch of programming competition problems, yes, they really are trivial. There's only a handful of techniques, primarily around what kind of set you're going to permute or select from; getting the correct results are easy, but usually exponential in time. Apply some constraints at each recursion to prune the depth, and perhaps memoize them if the substructure is similar, and you very quickly narrow in on efficient solutions. Use some heuristics, and you can sacrifice optimality for more speed.

It's definitely not rocket science. 15 year old kids have been doing this for years in IOI etc.

Re:The Prolog Story by pdany on Thursday May 20, 2010 @05:37PM (#1365519)
I never participated in IOI, but at least in ACM contests I have never seen a problem where suboptimal heuristic search was allowed.
Re:The Prolog Story by barrkel on Thursday May 20, 2010 @06:10PM (#1365619)
Now we're mixing up two criteria. Contest problems are small enough that an optimal solution can be found in reasonable time; but since packing problems usually end up NP complete or NP hard, in the real world you'll end up using heuristics.