Informatics in MAC (Codeforces 1935B)
Tags: Others, constructive algorithms

In the Master's Assistance Center, Nyam-Nyam was given a homework assignment in informatics.There is an array $$$a$$$ of length $$$n$$$, and you want to divide it into $$$k > 1$$$ subsegments$$$^{\dagger}$$$ in such a way that the $$$\operatorname{MEX} ^{\ddagger}$$$ on each subsegment is equal to the same integer.Help Nyam-Nyam find any suitable division, or determine that it does not exist.$$$^{\dagger}$$$A division of an array into $$$k$$$ subsegments is defined as $$$k$$$ pairs of integers $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ such that $$$l_i \le r_i$$$ and for each $$$1 \le j \le k - 1$$$, $$$l_{j + 1} = r_j + 1$$$, and also $$$l_1 = 1$$$ and $$$r_k = n$$$. These pairs represent the subsegments themselves.$$$^{\ddagger}\operatorname{MEX}$$$ of an array is the smallest non-negative integer that does not belong to the array.For example:   $$$\operatorname{MEX}$$$ of the array $$$[2, 2, 1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.  $$$\operatorname{MEX}$$$ of the array $$$[3, 1, 0, 1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.  $$$\operatorname{MEX}$$$ of the array $$$[0, 3, 1, 2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not. 

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output a single integer $$$-1$$$ if a suitable division does not exist.Otherwise, on the first line, output an integer $$$k$$$ ($$$2 \le k \le n$$$) — the number of subsegments in the division.Then output $$$k$$$ lines — the division into subsegments. The $$$i$$$-th line should contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the boundaries of the $$$i$$$-th subsegment.The following conditions must be satisfied: For all $$$1 \le j \le k - 1$$$, $$$l_{j + 1} = r_j + 1$$$; $$$l_1 = 1$$$, $$$r_k = n$$$.If there are multiple possible solutions, output any of them.

Note: In the first test case, the array $$$a$$$ can be divided into $$$2$$$ subsegments with boundaries $$$[1, 1]$$$ and $$$[2, 2]$$$:   $$$\operatorname{MEX}$$$ of the first subsegment $$$[0]$$$ is $$$1$$$, as $$$0$$$ belongs to the subsegment, but $$$1$$$ does not.  $$$\operatorname{MEX}$$$ of the second subsegment $$$[0]$$$ is $$$1$$$, as $$$0$$$ belongs to the subsegment, but $$$1$$$ does not. In the second test case, it can be proven that the required division does not exist.In the third test case, the array $$$a$$$ can be divided into $$$3$$$ subsegments with boundaries $$$[1, 3]$$$, $$$[4, 5]$$$, $$$[6, 8]$$$:   $$$\operatorname{MEX}$$$ of the first subsegment $$$[0, 1, 7]$$$ is $$$2$$$, as $$$0$$$ and $$$1$$$ belong to the subsegment, but $$$2$$$ does not.  $$$\operatorname{MEX}$$$ of the second subsegment $$$[1, 0]$$$ is $$$2$$$, as $$$0$$$ and $$$1$$$ belong to the subsegment, but $$$2$$$ does not.  $$$\operatorname{MEX}$$$ of the third subsegment $$$[1, 0, 3]$$$ is $$$2$$$, as $$$0$$$ and $$$1$$$ belong to the subsegment, but $$$2$$$ does not. 

Sample Inputs:
5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
2 2 2
4
0 1 2 0

Sample Outputs:
2
1 1
2 2
-1
3
1 3
4 5
6 8
3
1 1
2 2
3 3
-1

Solution (Python):
from re import L
import sys
from math import *
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solve():
    n = inp()
    A = inlt()
    MEX_arr = [0] * n
    for a in A:
        MEX_arr[a] = 1
    MEX = n
    if 0 in MEX_arr:
        MEX = MEX_arr.index(0)
    if MEX == 0:
        print(2)
        print(1, 1)
        print(2, n)
        return
    r = 0
    seen = set()
    while r < n:
        if A[r] < MEX:
            seen.add(A[r])
        r += 1
        if len(seen) == MEX:
            break
    seen2 = set()
    for i in range(r, n):
        if A[i] < MEX:
            seen2.add(A[i])
    if len(seen2) == MEX:
        print(2)
        print(1, r)
        print(r + 1, n)
    else:
        print(-1)
if __name__ == '__main__':
    t = inp()
    for i in range(t):
        solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline
from collections import defaultdict

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = set(a.copy())
    for mx in range(0, n + 2):
        if mx not in b:
            break
    s = set()
    l = 0
    ans = []
    for i in range(n):
        if a[i] < mx:
            s.add(a[i])
        if len(s) == mx:
            ans.append([l, i])
            l = i + 1
            s.clear()
    if ans:
        ans[-1][1] = n - 1
    if len(ans) > 1:
        print(len(ans))
        for x in ans:
            print(x[0] + 1, x[1] + 1)
    else:
        print(-1)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
from collections import deque
from bisect import bisect_left

def readline() -> str:
    return sys.stdin.readline().strip()

def inputArray() -> list:
    return list(map(int, sys.stdin.readline().strip().split()))

def inputString() -> list:
    return list(input().split())

def tc(solve):
    for _ in range(int(readline())):
        solve()

@tc
def solve():
    (n,) = inputArray()
    a = inputArray()
    s = set(a)
    x = -1
    for i in range(n):
        if i not in s:
            x = i
            break
    ans = []
    j = -1
    ps = set()
    flag = True
    for i in a:
        if len(ps) == x and i < x and flag:
            ps = set()
            flag = False
            ps.add(i)
            j += 1
            ans.append([i])
        else:
            if x == 0 and j >= 0:
                ans.append([])
                j += 1
                flag = False
            if j == -1:
                ans.append([])
                j = 0
            ans[j].append(i)
            if i < x:
                ps.add(i)
    if flag or len(ps) != x:
        print(-1)
    else:
        print(len(ans))
        l = 1
        for i in ans:
            print(l, l + len(i) - 1)
            l += len(i)