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

How Can a O(N^4) solution pass ?? This Solution Solution Gets 100 Points and apparently its a o(n^4) Solution , is this so or am I missing Something ??? And Can you please Explain me with the algorithm used in the Solution ?? Can you guys explain the solution in more detail , Lunchtime is for kids and apparently Some of them might need a little Help ?? answered 28 Jun '15, 19:52
what?? you're posting a solution to chefxr on the editorial to chefaor. Of course an O(N^4) solution will pass for chefxr. "Lunchtime is for kids" is probably the funniest thing I've heard in a while! :P
(28 Jun '15, 20:51)
By the way ,Alright My Fault I clicked on the wrong link (although I wonder how did I manage to stay here for hours..) , but Not my fault OR and XOR has a Nice suffix Match :P .... And yes I AM A KID
(28 Jun '15, 21:06)

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 !!