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

H. Matrxka

2013 World Finals St. Petersburg HOSTED BY ITMO Problem H Matrxka Time Limit: 5 seconds Matryoshkas are sets of traditional Russian wooden dolls of decreasing size placed one inside the other. A matryoshka doll can be opened to reveal a smaller figure of...

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

Matryoshkas are sets of traditional Russian wooden dolls of decreasing size placed one inside the other. A matryoshka doll can be opened to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside, and so on. The Russian Matryoshka Museum recently exhibited a col- lection of similarly designed matryoshka sets, differing only in the number of nested dolls in each set. Unfor- tunately, some over-zealous (and obviously unsupervised) children separated these sets, placing all the individual dolls in a row. There are n dolls in the row, each with an integer size. You need to reassemble the matryoshka sets, knowing neither the number of sets nor the number of dolls in each set. You know only that every complete set consists of dolls with consecutive sizes from 1 to some number m, Picture from Wikimedia Commons

which may vary between the different sets. When reassembling the sets, you must follow these rules:

  • You can put a doll or a nested group of dolls only inside a larger doll.
  • You can combine two groups of dolls only if they are adjacent in the row.
  • Once a doll becomes a member of a group, it cannot be transferred to another group or per- manently separated from the group. It can be temporarily separated only when combining two groups.

Your time is valuable, and you want to do this reassembly process as quickly as possible. The only time-consuming part of this task is opening and subsequently closing a doll, so you want to minimize how often you do this. For example, the minimum number of openings (and subsequent closings) when combining group [1, 2, 6] with the group [4] is two, since you have to open the dolls with sizes 6 and 4. When combining group [1, 2, 5] with the group [3, 4], you need to perform three openings. Write a program to calculate the minimum number of openings required to combine all disassembled matryoshka sets.

Input

The input consists of a single test case. A test case consists of two lines. The first line contains one integer n (1 ≤ n ≤ 500) representing the number of individual dolls in the row. The second line contains n positive integers specifying the sizes of the dolls in the order they appear in the row. Each size is between 1 and 500 inclusive.

Output

Display the minimum number of openings required when reassembling the matryoshka sets. If reassem- bling cannot be done (some of the kids might have been excessively zealous and taken some dolls), display the word impossible.

                                     ICPC 2013
2013 World Finals
                                St. Petersburg
                                HOSTED BY   ITMO

Sample Tests

Sample 1
Sample Input 
7
1 2 1 2 4 3 3
Sample Output 
impossible
Sample 2
Sample Input 
7
1 2 3 2 4 1 3
Sample Output 
7
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/2013/H-matr-xka/solution.texC++ implementationcompetitive_programming/icpc/2013/H-matr-xka/solution.cppStatement textcompetitive_programming/icpc/2013/H-matr-xka/statement.txtStatement PDFcompetitive_programming/icpc/2013/H-matr-xka/statement.pdfMetadatacompetitive_programming/icpc/2013/H-matr-xka/meta.jsonYear packetcompetitive_programming/icpc/2013/contest_problems.pdf