PROBLEM LINK:Author: Roman Furko DIFFICULTY:EasyMedium PREREQUISITES:DP, Bitwise Operations PROBLEM:Given an array $A$ of $N$ integers ranging from $0$ to $2^{30}$, partition this array into $K$ consecutive subarrays such that the sum of Bitwise ORs of these subarrays is maximized. Naive ApproachThe simplest approach is to try out all possible partitions using recursion and take the maximum. This approach will try out at least ${N \choose K1}$ possibilities. It is clearly inefficient and will timeout for all subtasks. An $\mathcal{O}(N^2K)$ solution:We can use Dynamic Programming. Let us maintain a 2D array $DP[][]$ in which $DP[i][j]$ stores the maximum sum that you can get by partitioning the segment $1 \dots i$ into $j$ subsegments. Evidently, this is an optimal overlapping substructure of the main problem. To calculate $DP[i][j]$, we can iterate from $p = i1 \dots 1$ and use the relation: $DP[i][j] = max(DP[i][j], DP[p][j1] + BitwiseOR(A[p+1], A[p+2], \dots, A[i]))$. Since $N, K \geq 1000$, this algorithm will time out for the last two subtasks. Optimising the DP to $\mathcal{O}(NK\log(A_{max}))$ :We make two observations:
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 i1$ 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:
This question is marked "community wiki".
asked 26 Jun '15, 12:32

Nice joke about "easily finish under 10 seconds". Here's author's code from editorial, submitted in practice: link answered 30 Jun '15, 06:01
On the testing server, all test files were passing under 8 seconds. Author's solution was only for first 2 subtasks. it was wrongly uploaded here. the correct solutions are up now. Try submitting tester2's solution.
(30 Jun '15, 08:53)
Tried tester1, it works 8.3 on maxtest. Far from TL*0.5 :) I agree that getting TL because of bad implementation why AC is possible is a contestant's fault, but that's definitely not "easily finish" :) Looking at other comments in this topic  I am not the only one who thinks this way. And what was the point about "try tester2's"? It is complitely different solution, based on Knuth optimization; it has nothing to do with NKlogA.
(30 Jun '15, 15:20)

Show us some solution please! answered 28 Jun '15, 16:42

can someone tell me if the Tester2 is based on knuth optimization? answered 04 Jul '15, 04:24

Why would you ever swap the order of [Author,Tester] => [Tester,Author]? answered 28 Jun '15, 23:30

http://www.codechef.com/viewplaintext/7298688
I coded the solution after going through editorial(but it is topdown approach).I could pass first subtask only.Can someone figure out what optimization i have to do to my code to pass other subtasks.I think I have taken care of trick mention in editorial.Plz help !!