PROBLEM LINK:Author: Roman Furko 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 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 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:
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:
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 top-down approach).I could pass first sub-task only.Can someone figure out what optimization i have to do to my code to pass other sub-tasks.I think I have taken care of trick mention in editorial.Plz help !!