Rating Compression (Codeforces 1450D)
Tags: Greedy, two pointers

On the competitive programming platform CodeCook, every person has a rating graph described by an array of integers $$$a$$$ of length $$$n$$$. You are now updating the infrastructure, so you've created a program to compress these graphs.The program works as follows. Given an integer parameter $$$k$$$, the program takes the minimum of each contiguous subarray of length $$$k$$$ in $$$a$$$.More formally, for an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$, define the $$$k$$$-compression array of $$$a$$$ as an array $$$b$$$ of length $$$n-k+1$$$, such that $$$$$$b_j =\min_{j\le i\le j+k-1}a_i$$$$$$For example, the $$$3$$$-compression array of $$$[1, 3, 4, 5, 2]$$$ is $$$[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}]=[1, 3, 2].$$$A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$m=3$$$ but there is $$$4$$$ in the array).A $$$k$$$-compression array will make CodeCook users happy if it will be a permutation. Given an array $$$a$$$, determine for all $$$1\leq k\leq n$$$ if CodeCook users will be happy after a $$$k$$$-compression of this array or not.

Input: The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$) — the number of test cases.The first line of the description of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 3\cdot 10^5$$$) — the length of the array.The second line of the description of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — the elements of the array.It is guaranteed, that the sum of $$$n$$$ for all test cases does not exceed $$$3\cdot 10^5$$$.

Output: For each test case, print a binary string of length $$$n$$$. The $$$k$$$-th character of the string should be $$$1$$$ if CodeCook users will be happy after a $$$k$$$-compression of the array $$$a$$$, and $$$0$$$ otherwise. 

Note: In the first test case, $$$a=[1, 5, 3, 4, 2]$$$.  The $$$1$$$-compression of $$$a$$$ is $$$[1, 5, 3, 4, 2]$$$ and it is a permutation.  The $$$2$$$-compression of $$$a$$$ is $$$[1, 3, 3, 2]$$$ and it is not a permutation, since $$$3$$$ appears twice.  The $$$3$$$-compression of $$$a$$$ is $$$[1, 3, 2]$$$ and it is a permutation.  The $$$4$$$-compression of $$$a$$$ is $$$[1, 2]$$$ and it is a permutation.  The $$$5$$$-compression of $$$a$$$ is $$$[1]$$$ and it is a permutation. 

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

Sample Outputs:
10111
0001
00111
1111111111
000

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def gift():
    for _ in range(t):
        n = int(input())
        A = [int(a) - 1 for a in input().split()]
        C = [0] * n
        for a in A:
            C[a] += 1
        (l, r) = (0, n - 1)
        for i in range(n):
            if C[i] != 1:
                break
            if A[l] == i:
                l += 1
            elif A[r] == i:
                r -= 1
            else:
                break
        a0 = min(C)
        k = min(i + 1, n - 1) if C[i] else i
        ans = str(a0) + '0' * (n - k - 1) + '1' * k
        yield ans
if __name__ == '__main__':
    t = int(input())
    ans = gift()
    print(*ans, sep='\n')

Solution (Python):
from sys import stdin
T = int(stdin.readline().strip())
for casos in range(T):
    n = int(stdin.readline().strip())
    s = list(map(int, stdin.readline().strip().split()))
    if n == 1:
        print('1')
        continue
    cnt = [0 for i in range(n + 2)]
    for i in s:
        cnt[i] += 1
    ans = '1'
    for i in range(1, n + 1):
        if cnt[i] != 1:
            ans = '0'
            break
    aux = ''
    if cnt[1] > 0:
        aux += '1'
        next = 2
        pos1 = 0
        pos2 = n - 1
        for i in range(2, n):
            if s[pos1] == i - 1 and cnt[i - 1] == 1 and (cnt[i] > 0):
                pos1 += 1
                aux += '1'
            elif s[pos2] == i - 1 and cnt[i - 1] == 1 and (cnt[i] > 0):
                pos2 -= 1
                aux += '1'
            else:
                while len(aux) < n - 1:
                    aux += '0'
                break
    else:
        aux = '0' * (n - 1)
    ans += aux[::-1]
    print(ans)

Solution (Python):
t = int(input())
for _ in range(t):
    output = ''
    n = int(input())
    alist = input().split()
    alist = [int(ele) for ele in alist]
    left = [0 for _ in range(n)]
    right = [0 for _ in range(n)]
    stack = []
    for i in range(len(alist)):
        while len(stack) != 0 and alist[i] <= alist[stack[-1]]:
            out = stack.pop()
            right[out] += i - out - 1
            left[i] += 1 + left[out]
        stack.append(i)
    while len(stack) != 0:
        out = stack.pop()
        right[out] += n - out - 1
    span_list = [left[i] + right[i] + 1 for i in range(n)]
    sorted_span = [0 for _ in range(n)]
    for i in range(n):
        sorted_span[alist[i] - 1] = max(sorted_span[alist[i] - 1], span_list[i])
    output = ''
    debt = 0
    for i in range(n):
        if debt > 0:
            output += '0'
            debt = max(debt - 1, n - i - sorted_span[i] - 1)
            continue
        if sorted_span[i] >= n - i:
            output += '1'
        else:
            debt = n - i - sorted_span[i] - 1
            output += '0'
    print(output[::-1])