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)