Xor-Subsequence (easy version) (Codeforces 1720D1)
Tags: DP, trees

It is the easy version of the problem. The only difference is that in this version $$$a_i \le 200$$$.You are given an array of $$$n$$$ integers $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$. Bryap wants to find the longest beautiful subsequence in the array.An array $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$, where $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$, is a subsequence of length $$$m$$$ of the array $$$a$$$.Subsequence $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ of length $$$m$$$ is called beautiful, if the following condition holds:   For any $$$p$$$ ($$$0 \le p < m - 1$$$) holds: $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$. Here $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$. For example, $$$2 \oplus 4 = 6$$$ and $$$3 \oplus 1=2$$$.Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$)  — 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 \leq n \leq 3 \cdot 10^5$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 200$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case print a single integer — the length of the longest beautiful subsequence.

Note: In the first test case, we can pick the whole array as a beautiful subsequence because $$$1 \oplus 1 < 2 \oplus 0$$$.In the second test case, we can pick elements with indexes $$$1$$$, $$$2$$$ and $$$4$$$ (in $$$0$$$-indexation). For this elements holds: $$$2 \oplus 2 < 4 \oplus 1$$$ and $$$4 \oplus 4 < 1 \oplus 2$$$.

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

Sample Outputs:
2
3
6

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def getnum(subarr):
    m = len(subarr)
    dp = [0] * m
    for i in range(m):
        dp[i] = 1
        for j in range(i):
            if i ^ subarr[j] < j ^ subarr[i]:
                dp[i] = max(dp[j] + 1, dp[i])
    return max(dp)

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = 0
    base = n // 256
    if n % 256 > 0:
        base += 1
    for k in range(base):
        temp = arr[256 * k:256 * k + 256]
        ans = max(ans, getnum(temp))
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
def solve(n, arr):
    dyn = [1] * len(arr)
    for (lasti, x) in enumerate(dyn):
        endj = min(len(arr), lasti - lasti % 256 + 256)
        arrlasti = arr[lasti]
        dynlasti = dyn[lasti]
        dynlasti1 = dyn[lasti] + 1
        for j in range(lasti + 1, endj):
            if arrlasti ^ j < arr[j] ^ lasti:
                if dyn[j] <= dynlasti:
                    dyn[j] = dynlasti1
    return max(dyn)
import os
import io
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    T = int(input().decode().strip())
    for t in range(T):
        n = int(input().decode().strip())
        arr = [int(x) for x in input().decode().strip().split()]
        res = solve(n, arr)
        print(res)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
m = 256
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans0 = 0
    dp = [1] * n
    for i in range(n // m + min(n % m, 1)):
        (l, r) = (i * m, min((i + 1) * m, n))
        ma = 0
        for j in range(l, r):
            (dpj, aj) = (1, a[j])
            for k in range(l, j):
                if a[k] ^ j < aj ^ k:
                    dpj = max(dpj, dp[k] + 1)
            dp[j] = dpj
            ma = max(ma, dpj)
        ans0 = max(ans0, ma)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))