Mr Thomspon's Problem

Problem I - Mr Thomspon's Problem

Ok, so think of the numbers as nodes on a graph. Put an edge between two numbers if they sum to one of the possible sum numbers. Your answer is then the maximum matching of the graph.

Not suprisingly, and (in the interests of creativity in the problems and their solutions),= unfortunately, there already exists a standard algorithm for finding the max. matching. Jack Edmonds detailed this algorithm in a paper in 1965 called 'Paths, Trees and Flowers' which does exactly what is required in the problem. Rather than writing about it again here, I'll redirect you to a lecture by one of his colleagues which describes it better than I could.

Personally, having this in seems too hard for an ACM regional, as noone is expected to know of this algorithm, and the only other way to solve it is an optimised brute force, yet these would no doubt still be too slow if custom test-cases could be prepared [a la TopCoder challenge phase].

Instead, it would have been excellent if all sum numbers were odd. Why? Well, if two numbers sum to an odd number, one must be odd and the other even. This means every edge in your graph is between an odd number and an even number, making it a bipartite graph. The maximum-matching algorithm for bipartite graphs is simpler and more known, so probably more appropriate for this level of contest.

Apologies that I don't have code for this one, as it's too much of a standard algorithm to re-write. If you're interested in an implementation, funnily enough it is inbuilt into the popular 'boost' C++ libraries [which you can't use in the ACM :p] - for details, see this which further illustrates how standard this algorithm is.

And that's all 9 problems, hope you enjoyed it!