← All solutions

Shortest judge solution: 2165 bytes. Shortest team solution (during contest): 4180 bytes.

This problem is conceptually easy but surprisingly tedious to code if you are not careful. There are only (6 choose 2, 2, 2) = 90 possible ways to put the pre/in/post calls, so we simply go through them all and check each one.

Checking if an assignment of calls is possible and finding the smallest tree can be done using dynamic programming. A state consists of three substrings of the inputs of equal length, each tagged as being the output of prePrint, inPrint, or postPrint (so a naive estimate for the number of states would be 3³ n⁴ though the actual number is much smaller). To find the smallest tree that could yield these three substrings as observed outputs, we guess the size of the left subtree. Such a guess is either contradictory, or splits each of the strings into two substrings representing the two subtrees. For instance, if the string “ABCDEFGH” was printed by prePrint and we guess that the left subtree has 3 nodes, then the root node is “A”, the observed output for the left subtree is “BCD” (and it is the observed output of the routine that we are currently trying as the first recursive call in the prePrint routine) and the observed output for the right subtree is “EFGH” (and it is the observed output of the routine that we are currently trying as the second recursive call in the prePrint routine). If in addition we had the string “BCDFAEGH” as the output of the inPrint, we would have a contradiction, since in that case if the left subtree had size 3 the root node would have to be “F”.