Interesting XOR OR problem (GOOGLE OA)

Revision en2, by curiousfellow, 2024-07-16 19:51:07

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:

$$$ F(B) = [(B_1 \, | \, B_2 \, | \, \ldots \, | \, B_K) \, \oplus \, (B_{K+1} \, | \, B_{K+2} \, | \, \ldots \, | \, B_{2K}) ]$$$

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.

Tags dp, xor, google

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English curiousfellow 2024-07-16 19:51:07 12
en1 English curiousfellow 2024-07-16 19:48:46 972 Initial revision (published)