Dreamoon Likes Permutations (Codeforces 1330B)
Tags: Math, implementation

The sequence of $$$m$$$ integers is called the permutation if it contains all integers from $$$1$$$ to $$$m$$$ exactly once. The number $$$m$$$ is called the length of the permutation.Dreamoon has two permutations $$$p_1$$$ and $$$p_2$$$ of non-zero lengths $$$l_1$$$ and $$$l_2$$$.Now Dreamoon concatenates these two permutations into another sequence $$$a$$$ of length $$$l_1 + l_2$$$. First $$$l_1$$$ elements of $$$a$$$ is the permutation $$$p_1$$$ and next $$$l_2$$$ elements of $$$a$$$ is the permutation $$$p_2$$$. You are given the sequence $$$a$$$, and you need to find two permutations $$$p_1$$$ and $$$p_2$$$. If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) denoting the number of test cases in the input.Each test case contains two lines. The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 200\,000$$$): the length of $$$a$$$. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n-1$$$).The total sum of $$$n$$$ is less than $$$200\,000$$$.

Output: For each test case, the first line of output should contain one integer $$$k$$$: the number of ways to divide $$$a$$$ into permutations $$$p_1$$$ and $$$p_2$$$.Each of the next $$$k$$$ lines should contain two integers $$$l_1$$$ and $$$l_2$$$ ($$$1 \leq l_1, l_2 \leq n, l_1 + l_2 = n$$$), denoting, that it is possible to divide $$$a$$$ into two permutations of length $$$l_1$$$ and $$$l_2$$$ ($$$p_1$$$ is the first $$$l_1$$$ elements of $$$a$$$, and $$$p_2$$$ is the last $$$l_2$$$ elements of $$$a$$$). You can print solutions in any order.

Note: In the first example, two possible ways to divide $$$a$$$ into permutations are $$$\{1\} + \{4, 3, 2, 1\}$$$ and $$$\{1,4,3,2\} + \{1\}$$$.In the second example, the only way to divide $$$a$$$ into permutations is $$$\{2,4,1,3\} + \{2,1\}$$$.In the third example, there are no possible ways.

Sample Inputs:
6
5
1 4 3 2 1
6
2 4 1 3 2 1
4
2 1 1 3
4
1 3 3 1
12
2 1 3 4 5 6 7 8 9 1 10 2
3
1 1 1

Sample Outputs:
2
1 4
4 1
1
4 2
0
0
1
2 10
0

Solution (Python):
def count(a):
    a.sort()
    n = len(a)
    for i in range(n):
        if a[i] != i + 1:
            return 0
    return 1
t = int(input())
while t:
    n = int(input())
    a = list(map(int, input().split()))
    m = max(a)
    c1 = count(a[:m]) and count(a[m:])
    a.reverse()
    c2 = count(a[:m]) and count(a[m:])
    k = c1 + c2
    if k == 0:
        print(0)
    elif k == 1:
        print(1)
        if c1 == 1:
            print(m, n - m)
        if c2 == 1:
            print(n - m, m)
    elif m == n - m:
        print(1)
        print(m, n - m)
    else:
        print(2)
        print(m, n - m)
        print(n - m, m)
    t -= 1

Solution (Python):
import sys
read = sys.stdin.buffer.readline
for _ in range(int(read())):
    n = int(read())
    a = list(map(int, read().split()))
    ans = set()
    mx = max(a)
    for i in range(2):
        if set(a[:mx]) == set(range(1, mx + 1)) and set(a[mx:]) == set(range(1, n - mx + 1)):
            ans.add(mx)
        mx = n - mx
    print(len(ans))
    for i in ans:
        print(i, n - i)

Solution (Python):
def search(p1, p2, lp1, lp2):
    used_1 = [True] + [False] * lp1
    for ele in p1:
        if ele > lp1:
            return False
        elif used_1[ele] == False:
            used_1[ele] = True
        else:
            return False
    used_2 = [True] + [False] * lp2
    for ele in p2:
        if ele > lp2:
            return False
        elif used_2[ele] == False:
            used_2[ele] = True
        else:
            return False
    return True

def solve(ans1, ans2):
    n = int(input())
    a = [int(x) for x in input().split()]
    ma = max(a)
    count = 0
    p1 = a[0:ma:1]
    p2 = a[ma:]
    stm1 = search(p1, p2, ma, n - ma)
    if stm1:
        count += 1
        ans2.append([ma, n - ma])
    if ma == n - ma:
        ans1.append(count)
        return
    p1 = a[0:n - ma:1]
    p2 = a[n - ma:]
    stm2 = search(p1, p2, n - ma, ma)
    if stm2:
        count += 1
        ans2.append([n - ma, ma])
    ans1.append(count)
    return
n = int(input())
ans1 = []
ans2 = []
for i in range(n):
    solve(ans1, ans2)
for ele in ans1:
    print(ele)
    for i in range(ele):
        print(*ans2[0])
        ans2.pop(0)