yashv's blog

Help needed in Google APAC 2016 Round E problem C
By yashv, history, 9 years ago, In English

The problem is Google APAC 2016 Round E Problem C

I can't understand the problem in my solution described below

We can create a tree and then find the pattern as follows:

As can be seen above, there are only 8 possible numbers (not necessarily distinct) shown below: {0, x, x&k, x|k, (∼x)&k, x&(∼k), x^k, k} (where ∼n represents bitwise negation of n; and all operators have their usual meanings)

So we can create a transition table for each of these numbers for each of the possiblities of AND, OR, XOR. Using this logic I arrived at this solution

But my program is giving incorrect answer. Can someone point out the flaw in logic and/or implementation, please.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I also used the same logic for solving this question !!!

Your logic is right,but there was bug in your dp equation...

your working code : http://ideone.com/aoqfdZ

my code: http://ideone.com/QixOw6

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for reply. But ar[i]&k, ar[i]|k and ar[i]^k will be one of ar[i]'s whose index is already in tr[][] table. S, why can't I just use this table for the calculation?

    → Reply