K. Up a Tree

2013 World Finals St. Petersburg HOSTED BY ITMO Problem K Up a Tree Time Limit: 6 seconds Anatoly Cheng McDougal is a typical student in many ways. Whenever possible he tries to cut and paste code instead of writing it from scratch. Unavoidably this appro...

Updated May 21, 2026

Track ICPC

Year 2013

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 6 seconds

Anatoly Cheng McDougal is a typical student in many ways. Whenever possible he tries to cut and paste code instead of writing it from scratch. Unavoidably this approach causes him problems. For example, when he first learned about preorder, inorder and postorder traversals of trees, and was given code for a preorder print of a tree (shown on the left below), he simply cut and pasted the code, then moved the print statement to the correct location and renamed the procedure. However, he forgot to rename the procedure calls inside the code, resulting in the defective inorder print and postorder print code shown below.

void prePrint(TNode t)             void inPrint(TNode t)               void postPrint(TNode t)
{                                  {                                   {
  output(t.value);                   if (t.left != null)                 if (t.left != null)
  if (t.left != null)                  prePrint(t.left);                   prePrint(t.left);
    prePrint(t.left);                output(t.value);                    if (t.right != null)
  if (t.right != null)               if (t.right != null)                  prePrint(t.right);
    prePrint(t.right);                 prePrint(t.right);                output(t.value);
}                                  }                                   }

At this point, Anatoly did not behave like a typical student. He actually tested his code! Unfortunately, when the results were not correct, he reverted back to typical student behavior. He panicked and started randomly changing calls in all three procedures, hoping to get things right. Needless to say, the situation became even worse now than when he started. Anatoly’s professor tested the code on a random tree of characters. When she looked at the output of his three print routines, she correctly guessed what had happened. However, instead of going directly to his code, she decided to try to reconstruct Anatoly’s code just by observing the output. In order to do this, she correctly made the following assumptions:

The output statement in each print routine is in the correct location (for example, between the two recursive calls in the inPrint routine).

Among the six recursive calls made by the three routines, exactly two calls are to prePrint, exactly two are to inPrint, and exactly two are to postPrint, though potentially in the wrong routines.

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible recon- structions of Anatoly’s code. In addition, for each such reconstruction, you are to find the alphabetically first tree (as described in the output section) giving the observed output.

Input

The input consists of a single test case. A test case consists of three strings on three separate lines: the observed output of Anatoly’s prePrint, inPrint and postPrint routines (in that order) on some test tree. Each of these strings consists of n uppercase letters (4 ≤ n ≤ 26), with no repeated letters in any string. The test case is guaranteed to have at least one solution.

                                                                 ICPC 2013
2013 World Finals
                                                           St. Petersburg
                                                            HOSTED BY   ITMO

Output

Display all possible reconstructions for the test case, ordered as described in the last paragraph below. The output for each reconstruction consists of two parts. The first part is a single line and describes the six calls in Anatoly’s routines: first the two (recursive) calls in Anatoly’s prePrint routine, followed by the calls in his inPrint routine, and finally the calls in his postPrint routine. The calls are described by the words Pre, In, and Post, separated by spaces. For example, if Anatoly’s routines were correct, the resulting output of the first part of the reconstruction would be Pre Pre In In Post Post. The second part consists of three lines and describes the first test tree that could have generated the ob- served outputs. The first line is the correct preorder print of the tree, and the second and third lines con- tain the correct inorder and postorder prints, respectively. The first tree is the one with the alphabetically first preorder print. If there are multiple such trees, the first of these is the one with the alphabetically first inorder print. Every reconstruction is a sequence of 6 tokens chosen from Pre, In, and Post. The ordering of reconstructions is lexicographic with respect to the following ordering of tokens: Pre < In < Post.

Sample Tests

Sample 1

Sample Input

 HFBIGEDCJA
 BIGEDCJFAH
 BIGEDCJFAH

Sample Output

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Sample 2

Sample Input

 BNLFAGHPEDOCMJIK
 NLBGAPHCODEIJMKF
 NLFAGHPEDOCMJIKB

Sample Output

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2013/K-up-a-tree/solution.texC++ implementationcompetitive_programming/icpc/2013/K-up-a-tree/solution.cppStatement textcompetitive_programming/icpc/2013/K-up-a-tree/statement.txtStatement PDFcompetitive_programming/icpc/2013/K-up-a-tree/statement.pdfMetadatacompetitive_programming/icpc/2013/K-up-a-tree/meta.jsonYear packetcompetitive_programming/icpc/2013/contest_problems.pdf

K. Up a Tree

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets