CHEFAOR -- Editorial
#PROBLEM LINK:
[Practice][222]
[Contest][111]
**Author:** [Roman Furko][3333]
**Testers:** [Pushkar Mishra][4444] and [Sergey Kulik][7777]
**Editorialist:** [Pavel Kacprzak][6666]
**Russian Translator:** [Sergey Kulik][7777]
**Mandarian Translator:** [Gedi Zheng][8888]
#DIFFICULTY:
Easy-Medium
#PREREQUISITES:
DP, Bitwise Operations
#PROBLEM:
Given an array $A$ of $N$ integers ranging from $0$ to $2^30$, partition this array into $K$ sub-arrays such that the sum of Bitwise OR of these sub-arrays is maximised.
#Naive Approach
The simplest approach is to try out all possible partitions using recursion and take the maximum. This approach will try out at least ${N \choose K-1}$ possibilities. It is clearly inefficient and will time-out for all sub-tasks.
#An $\mathcal{O}(N^2K)$ solution:
We can use Dynamic Programming. Let us maintain an array $DP[][]$ in which $DP[i][j]$ stores the maximum sum that you can get by partitioning the segment $1 \dots i$ into $j$ sub-segments. As is evident, this is an optimal overlapping sub-structure of the main problem.
To calculate $DP[i][j]$, we can iterate from $p = i-1 \dots 1$ and use the relation:
$DP[i][j] = max(DP[i][j], DP[p][j-1] + BitwiseOR(A[p+1], A[p+2], \dots, A[i]))$.
Since $N, K \geq 1000$, this algorithm will time out for the last two sub-tasks.
#Optimising the DP to $\mathcal{O}(NK\log(A_{max}))$ :
We make two observations:
- $DP[p][j] \leq DP[i][j]$ for $p \leq i$. This isn't tough to see since Bitwise OR operation of two numbers never results in a number smaller than either of the two.
- Let us consider an array $C$ where $BitwiseOR(A[1], A[2], $BitwiseOR(A[i], A[j], \dots, A[i])$$. A[i])$. For $i > 30$, we claim that there are only $30$ distinct values in the array $C$. The reason is that cumulative Bitwise Or operation accumulates 1 bits. Since the maximum number of 1 bits can be $30$, thus there can only be $30$ distinct values in array $C$.
Now, using the two aforementioned observations, we can optimise our DP. While calculating $DP[i][1 \dots ]$, K]$, we were iterating from $p = 1 \dots i-1$ and checking $DP[p][1 \dots k]$. K]$. But we can now say that we only need to iterate from $1 \dots K$ for those $p$ such that where $BitwiseOR(A[p], A[p+1], \dots, A[i])$ and $BitwiseOR(A[p+1], A[p+2], \dots, A[i])$ are different. Since, there can at max be $30$ such $p$, therefore, the net complexity comes down to $\mathcal{O}(NK\log(A_{max}))$. This will easily pass under $10$ seconds.
#AUTHOR'S AND TESTER'S SOLUTIONS:
[Author's solution][55]
[Tester's solution][66]
[1]: http://www.codechef.com/users/dpraveen
[111]: http://www.codechef.com/LTIME25/problems/CHEFAOR
[222]: http://www.codechef.com/problems/CHEFAOR
[3333]: http://www.codechef.com/users/furko
[4444]: http://www.codechef.com/users/pushkarmishra
[6666]: http://www.codechef.com/users/pkacprzak
[7777]: http://www.codechef.com/users/xcwgf666
[8888]: http://www.codechef.com/users/stzgd
[55]: http://www.codechef.com/download/Solutions/JUNE15/setter/CHEFAOR.cpp
[66]: http://www.codechef.com/download/Solutions/JUNE15/tester/CHEFAOR.cpp