PROBLEM LINK:

Practice
Contest

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

AUTHOR'S AND TESTER'S SOLUTIONS:

Tester1
Tester2