EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2017
ICPC 2017

I. Secret Chamber at Mount Rushmore

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 tha...

Updated May 21, 2026
Track ICPC
Year 2017
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 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
sponsor
          ICPC 2017

Output

For each pair of words, display yes if the two words match, and no otherwise.

Sample Tests

Sample 1
Sample Input 
 9 5
 c t
 i r
 k p
 o c
 r o
 t e
 t f
 u h
 w p
 we we
 can the
 work people
 it of
 out the
Sample Output 
yes
no
no
yes
yes
Sample 2
Sample Input 
 3 3
 a c
 b a
 a b
 aaa abc
 abc aaa
 acm bcm
Sample Output 
yes
no
yes
Editorial

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

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. 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.

Implementation

Code

C++ solution used for this page.

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;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/solution.texC++ implementationcompetitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/solution.cppStatement textcompetitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/statement.txtStatement PDFcompetitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/statement.pdfMetadatacompetitive_programming/icpc/2017/I-secret-chamber-at-mount-rushmore/meta.jsonYear packetcompetitive_programming/icpc/2017/contest_problems.pdf