Automatic Marking

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 less thinking and code.

Also, as the tree validation is given in the problem statement, the only new 'algorithm' that must be devised to solve this is how to parse the tree itself - as with many parsers, a good approach is similar to state-based, where the input is read as a stream (character-by-character). In this case, the 'interesting' characters are the brackets, between each pair you can parse a node and add it to a queue. Once the stream is finished, you work through the queue, linking up parent nodes with their required number of children. [Note that what they call 'level-order traversal' isn't really the nicest way of representing trees, pre- or post-order is much easier to parse, yet I guess it was used to make this harder]

Another gotcha with this question was how the children's values could be less-than-or-equal-to their upper bound, which makes things a bit more fiddly again.

Implementation of the idea described above can be found here.