3 ms·
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 o
by barrkel 17y ago
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.
- pdany 17y agoI never participated in IOI, but at least in ACM contests I have never seen a problem where suboptimal heuristic search was allowed.
- barrkel 17y agoNow 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.