All Tracks Algorithms Graphs Breadth First Search Problem

Permutation
Tag(s):

Algorithms, Breadth-first search, Easy, Graph

Problem
Editorial
Analytics

Given a permutation of 1 to n, you need to perform some operations to make it into increasing order. Each operation is to reverse an interval \(a_1,a_2,\dots,a_x(1\le x\le n)\) (a prefix). Your goal is to minimize the number of operations.

Input

The first line contains an integer \(n\) (\(1\le n\le 8\)).

The second line contains \(n\) space separated integers, representing the sequence \(a\).

Output

An integer representing the answer, that is, the minimum number of operations needed to make the permutation into increasing order.

SAMPLE INPUT
3
3 1 2
SAMPLE OUTPUT
2
Explanation

A possible way is to reverse \([1,3]\), and then \([1,2]\).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, 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, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?