curiousfellow's blog

Interesting XOR OR problem (GOOGLE OA)
By curiousfellow, history, 103 minutes ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
102 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
101 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by curiousfellow (previous revision, new revision, compare).

→ Reply
»
72 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

→ Reply