Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

10202 – Pairsumonious Numbers

Finished the last problem in chapter five. This one was the first “Level 4” problem in the book, I believe, though it ends up being a backtracking search, with some extra overhead to shape the problem appropriately (which is to say if you sort the sums). Having a language-provided vector/sort/binary_search/set makes this sort of stuff pretty cookie-cutter, but it would take a while to write all of this from scratch and keep it fast.

That said, I’m not sure I need a solution that needs all this cleverness. While it does finish in 0.00 seconds (judge clock), the size of the problem is well-bounded and n stays very small: at most we’re looking at n=9, which means we’re looking at 36 sums. There is no algorithmic effect from the value of the numbers, as it’s all produced using the inputs, rather than just using the inputs for verification (I imagine using this approach would pretty quickly run into time limits on the judge).

With backtracking, the rather small size of the problem means the specific implementation details (logarithmic set membership, “n lg n” sorting (yes, I know, this is introsort, and probably does a smarter sort for the size of the problem anyway), etc.) probably bear little real-world impact.

Still, I’m glad somebody else implements all that crap in the STL containers/algorithms, so I don’t have to. My solution is functional, if inelegant.