ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2008, Eastern subregion quarterfinals

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Shortest Subchain

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
A chain p is given in a directed graph without loops or multiple edges. It is required to specify its subchain q such that
  • the initial and final vertices of the chains p and q coincide;
  • the edges in the chain q are in the same order as in the chain p;
  • the chain q has the minimal possible number of edges under the given conditions.


The chain p is given by the list of its vertices. The first line contains the number n of vertices in the list, 2 ≤ n ≤ 100000 (thus, the length of the chain is n−1). The following lines contain n numbers of vertices (they are integers in the range from 1 to 10000). The numbers are separated by spaces or linebreaks. No two successive vertices in the list coincide.


Output the vertices of the chain q by giving their numbers separated by a space. Chain q may consist of single a vertex.


1 2 7 3 2
8 4 8 5
1 2 8 5
Problem Author: Vladimir Yakovlev (idea by Magaz Asanov)
Problem Source: NEERC 2008, Eastern subregion quarterfinals
To submit the solution for this problem go to the Problem set: 1651. Shortest Subchain