Beautiful Numbers (Codeforces 1265B)
Tags: Math, two pointers

You are given a permutation $$$p=[p_1, p_2, \ldots, p_n]$$$ of integers from $$$1$$$ to $$$n$$$. Let's call the number $$$m$$$ ($$$1 \le m \le n$$$) beautiful, if there exists two indices $$$l, r$$$ ($$$1 \le l \le r \le n$$$), such that the numbers $$$[p_l, p_{l+1}, \ldots, p_r]$$$ is a permutation of numbers $$$1, 2, \ldots, m$$$.For example, let $$$p = [4, 5, 1, 3, 2, 6]$$$. In this case, the numbers $$$1, 3, 5, 6$$$ are beautiful and $$$2, 4$$$ are not. It is because:  if $$$l = 3$$$ and $$$r = 3$$$ we will have a permutation $$$[1]$$$ for $$$m = 1$$$;  if $$$l = 3$$$ and $$$r = 5$$$ we will have a permutation $$$[1, 3, 2]$$$ for $$$m = 3$$$;  if $$$l = 1$$$ and $$$r = 5$$$ we will have a permutation $$$[4, 5, 1, 3, 2]$$$ for $$$m = 5$$$;  if $$$l = 1$$$ and $$$r = 6$$$ we will have a permutation $$$[4, 5, 1, 3, 2, 6]$$$ for $$$m = 6$$$;  it is impossible to take some $$$l$$$ and $$$r$$$, such that $$$[p_l, p_{l+1}, \ldots, p_r]$$$ is a permutation of numbers $$$1, 2, \ldots, m$$$ for $$$m = 2$$$ and for $$$m = 4$$$. You are given a permutation $$$p=[p_1, p_2, \ldots, p_n]$$$. For all $$$m$$$ ($$$1 \le m \le n$$$) determine if it is a beautiful number or not.

Input: The first line contains the only integer $$$t$$$ ($$$1 \le t \le 1000$$$)  — the number of test cases in the input. The next lines contain the description of test cases.The first line of a test case contains a number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the given permutation $$$p$$$. The next line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are different) — the given permutation $$$p$$$.It is guaranteed, that the sum of $$$n$$$ from all test cases in the input doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print $$$t$$$ lines — the answers to test cases in the order they are given in the input. The answer to a test case is the string of length $$$n$$$, there the $$$i$$$-th character is equal to $$$1$$$ if $$$i$$$ is a beautiful number and is equal to $$$0$$$ if $$$i$$$ is not a beautiful number.

Note: The first test case is described in the problem statement.In the second test case all numbers from $$$1$$$ to $$$5$$$ are beautiful:  if $$$l = 3$$$ and $$$r = 3$$$ we will have a permutation $$$[1]$$$ for $$$m = 1$$$;  if $$$l = 3$$$ and $$$r = 4$$$ we will have a permutation $$$[1, 2]$$$ for $$$m = 2$$$;  if $$$l = 2$$$ and $$$r = 4$$$ we will have a permutation $$$[3, 1, 2]$$$ for $$$m = 3$$$;  if $$$l = 2$$$ and $$$r = 5$$$ we will have a permutation $$$[3, 1, 2, 4]$$$ for $$$m = 4$$$;  if $$$l = 1$$$ and $$$r = 5$$$ we will have a permutation $$$[5, 3, 1, 2, 4]$$$ for $$$m = 5$$$. 

Sample Inputs:
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

Sample Outputs:
101011
11111
1001

Solution (Python):
def solve():
    n = int(input())
    p = [0] * n
    data = list(map(int, input().split()))
    for i in range(n):
        p[data[i] - 1] = i
    l = n
    r = 0
    ans = ''
    for i in range(n):
        l = min(l, p[i])
        r = max(r, p[i])
        if r - l == i:
            ans += '1'
        else:
            ans += '0'
    print(ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
def s():
    n = int(input())
    a = [int(i) for i in input().split()]
    res = ''
    d = [0] * (n + 1)
    for i in range(n):
        d[a[i]] = i
    (mi, ma, i) = (d[1], d[1], 0)
    for k in d[1:]:
        mi = min(k, mi)
        ma = max(k, ma)
        if ma - mi > i:
            res += '0'
        else:
            res += '1'
        i += 1
    return res
t = int(input())
r = ''
for j in range(t):
    r += s() + '\n'
print(r)

Solution (Python):
def s():
    n = int(input())
    a = [int(i) for i in input().split()]
    res = ''
    d = [0] * (n + 1)
    for i in range(n):
        d[a[i]] = i
    (mi, ma, i) = (d[1], d[1], 0)
    for k in d[1:]:
        mi = min(k, mi)
        ma = max(k, ma)
        if ma - mi > i:
            res += '0'
        else:
            res += '1'
        i += 1
    return res
t = int(input())
r = [s() for i in range(t)]
for b in r:
    print(b)