ICPC 2017 - K. Tarot Sham Boast
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/K-tarot-sham-boast. Edit
competitive_programming/icpc/2017/K-tarot-sham-boast/solution.tex to update the written solution and
competitive_programming/icpc/2017/K-tarot-sham-boast/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 K
Tarot Sham Boast
Time limit: 2 seconds
Curse your rival! Every year at the annual Rock Paper Scissors tournament, you have made it to the final
match. (Your Rock technique is unmatched, and your Paper cuts to the bone! Your Scissors need a little
work, though.) But every year, he defeats you, even though his moves appear entirely random! And he
claims to the press that he simply cannot be beaten. What is his secret?
Fortunately, you think you have figured it out. This year, just before the tournament, you caught him visiting
various shamans around town. Aha! He is using the supernatural against you! You figured two can play at
this game. So you went and visited a set of fortune-tellers, who have each used a Tarot deck to predict a
sequence that your rival will end up using, sometime during the match.
However, your initial excitement has passed, and now you are feeling a little silly. This cannot possibly
work, right? In the end it feels like you have paid good money for a fraudulent, random set of predictions.
Oh well; you might as well keep an eye out for some of them during the match. But which predictions will
you use?
In the final match, you and your rival will play n rounds of Rock Paper Scissors. In each round, your rival
and you will both choose one of the three options (Rock, Paper, or Scissors). Based on your selections, a
winner of the round will be determined (exactly how is irrelevant to this problem).
Given the length of the final match and the various predictions, sort them in order of how likely they are to
appear sometime during the match as a contiguous sequence of options chosen by your rival, assuming he
is choosing his symbol in each round independently and uniformly at random.
Input
The first line of input contains two integers n (1 ≤ n ≤ 106 ), the number of rounds in the final match, and
s (1 ≤ s ≤ 10), the number of sequences. The remaining s lines each describe a prediction, consisting
of a string of characters ‘R’, ‘P’, and ‘S’. All predictions have the same length, which is between 1 and n
characters long, inclusive, and no longer than 105 .
Output
Display all of the predictions, sorted by decreasing likelihood of appearance sometime during the final
match. In the case of tied predictions, display them in the same order as in the input.
Sample Input 1 Sample Output 1
3 4 PS
PP PP
RR RR
PS SS
SS
Rapid City
event
sponsor
ICPC 2017
Sample Input 2 Sample Output 2
20 3 PRSPS
PRSPS PPSPP
SSSSS SSSSS
PPSPP
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\\K. Tarot Sham Boast}
\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;
}