curiousfellow's blog

Interesting XOR OR problem (GOOGLE OA)
By curiousfellow, history, 4 months 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
  • +9
  • Vote: I do not like it

»
4 months 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
»
4 months 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
»
4 months 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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks , can you explain your approach and suggest similar problems

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply