Hi, I've encountered this problem in a contest which is already over, so I'd like to share it and see if you have any solution. I've been trying for about a week and still haven't found any good dp or backtracking solution.
Given array $$$a$$$ of $$$n$$$ integers, divide it into $$$m$$$ non-empty subarray so that bitwise and of sums of subarrays is maximal. Print maximal and.
$$$1 \leq n, m \leq 50$$$ $$$1 \leq a_i \leq 2^{50}$$$
Time limit is 0.4 sec
Auto comment: topic has been updated by Vovkaez (previous revision, new revision, compare).
Auto comment: topic has been updated by Vovkaez (previous revision, new revision, compare).
Searching the web for a copy-pasted part of your problem statement led me quickly to someone else asking about essentially the same problem 17 months ago, with some (quite explicit) solution ideas available.
The basic idea is that each bit in the answer can be calculated using a simple pathfinding or DP routine if you know all of the answer's more significant bits. For example, suppose you know that the answer is less than $$$2^7$$$. Then, if there is any partition achieves a bitwise-and of at least $$$2^6$$$ if and only if same partition uses only subarrays that have the $$$2^6$$$ bit in their sums set. Suppose you find such a partition and discover that the answer is between $$$2^6$$$ and $$$2^6 + 2^6 - 1$$$: you can then search for partitions using only subarrays with both the $$$2^6$$$ and $$$2^5$$$ bits of their sums set to see whether the answer is above or below $$$2^6 + 2^5$$$, and so on.
Thank you
It is always optimal to have the most significant bit of answer set to $$$1$$$. We can construct the answer $$$X$$$ in binary bit by bit. Iterate on $$$k$$$ from $$$55$$$ down to $$$0$$$ and try to turn on the $$$k$$$-th bit of $$$X$$$. Then you can do a simple $$$O(N^3)$$$ DP to check if it is actually possible to have the answer match till the $$$k$$$-th bit of of $$$X$$$. If yes, then keep $$$X$$$ as is and continue; otherwise turn off the $$$k$$$-th bit of $$$X$$$ again.
981D - Bookshelves