gorssorser's blog

[Help needed please] either solve this interesting problem or prove it is NP-Hard??
By gorssorser, history, 10 months ago, In English

you are given an Array A with N numbers, you will be dividing the array in two sets, such that if A[i] can only belong either to set 1 or set 2, you will take get a number x by taking or of all elements of set 1 and similarly a number y from set 2, you have to find the maximum value of X & Y.

(well i am not able to do either cause it is created by me only)

  • Vote: I like it
  • -31
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it -17 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it -55 Vote: I do not like it

it is too bad to see people down voting for no reason

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it -47 Vote: I do not like it

it is too bad to see people downvoting for no reason

→ Reply
»
10 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Partition problem

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I know this sir, but is there any solution to this particular problem, in some polynomial time n^2 or something

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

Well, I've got some observations so I'm sure the problem is solvable to some extent!

1) The number of elements in the smaller set will never have to be more than $$$log(maxa[i])$$$, just don't pick the elements that don't increase the OR of the set, there can only be $$$log$$$ of those that do. This already gives a whopping $$$O {n \choose log(maxa[i])}$$$ solution.

2) You can construct the answer greedily, starting from the highest bit, just check if you can add it to the answer, and if you can, do it. The question is of course how to check if such AND is achievable, and maybe that can be done with something like matchings?

3) If you have a pair of elements, one of which is the submask of another, then by putting them into different sets, you are guaranteed to have the submask in the answer.

4) I feel like this problem would be approximated well using simulated annealing, because of the fact 1.

→ Reply