ICPC 2017 - I. Secret Chamber at Mount Rushmore
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/2017/I-secret-chamber-at-mount-rushmore. Edit
competitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/solution.tex to update the written solution and
competitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/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.
Rapid City
event
sponsor
ICPC 2017
Problem I
Secret Chamber at Mount Rushmore
Time limit: 1 second
By now you have probably heard that there is a spectacular stone sculp-
ture featuring four famous U.S. presidents at Mount Rushmore. How-
ever, very few people know that this monument contains a secret cham-
ber. This sounds like something out of a plot of a Hollywood movie, but
the chamber really exists. It can be found behind the head of Abraham
Lincoln and was designed to serve as a Hall of Records to store impor-
tant historical U.S. documents and artifacts. Historians claim that the
construction of the hall was halted in 1939 and the uncompleted cham-
ber was left untouched until the late 1990s, but this is not the whole
truth.
In 1982, the famous archaeologist S. Dakota Jones secretly visited the
monument and found that the chamber actually was completed, but it
was kept confidential. This seemed suspicious and after some poking
around, she found a hidden vault and some documents inside. Unfortu-
nately, these documents did not make any sense and were all gibberish.
She suspected that they had been written in a code, but she could not
decipher them despite all her efforts.
Earlier this week when she was in the area to follow the ACM-ICPC World Finals, Dr. Jones finally dis-
covered the key to deciphering the documents, in Connolly Hall of SDSM&T. She found a document that
contains a list of translations of letters. Some letters may have more than one translation, and others may
have no translation. By repeatedly applying some of these translations to individual letters in the gibberish
documents, she might be able to decipher them to yield historical U.S. documents such as the Declaration
of Independence and the Constitution. She needs your help.
You are given the possible translations of letters and a list of pairs of original and deciphered words. Your
task is to verify whether the words in each pair match. Two words match if they have the same length and
if each letter of the first word can be turned into the corresponding letter of the second word by using the
available translations zero or more times.
Input
The first line of input contains two integers m (1 ≤ m ≤ 500) and n (1 ≤ n ≤ 50), where m is the number
of translations of letters and n is the number of word pairs. Each of the next m lines contains two distinct
space-separated letters a and b, indicating that the letter a can be translated to the letter b. Each ordered
pair of letters (a, b) appears at most once. Following this are n lines, each containing a word pair to check.
Translations and words use only lowercase letters ‘a’–‘z’, and each word contains at least 1 and at most 50
letters.
Rapid City
event
sponsor
ICPC 2017
Output
For each pair of words, display yes if the two words match, and no otherwise.
Sample Input 1 Sample Output 1
9 5 yes
c t no
i r no
k p yes
o c yes
r o
t e
t f
u h
w p
we we
can the
work people
it of
out the
Sample Input 2 Sample Output 2
3 3 yes
a c no
b a yes
a b
aaa abc
abc aaa
acm bcm
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 2017\\I. Secret Chamber at Mount Rushmore}
\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;
}