Блог пользователя gorssorser

[Help needed please] either solve this interesting problem or prove it is NP-Hard??
Автор gorssorser, история, 10 месяцев назад, По-английски

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)

  • Проголосовать: нравится
  • -31
  • Проголосовать: не нравится

»
10 месяцев назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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

→ Ответить
»
10 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -55 Проголосовать: не нравится

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

→ Ответить
»
10 месяцев назад, # |
← Rev. 3   Проголосовать: нравится -47 Проголосовать: не нравится

it is too bad to see people downvoting for no reason

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

Partition problem

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить