Thoughts of a Psych/Code Monkey/Guitarist

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 w...

Problem E - A Fitting Advertisement It wouldn't be an SPP ACM Regional without its fair share of bugs, and this problem provided them for us. Given a histogram (i.e. heights across X value), find whether rectangles fit inside it. Sounds simple, with small catches - the heights can be zero, though that changes not much, and it doesn't matter which orientation you have for the rectangle, though again, you can just treat it as two different rectangles, and OR the results together, not too bad. Ok, so as submissions come in, people whose code looks right are failing. A bit of testing by the judges leads to the discovery that some of the rectangles you are placing have their width (or height) zero, which is explicitly disallowed in the problem specification. What's more, it's hard to know when a zero-sized rectangle fits within the histogram - the most 'logical' to me would be that it always fits, as it has zero area, yet the official judgement was different. Here...

Question H - Automatic Marking I usually like tree problems, they often have ncie recursive solutions using little code - a good example is Paths from the regional in 2005. This still was good in that sense, however the extra parsing/validation was a bit of a paint. Because of the fiddly-ness of the input, this again is one where it's more profitable to spend much time planning, rather than coding. In this case, I found it simplest to write my own tree structure, then separate it into sections which: Parse the input into a tree, returning null for an invalid tree Find where the single '?' is in the tree - returning a pointer, so you can.... Replace the '?' with each letter, and validate the tree using the rules they give. The use of a pointer here makes it easy to change the '?', and while the re-validation might be a bit slow compared to figuring out the valid range in one pass of the tree, it seems like it should still be fast enough, and results in les...