Codeforces Round #631 (Div. 2) - Problem B

Problem Link : https://codeforces.com/contest/1330/problem/B

The problem is very easy to solve if you make some basic observations.

The main observation to solve this problem is you cannot take a contiguous segment which has repeated elements as it violates the property of permutation.

In the above figure it's impossible to go after 4 so it's no use checking.

Using this observation we try to make a contiguous array as long as we don't find a duplicate, because if we don't find a duplicate the current element either belongs to the permutation on the left side or the permutation on the right side. So after you get 2 arrays left and right , sort them and check if they form a permutation and if yes this is a valid case.

Now there can be two solutions as can be seen from pretest

5
1 4 3 2 1

So in the case above we have 2 valid solutions .

In first case will start forming a non repeating contiguous array from left and get 1 3 4 2 as left and 1 as right. 

In second case we will get 1 as left and 1 2 3 4 as right array.

So check from both the directions if you get 2 valid permutations and then output the result.

Do check that a[0] == 1 after you sort left and right array , as you can get 2 3 4 and 3 4 5 as 2 arrays and it will be a wrong solution.

Solution : https://codeforces.com/contest/1330/submission/75395895