All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Permutation and reverse



This is an Approximate problem!
The Museum of Tomorrow (Museu do Amanhã) is a science museum in the city of Rio de Janeiro, Brazil. The main exhibition takes visitors through five main areas: Cosmos, Earth, Anthropocene, Tomorrow and Now via a number of experiments and experiences. The museum mixes science with an innovative design to focus on sustainable cities.

enter image description here

Today, manager of the museum is planning to conduct a quiz in which visitors can participate and win free ticket to the museum.

There are $$n$$ cards on the table and each card has a unique integer ( from $$1$$ to $$n$$ ) written on it. The cards represent a permutation $$p$$ of size $$n$$. A visitor can perform many operations. In one operation, a visitor will select a continuous segment of cards and reverse the order of the cards. The task is to convert $$p$$ into identity permutation ( i.e. all the cards have to be in strictly increasing order ).

To decide the winner of the quiz, the manager will give a score to the sequence of operations. The score will depend on the length of continuous segments the visitor will select and another permutation $$a$$ of size $$n$$.

The score is computed in the following way:

Let's define a sequence of lengths of all the continuous segments selected by a visitor as $$lens$$ and an infinite sequence $$b$$: $$b_i = a_{i \mod n}$$. Consider a sub-sequence of $$b$$ which is equal to $$lens$$ and have the smallest position of the last element. Let the smallest possible position of last element be $$pos$$. Then, the score of the operation will be $$10^5 \cdot \frac{n^2}{pos+1}$$.

The visitor who's score is maximum will win and will get a free ticket to the museum.

Input format

The first line of input contains the single integer $$n$$ ($$1 \leq n \leq 100)$$.

The second line of input contains $$n$$ integers $$p_i$$ ($$1 \leq p_i \leq n$$) - permutation $$p$$.

The third line of input contains $$n$$ integers $$a_i$$ ($$1 \leq a_i \leq n$$) - permutation $$a$$.

Output format

In the first line of input print single integer $$q$$ ($$0 \leq q \leq 10^5$$) - number of operations.

Then print $$q$$ lines. In the $$i$$-th of them print two integers $$l_i$$ and $$r_i$$ ($$1 \leq l_i \leq r_i \leq n$$) - continuous segment of cards which you want to reverse.

Note that $$lens_i = r_i - l_i + 1$$.


This is approximate problem and total score is sum of score of all test-cases and points of a solution is scaled based on best solution. Details of scoring is mentioned above.


There are $$100$$ tests. For each test independently: $$n$$ was generated randomly from interval $$[90, 100]$$. After both $$p$$ and $$a$$ were generated randomly.

After contest ending we will add $$100$$ more random tests in same manner but with new seeds.

3 1 2
2 1 3
1 3
1 2
1 1

$$lens$$ = $$(3, 2, 1)$$

$$b$$ = $$(2, 1, 3, 2, 1, 3, 2, 1, 3, ...)$$

Find the subsequence: $$(2, 1, [3], [2], [1], 3, 2, 1, 3, ...)$$. So $$pos=5$$ and score for this test will be $$10^5 \cdot \frac{3^2}{5+1}= 150000 $$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

July Circuits '17

View All Notifications