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

K. Tarot Sham Boast

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

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 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 Tests

Sample 1
Sample Input 
 3 4
 PP
 RR
 PS
 SS
Sample Output 
PS
PP
RR
SS


Rapid City

sponsor
ICPC 2017
Sample 2
Sample Input 
20 3
PRSPS
SSSSS
PPSPP
Sample Output 
PRSPS
PPSPP
SSSSS
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/K-tarot-sham-boast/solution.texC++ implementationcompetitive_programming/icpc/2017/K-tarot-sham-boast/solution.cppStatement textcompetitive_programming/icpc/2017/K-tarot-sham-boast/statement.txtStatement PDFcompetitive_programming/icpc/2017/K-tarot-sham-boast/statement.pdfMetadatacompetitive_programming/icpc/2017/K-tarot-sham-boast/meta.jsonYear packetcompetitive_programming/icpc/2017/contest_problems.pdf