You are given an array of size n and an integer k, you have to partition the array into k contiguous subarrays such that the sum of bitwise OR of all the subarrays is maximised. Each element should belong to a partition.
eg -> A = [1, 2, 3, 4], k = 2 1st way: [1], [2, 3, 4] -> (1) + (2 | 3 | 4) = 8 2nd way: [1, 2], [3, 4] -> (1 | 2) + (3 | 4) = 10 3rd way: [1, 2, 3], [4] -> (1 | 2 | 3) + 4 = 7 Hence, the answer is 10.
N = 10^3
This question came up in Trilogy Innovations OA round, Well, I arrived to a simple DP solution that was O(n^3), How can this be optimised further?
I covered this in my live stream.
Still I will explain the solution here.
You can use a 2d dp to solve this in $$$O(n*n*log(max(a_{i})))$$$
this can be calculated using,
where $$$x$$$ is the index of closest position for every bit from $$$0$$$ to $$$log(max(a_{i}))$$$ where it is set.
Suppose $$$dp[i][j]$$$ gives the maximum value if we partition first $$$i$$$ elements into $$$j$$$ contiguous subarrays.
Now it's easy to see that $$$dp[l][x] \leq dp[r][x](l \leq r)$$$
Here's one important observation — if $$$check[l][r]=a_l | a_{l+1} | \dots a_r$$$, for any index $$$j$$$ there are atmost $$$log(MAX)$$$ indices $$$j$$$ such that $$$check[i][j] != check[i+1][j] (1 \leq i \leq j \leq n)$$$.
So instead of considering $$$i$$$ choices for leftmost endpoint for subarray $$$a[l,i]$$$, you have to consider only $$$log(MAX)$$$ indices.
Now you can solve this problem in $$$O(n^2 \cdot log(MAX))$$$
Did you solve problem D?
We can represent $$$f(x)$$$ as
$$$f(x)=k \cdot (x-1) \cdot (x-2) \cdot (x-3) \dots (x-a) + 1$$$
Now you know that value of $$$f(a+b)$$$.
So you can put $$$x=a+b$$$ and get the value of $$$k$$$.
You have whole polynomial with you now. So you can easiy find $$$f(c)$$$.
Ahhh so simple. I was trying to find coefficients for every $$$x^i$$$.
CHEFAOR.