LIS of Sequence (Codeforces 486E)
Tags: Math, hashing

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.Nam created a sequence a consisting of n (1 ≤ n ≤ 105) elements a1, a2, ..., an (1 ≤ ai ≤ 105). A subsequence ai1, ai2, ..., aik where 1 ≤ i1 < i2 < ... < ik ≤ n is called increasing if ai1 < ai2 < ai3 < ... < aik. An increasing subsequence is called longest if it has maximum length among all increasing subsequences. Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups: group of all i such that ai belongs to no longest increasing subsequences. group of all i such that ai belongs to at least one but not every longest increasing subsequence. group of all i such that ai belongs to every longest increasing subsequence. Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.

Input: The first line contains the single integer n (1 ≤ n ≤ 105) denoting the number of elements of sequence a.The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 105).

Output: Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.

Note: In the second sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a1, a2, a4} = {1, 3, 5} and {a1, a3, a4} = {1, 2, 5}.In the third sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a1, a3, a4} = {1, 2, 3}.

Sample Inputs:
1
4

4
1 3 2 5

4
1 5 2 3

Sample Outputs:
3

3223

3133

Solution (Python):
import bisect

def lis(arr, arr2):
    last = [-100]
    for i in range(len(arr)):
        if last[-1] < arr[i]:
            last.append(arr[i])
        idx = bisect.bisect_left(last, arr[i])
        last[idx] = arr[i]
        arr2[i] = idx
n = int(input())
arr = list(map(int, input().split()))
li = [0] * n
lis(arr, li)
max_len = max(li)
brr = [1000000 - arr[i] for i in range(n)]
brr.reverse()
crr = [0] * n
lis(brr, crr)
drr = list(reversed(crr))
ans = [1] * n
for i in range(n):
    if li[i] + drr[i] == max_len + 1:
        ans[i] = 3
max_val = 0
for i in range(n):
    if ans[i] != 1:
        if arr[i] <= max_val:
            ans[i] = 2
        max_val = max(max_val, arr[i])
min_val = 1000000
for i in range(n - 1, -1, -1):
    if ans[i] != 1:
        if arr[i] >= min_val:
            ans[i] = 2
        min_val = min(min_val, arr[i])
print(''.join(map(str, ans)))

Solution (Python):
import bisect

def main():
    n = int(input())
    nums = list(map(int, input().split(' ')))
    prefix_lengths = lis_length(nums)
    suffix_lengths = lis_length(list((-nums[n - i - 1] for i in range(n))))
    length = prefix_lengths[-1]
    cases = [0] * n
    combination = {}
    for i in range(n):
        a = prefix_lengths[i]
        b = suffix_lengths[n - i - 1]
        if a + b + 1 == length:
            if (a, b) in combination:
                cases[combination[a, b]] = 2
                cases[i] = 2
            else:
                combination[a, b] = i
                cases[i] = 3
        else:
            cases[i] = 1
    print(''.join((f'{x}' for x in cases)))

def lis_length(nums: list):
    length = []
    possible = []
    for n in nums:
        ind = bisect.bisect_left(length, n)
        if ind == len(length):
            length.append(n)
        else:
            length[ind] = n
        possible.append(ind)
    possible.append(len(length))
    return possible
if __name__ == '__main__':
    main()

Solution (Python):
def main():

    def parser():
        while 1:
            data = list(input().split(' '))
            for number in data:
                if len(number) > 0:
                    yield number
    input_parser = parser()
    gets = lambda : next(input_parser)

    def getNum():
        data = gets()
        try:
            return int(data)
        except ValueError:
            return float(data)
    from bisect import bisect_left as binsleft
    MAXA = int(9000000000.0)
    n = getNum()
    RANGN = range(n)
    a = [getNum() for _ in RANGN]
    revlis = []
    g = [MAXA] * n
    for i in reversed(RANGN):
        x = -a[i]
        pt = binsleft(g, x)
        revlis.append(pt + 1)
        if x < g[pt]:
            g[pt] = x
    hlis = max(revlis)
    (lis, inlis) = ([], [])
    d = [0] * n
    for i in RANGN:
        g[i] = MAXA
    for i in RANGN:
        pt = binsleft(g, a[i])
        lis.append(pt + 1)
        inlis.append(lis[i] + revlis[n - i - 1] > hlis)
        d[pt] += inlis[-1]
        if a[i] < g[pt]:
            g[pt] = a[i]
    print(''.join(['32'[d[lis[i] - 1] > 1] if inlis[i] else '1' for i in RANGN]))
if __name__ == '__main__':
    main()