| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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)
Auto comment: topic has been updated by gorssorser (previous revision, new revision, compare).
it is too bad to see people down voting for no reason
it is too bad to see people downvoting for no reason
Partition problem
I know this sir, but is there any solution to this particular problem, in some polynomial time n^2 or something
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.
thanks for insights