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

E. Evolution in Parallel

It is 2178, and alien life has been discovered on a distant planet. There seems to be only one species on the planet and they do not reproduce as animals on Earth do. Even more amazing, the genetic makeup of every single organism is identical! The genetic m...

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

It is 2178, and alien life has been discovered on a distant planet. There seems to be only one species on the planet and they do not reproduce as animals on Earth do. Even more amazing, the genetic makeup of every single organism is identical! The genetic makeup of each organism is a single sequence of nucleotides. The nucleotides come in three types, denoted by ‘A’ (Adenine), ‘C’ (Cytosine), and ‘M’ (Muamine). According to one hypothesis, evolution on this planet occurs when a new nucleotide is inserted somewhere into the genetic sequence of an existing organism. If this change is evolutionarily advantageous, then organisms with the new sequence quickly replace ones with the old sequence. It was originally thought that the current species evolved this way from a single, very simple organism with a single-nucleotide genetic sequence, by way of mutations as described above. However, fossil evidence suggests that this might not have been the case. Right now, the research team you are working with is trying to validate the concept of “parallel evolution” – that there might actually have been two evolutionary paths evolving in the fashion described above, and eventually both paths evolved to the single species present on the planet today. Your task is to verify whether the parallel evolution hypothesis is consistent with the genetic material found in the fossil samples gathered by your team.

Input

The input begins with a number n (1 ≤ n ≤ 4 000) denoting the number of nucleotide sequences found in the fossils. The second line describes the nucleotide sequence of the species currently living on the planet. Each of the next n lines describes one nucleotide sequence found in the fossils. Each nucleotide sequence consists of a string of at least one but no more than 4 000 letters. The strings contain only upper-case letters A, C, and M. All the nucleotide sequences, including that of the currently live species, are distinct.

Output

Display an example of how the nucleotide sequences in the fossil record participate in two evolution- ary paths. The example should begin with one line containing two integers s1 and s2 , the number of nucleotide sequences in the fossil record that participate in the first path and second path, respectively. This should be followed by s1 lines containing the sequences attributed to the first path, in chronological order (from the earliest), and then s2 lines containing the sequences attributed to the second path, also in chronological order. If there are multiple examples, display any one of them. If it is possible that a sequence could appear in the genetic history of both species, your example should assign it to exactly one of the evolutionary paths. If it is impossible for all the fossil material to come from two evolutionary paths, display the word impossible.

Sample Tests

Sample 1
Sample Input 
5
AACCMMAA
ACA
MM
ACMAA
AA
Sample Output 
1 4
MM
A
AA
ACA
ACMAA
Sample 2
Sample Input 
3
ACMA
ACM
ACA
AMA
Sample Output 
impossible
Sample 3
Sample Input 
1
AM
MA
Sample Output 
impossible
Sample 4
Sample Input 
4
AAAAAA
AA
AAA
A
AAAAA
Sample Output 
0 4
A
AA
AAA
AAAAA
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/2015/E-evolution-in-parallel/solution.texC++ implementationcompetitive_programming/icpc/2015/E-evolution-in-parallel/solution.cppStatement textcompetitive_programming/icpc/2015/E-evolution-in-parallel/statement.txtStatement PDFcompetitive_programming/icpc/2015/E-evolution-in-parallel/statement.pdfMetadatacompetitive_programming/icpc/2015/E-evolution-in-parallel/meta.jsonYear packetcompetitive_programming/icpc/2015/contest_problems.pdf