PROBLEM LINK:
Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak and Pushkar Mishra
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
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 consecutive sub-arrays such that the sum of Bitwise ORs of these sub-arrays is maximized.
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 a 2-D 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. Evidently, 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 difficult to infer since Bitwise OR operation on two numbers never results in a number smaller than either of the two.
- Let us consider an array C where C[i] = BitwiseOR(A[1], A[2], \dots, 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 in the values stored in array C can be 30, thus there can only be 30 distinct values in array C.
Now, using the two aforementioned observations, we can optimize 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]. But we can now say that we only need to iterate from 1 \dots K for those p 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 finish in under 10 seconds.
An \mathcal{O}(NK) solution :
The \mathcal{O}(N^2K) DP solution can directly be optimised to \mathcal{O}(NK) DP using a widely known optimisation method called “Knuth Optimisation”. Though this was not required to solve the problem for 100 points, we suggest that you go through the concept:
Quora
Codeforces
. Morover use memset over simple loop to fasten up your code!!