Another MEX Problem (Codeforces 1870E)
Tags: DP, shortest paths

You are given an array of integers $$$a$$$ of size $$$n$$$. You can choose a set of non-overlapping subarrays of the given array (note that some elements may be not included in any subarray, this is allowed). For each selected subarray, calculate the MEX of its elements, and then calculate the bitwise XOR of all the obtained MEX values. What is the maximum bitwise XOR that can be obtained?The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:   The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.  The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.  The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not. 

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. This is followed by the description of the test cases.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the size of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$) — the array $$$a$$$.It is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$5000$$$.

Output: For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

Note: In the first test case, the maximum XOR is $$$2$$$ if we take the entire array, $$$\operatorname{MEX}([1, 0]) = 2$$$.In the second test case, the maximum XOR is $$$6$$$ if we partition the array into segments $$$[1, 2, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$:   $$$\operatorname{MEX}([1, 2, 0]) = 3$$$,  $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,  therefore, the XOR is $$$5 \oplus 3=6$$$.In the third test case, the maximum XOR is $$$7$$$ if we partition the array into segments $$$[1, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$:   $$$\operatorname{MEX}([1, 0]) = 2$$$,  $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,  therefore, the XOR is $$$5 \oplus 2 = 7$$$.

Sample Inputs:
4
2
1 0
10
1 2 0 7 1 2 0 2 4 3
10
2 1 0 7 1 2 0 2 4 3
3
1 2 1

Sample Outputs:
2
6
7
0

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

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    neigh = [[] for _ in range(n)]
    firstappear = [float('inf')] * (n + 1)
    appear = [set() for _ in range(n)]
    visited = set()
    for i in range(n):
        mex = 0
        currset = set()
        for j in range(i, -1, -1):
            currset.add(arr[j])
            premex = mex
            while mex in currset:
                mex += 1
            if mex > premex:
                if (j, mex) in visited:
                    continue
                visited.add((j, mex))
                neigh[j].append((i, mex))
                if i < firstappear[mex]:
                    firstappear[mex] = i
                    appear[i].add(mex)
    currset = set()
    for i in range(n):
        for (nextindex, mex) in neigh[i]:
            for num in currset:
                if firstappear[mex ^ num] > nextindex:
                    firstappear[mex ^ num] = nextindex
                    appear[nextindex].add(mex ^ num)
        for ele in appear[i]:
            currset.add(ele)
    ans = 0
    for i in range(1, n + 1):
        if firstappear[i] < float('inf'):
            ans = i
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
def main():
    """"""
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        MEX = [[0 for __ in range(n)] for ___ in range(n)]
        for l in range(n):
            vi = [0] * (n + 2)
            m = 0
            for r in range(l, n):
                vi[a[r]] = 1
                while vi[m] == 1:
                    m += 1
                MEX[l][r] = m
        ranges = [[] for __ in range(n + 1)]
        for l in range(n):
            for r in range(l, n):
                if l == r or (MEX[l + 1][r] != MEX[l][r] and MEX[l][r] != MEX[l][r - 1]):
                    ranges[r].append((l, MEX[l][r]))
        dp = [[] for __ in range(n)]
        for r in range(n):
            vi = [0] * (n + 2)
            if r - 1 >= 0:
                for xor in dp[r - 1]:
                    vi[xor] = 1
            for (l, mex) in ranges[r]:
                vi[mex] = 1
                if l - 1 >= 0:
                    for xor in dp[l - 1]:
                        vi[xor ^ mex] = 1
            arr = dp[r]
            for v in range(n + 2):
                if vi[v] == 1:
                    arr.append(v)
        ans = max(dp[n - 1])
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
def main():
    """"""
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        MEX = [[0 for __ in range(n)] for ___ in range(n)]
        for l in range(n):
            vi = [0] * (n + 2)
            m = 0
            for r in range(l, n):
                vi[a[r]] = 1
                while vi[m] == 1:
                    m += 1
                MEX[l][r] = m
        ranges = [[] for __ in range(n + 1)]
        for l in range(n):
            for r in range(l, n):
                if l == r or (MEX[l + 1][r] != MEX[l][r] and MEX[l][r] != MEX[l][r - 1]):
                    ranges[r].append((l, MEX[l][r]))
        dp = [[] for __ in range(n)]
        for r in range(n):
            vi = [0] * (n + 2)
            if r - 1 >= 0:
                for xor in dp[r - 1]:
                    vi[xor] = 1
            for (l, mex) in ranges[r]:
                vi[mex] = 1
                if l - 1 >= 0:
                    for xor in dp[l - 1]:
                        vi[xor ^ mex] = 1
            arr = dp[r]
            for v in range(n + 2):
                if vi[v] == 1:
                    arr.append(v)
        ans = max(dp[n - 1])
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()