{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eAnatoly Cheng McDougal is a typical student in many ways.\n Whenever possible he tries to cut and paste code instead of\n writing it from scratch. Unavoidably this approach causes him\n problems. For example, when he first learned about preorder,\n inorder and postorder traversals of trees, and was given code\n for a preorder print of a tree (shown on the left below), he\n simply cut and pasted the code, then moved the print statement\n to the correct location and renamed the procedure. However, he\n forgot to rename the procedure calls inside the code, resulting\n in the defective inorder print and postorder print code shown\n below.\u003c/p\u003e\n\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; border-bottom-color:black; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid prePrint(TNode t)\n{ \n output(t.value);\n if (t.left !\u003d null)\n prePrint(t.left);\n if (t.right !\u003d null) \n prePrint(t.right);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid inPrint(TNode t)\n{\n if (t.left !\u003d null)\n prePrint(t.left);\n output(t.value);\n if (t.right !\u003d null)\n prePrint(t.right);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid postPrint(TNode t)\n{\n if (t.left !\u003d null)\n prePrint(t.left);\n if (t.right !\u003d null)\n prePrint(t.right);\n output(t.value);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n\n \u003cp\u003eAt this point, Anatoly did not behave like a typical\n student. He actually tested his code! Unfortunately, when the\n results were not correct, he reverted back to typical student\n behavior. He panicked and started randomly changing calls in\n all three procedures, hoping to get things right. Needless to\n say, the situation became even worse now than when he\n started.\u003c/p\u003e\n\n \u003cp\u003eAnatoly’s professor tested the code on a random tree of\n characters. When she looked at the output of his three print\n routines, she correctly guessed what had happened. However,\n instead of going directly to his code, she decided to try to\n reconstruct Anatoly’s code just by observing the output. In\n order to do this, she correctly made the following\n assumptions:\u003c/p\u003e\n\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe output statement in each print routine is in the\n correct location (for example, between the two recursive\n calls in the \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e\n routine).\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eAmong the six recursive calls made by the three\n routines, exactly two calls are to \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e, exactly two are to \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e, and exactly two are to \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e, though potentially in the wrong\n routines.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n\n \u003cp\u003eSoon the professor realized that reconstructing Anatoly’s\n code and the test tree from his output was not a simple task\n and that the result might be ambiguous. You will have to help\n her find all possible reconstructions of Anatoly’s code. In\n addition, for each such reconstruction, you are to find the\n alphabetically first tree (as described in the output section)\n giving the observed output.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case\n consists of three strings on three separate lines: the observed\n output of Anatoly’s \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e,\n \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e and \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e routines (in that order) on some test\n tree. Each of these strings consists of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e uppercase letters (\u003cspan class\u003d\"tex2jax_process\"\u003e$4 \\le n \\le 26$\u003c/span\u003e), with no repeated\n letters in any string. The test case is guaranteed to have at\n least one solution.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay all possible reconstructions for the test case,\n ordered as described in the last paragraph below. The output\n for each reconstruction consists of two parts. The first part\n is a single line and describes the six calls in Anatoly’s\n routines: first the two (recursive) calls in Anatoly’s\n \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e routine, followed by the\n calls in his \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e routine, and\n finally the calls in his \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e\n routine. The calls are described by the words \u003ctt class\u003d\"ttfamily\"\u003ePre\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eIn\u003c/tt\u003e, and\n \u003ctt class\u003d\"ttfamily\"\u003ePost\u003c/tt\u003e, separated by spaces. For\n example, if Anatoly’s routines were correct, the resulting\n output of the first part of the reconstruction would be\n \u003ctt class\u003d\"ttfamily\"\u003ePre Pre In In Post Post\u003c/tt\u003e.\u003c/p\u003e\n\n \u003cp\u003eThe second part consists of three lines and describes the\n first test tree that could have generated the observed outputs.\n The first line is the \u003cem\u003ecorrect\u003c/em\u003e preorder print of the\n tree, and the second and third lines contain the correct\n inorder and postorder prints, respectively. The first tree is\n the one with the alphabetically first preorder print. If there\n are multiple such trees, the first of these is the one with the\n alphabetically first inorder print.\u003c/p\u003e\n\n \u003cp\u003eEvery reconstruction is a sequence of 6 tokens chosen from\n \u003ctt class\u003d\"ttfamily\"\u003ePre\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eIn\u003c/tt\u003e,\n and \u003ctt class\u003d\"ttfamily\"\u003ePost\u003c/tt\u003e. The ordering of\n reconstructions is lexicographic with respect to the following\n ordering of tokens: \u003ctt class\u003d\"ttfamily\"\u003ePre \u0026lt; In \u0026lt;\n Post\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eHFBIGEDCJA\nBIGEDCJFAH\nBIGEDCJFAH\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ePre Post In Post In Pre\nHFBJCDEGIA\nBIGEDCJFAH\nIGEDCJBAFH\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eBNLFAGHPEDOCMJIK\nNLBGAPHCODEIJMKF\nNLFAGHPEDOCMJIKB\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eIn Pre In Post Post Pre\nBLNFKMEHAGPCODIJ\nNLBAGHPEODCMIJKF\nNLGAPHDOCEJIMKFB\n\nPost Pre In In Post Pre\nBLNFKICPGAHEODMJ\nNLBGAPHCODEIJMKF\nNLAGHPDOECJMIKFB\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}