ICPC 2013 - K. Up a Tree
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2013/K-up-a-tree. Edit
competitive_programming/icpc/2013/K-up-a-tree/solution.tex to update the written solution and
competitive_programming/icpc/2013/K-up-a-tree/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
ICPC 2013
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 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:
1. The output statement in each print routine is in the correct location (for example, between the two
recursive calls in the inPrint routine).
2. 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 Input 1 Sample Output 1
HFBIGEDCJA Pre Post In Post In Pre
BIGEDCJFAH HFBJCDEGIA
BIGEDCJFAH BIGEDCJFAH
IGEDCJBAFH
Sample Input 2 Sample Output 2
BNLFAGHPEDOCMJIK In Pre In Post Post Pre
NLBGAPHCODEIJMKF BLNFKMEHAGPCODIJ
NLFAGHPEDOCMJIKB NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB
Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
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.
Code
Exact copied C++ implementation from solution.cpp.
#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;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2013\\K. Up a Tree Time Limit: 6 seconds}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#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;
}