Spectacular_Lemma's blog

Please help me with this Bits Question!!!
By Spectacular_Lemma, history, 16 months ago, In English

Given an array A of size n and a target integer X, we need to find an array B such that ΣA[i]&B[i]=X (1<=i<=n).

If multiple answers are possible find the lexicographically smallest array B.

As constraints are unknown, I hope someone can help me to find suitable constraints too.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you give me more informations ?

a[i] <= ? b[i] <= ? n <= ?

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

    He said constraints are unknown

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

      Ahh, sorry I really didn't notice that. :)

      → Reply
»
16 months ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

This problem is a kind of knapsack problem with restoring the path from the end..

Let maxValue maximum b[i] , b[i] <= maxValue

My solution with DP.

Time complexity will be O(n * x * maxValue) .

Let : N <= 100 , maxValue <= 100 , x <= 10000

bool dp[N][maxValue * N] ;

Our DP state will be dp[i][sum] ;

Initially dp[0][0] = 1 , because to get sum 0 is always available.

dp[i][sum] -> means Can we get prefixSum j on prefix I ?

Transitions: dp[i][sum] |= dp[i — 1][sum — (j & a[i])] ; Here j means the value we can put as a b[i]

Code

if (dp[n][x] == 0) then answer = -1 ;

else you can restore the dp path from end , and you can add j value to array b .

SORRY FOR BAD ENGLISH

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, haven't thought about it much but this should probably work.

In the optimal answer, all $$$B[i]$$$s are sub-masks of their $$$A[i]$$$s.(If they aren't, the sum won't change by setting the extra '1' bits to '0's leading to a better answer and hence, a contradiction) Store the bits in a frequency array for all $$$A[i]$$$. If they can't make $$$X$$$, then impossible. Else: Assign each $$$b[i]$$$ greedily from the first to last(to get lexicographical smallest). For each $$$b[i]$$$, set the bits greedily from HSB to LSB. Basically, check if it is still possible to get $$$X$$$ with the remaining bits assuming the current bit is set to $$$0$$$, if not, then it must be set to $$$1$$$ and remove that from $$$X$$$. Checking if a frequency array of $$$log(X)$$$ bits can make $$$X$$$ is easy to do in $$$O(log(X))$$$ by checking from LSB to HSB and transferring bits to higher bit $$$(2^a = 2^{a-1} * 2)$$$ depending on if current bit in $$$X$$$ is $$$0/1$$$.

Complexity: $$$O(Nlog(X)^2)$$$. A $$$log(X)$$$ factor could probably be shaved off.

→ Reply