You are given the following:

Two integers ( N ) and ( K ) An array ( A ) of size ( N )

Let sequence $$$ B = (B_1, B_2, \ldots, B_{2K}) )$$$ of size 2K be a subsequence of array A .

Let's define F(B) as:

Where | denotes the bitwise OR operation and $$$\oplus$$$ denotes the bitwise XOR operation.

### Task

Determine the maximum value of F(B) for all possible sequences B .

$$$[ 1 \leq T \leq 102 ]$$$ $$$[ 2 \leq N \leq 1001 ]$$$ $$$[ 1 \leq K \leq \left\lfloor \frac{N}{2} \right\rfloor ]$$$ $$$[ 0 \leq A_i < 2^7 ]$$$

**Note:** A sequence ( X ) is a subsequence of sequence ( Y ) if ( X ) can be obtained from ( Y ) by deleting several (possibly zero or all) elements without changing the order of the remaining elements.

This question was asked in a Google OA.

i remember seeing a similar problem in one of the div 4s with constraint of Ai being 2^6 .

Auto comment: topic has been updated by curiousfellow (previous revision, new revision, compare).here is my approach https://pastebin.com/ZD37sJR6

-> finding the first index from left and right to generate a mask and we need to make sure it is formed with k elements -> bruteforce for all num < 128 , set the result of first k numbers as mask -> now as if pre[mask] < suf[mask ^ num]

thanks , can you explain your approach and suggest similar problems

https://pastebin.com/8hcWUGxs

Here is the modified approach using DP. why dp ?

-> our answer is a number < 128 so lets check for each number if it is possible -> let us set the bitwise OR of first set of k numbers in the sequence as l

-> then the other part is given by (number ^ l)

-> now bitwise or of first set of k numbers and latter is (l , number ^ l )

-> if we know what is the first index in array so that we can construct a sequence of k numbers which will generate bitwise OR of l , and same for number ^ l from the right . we can simply check if they are not intersecting then it is clearly possible for such a construction to exists.

-> lets start calling numbers as mask ( < 128 ). conditions to form this mask are

-> minimum elements required to form mask <= k (mandatory) && submasks of this mask >= k ( take minimum elements to form mask and fill in with submasks for the rest of the part).

-> maintain a dp for minimum elements required to form a mask and no of submask for all masks till now. (checkout the solution from here to get a better idea)