4 ms·
That would be slow if you didn't know the slice size (the bonus part of the question), but no, you're not missing anything for the basic solution. That said, it
by lunaru 15y ago
That would be slow if you didn't know the slice size (the bonus part of the question), but no, you're not missing anything for the basic solution. That said, it would be O(n^2) since you're comparing every slice to every other slice.
- bermanoid 15y agoThe general problem is fairly easily isomorphic to traveling salesman, so if you can get even O(n^2) you're already making simplifying assumptions that mean you can't solve the general case. Further, with n=20, I wouldn't usually worry too much about asymptotic performance unless you're in exponential territory.
- bermanoid 15y agoActually, on second thought, this isn't quite so easily isomorphic to traveling salesman (any particular "order shredded strips" problem is easily equivalent to a traveling salesman problem, but I'm not positive that an arbitrary traveling salesman problem can be re-cast as an "order shredded strips" problem in a consistent manner, so I shouldn't make that claim). So I retract my statement, it's quite possible that someone could effectively solve this problem for reasonable inputs without quadratic runtime (though I'm not positive exactly how you would do it, and the efficacy of your method would likely depend on your assumptions about the inputs).