Source : Uber offcampus 2021
I am not able to solve 4th problem of coding round and need help to upsolve it. I put problem statement here also :
Given an array A consisting of N elements, you need to perform the following operations: – remove p elements from the array – remove q groups of consecutive elements of size 2 – remove r groups of consecutive elements of size 3 After performing the operations, the left and right array formed are merged. Output the maximum possible sum after performing the operations.
Constraint: 1 <= N <= 1e5, 1 <= p+2*q+3*r <= N
Example:
Input:
7 1 1 1 //N p q r
4 5 2 1 3 6 7
Output: 7
Explanation: For p=1, you can remove 1 from the array -> [4,5,2,3,6,7]
For q=1, you can remove 2 and 3 which is group of consecutive elements of size 2 -> [4,5,6,7]
For r=1, you can remove 4,5 and 6 which is group of consecutive elements of size 3 -> [7].The maximum possible sum of array equals to 7. (Note: There are other ways to remove elements which will give the same result)
How did you solve the first problem?
Sort the array and for each i maintain a window such that all the elements in that window should be less than (a[i]+n), so number of elements outside that window is the answer for that i. Now minimize ans for all i's.
Can you provide the first three questions too, it will be a big help
Mike_Mirzayanov_Is_Pussy is your solution for problem 3 takes O(4 ^ K) if not then how did you solve it?
UPD: 4 ^ K = 16777216 as max k is 12
we can slightly optimize it by observing that the robot can't go beyond a distance of k / 2 from (0,0) as he also has to return to the cell (0,0). I think this should work.
You can solve it by using BFS. Starting location will be (0,0). For each location you reach in queue, check if 2<=k, if yes then you can subtract 2 from k.
I Don't think this will work, as the robot can clean cells while returning to (0,0)
Can you give one counter example ?
Consider all the cells needs to be cleaned how your bfs is going to work?
It has to return to (0,0) even it keeps moving in one direction. And number of times it will move = 2*number of new cells visited.
Note that example given in GFG, using queue the path will be (0,0)->(0,1)->(0,2)->(0,1)->(0,0)->(1,0)->(0,0). Note that here it visited (0,0) 2 times but still only took 6 moves. If you still didn't get something I can try to elaborate more.
For n,m = 4,4 and k == 12, no obstacles. Answer is 12. How bfs would solve it?
agarus and kunal_rai, thanks for counter example. When it's forming cycle then it's not working. While solving I didn't thought of cycle. Sorry.
Notice that you can get max at (k//2) = 6 steps away, so you can visit no more then trangle (0,0)->(0,7)->(7,0) that is 7*8//2 = 28 cells. You can do dfs from (0, 0) and achieve no more that 4K possible paths and code them as bitmasks of those cell out of 28 that you visited. Then make 28 groups based on cell number where path ends. For every group you could find two that give best bitwise-OR result. And choose best among them.
But I think even traversing from every cell reached, back to (0, 0) could pass. Especially with some heuristics, like: back-path should be lower-or-equal to the forward path that is being considered. 4K*4K doesn't seam a lot.
Hey, can you explain how is the total number of paths $$$4k$$$ ??
Moreover, I was thinking of a DP solution. Let's initially assume that two robots start simultaneously from $$$(0,0)$$$ and reach positions $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$, taking $$$k_1$$$ and $$$k_2$$$ steps, respectively. That is, let $$$dp[x_1][y_1][x_2][y_2][k_1][k_2]$$$ be max floors cleaned with first robot reaching $$$(x_1,y_1)$$$ using $$$k_1$$$ steps and second robot reaching $$$(x_2,y_2)$$$ using $$$k_2$$$ steps. If they cross over some point we will count it only once.
This problem is analogous to the given problem as while calculating the final answer, we will consider the ending point of the first robot and that of the second robot to be the same. That is, you can safely assume that the first robot moves from $$$(0,0)$$$ -> $$$(x_1,y_1)$$$, and the same robot moves from $$$(x_1,y_1)$$$ -> $$$(0,0)$$$ That is, answer would be max of $$$dp[i][j][i][j][k_1][k_2]$$$ for $$$0 \leq i \leq 7$$$, $$$0 \leq j \leq 7$$$ and $$$\forall k_1,k_2$$$ such that $$$k_1 + k_2 \leq K$$$
You can relate the transitions and the logic with the Cherry-Pickup problem.
Time complexity would be something like $$$7^4 \times 12 \times 12 \times 4 \times 4 \approx 5.5e6$$$
4k == 4^steps, where steps = 6. You can't go more then 6 steps if you need to return in 12. To be more precise — this would mean that there up to 4K-1 path of length less then 6 too, but 4K is the rough upper bound since first move have only 2-direction, 2nd 3-directions it will be less then 2*3*(~4^4) < 2K, so number of all the paths with steps <= 6 is < 4K.
Hey will k1 be always equal to k2 because both robots are moving simultaneously?
This will not work as in the problem you mentioned it is allowed to move in only 2 directions left up or right down, but in this problem, it is allowed to move in all 4 direction, you will eventually run in infinite dp call.
It looks kind of backward-greedy: if you imaging all deleted cells in the end (after 3 operations), the segments that where deleted after all delete/merge will form corresponding summary lengths segments. And there really would be no difference in what faze you'd delete them. So we can put all possible triplets sums in priority queue paired with their index; get lowest of those from PQ and do the same with 2-segments, and easiest 1-segment. But there is one problem — how should we deal with triplet (pairs) that intersect? For this, we have a tree-map of numbers 1 to N. Every time we get triplet from PQ we check if there still same 3 numbers behind that index. If so we just delete those 3 indexes from tree-map and decrease our ans by their sum. If no — we recalculate triplet and put it back to PQ.
Since recalculation is needed at most 2 times for every deletion and its only 3 elements to add (thought log(n) time to get it), we can estimate complexity as O(NlogN).
Not sure if I understood you correctly, but what would your algorithm do in the following case: $$$A = [0, 5, 20, 4], p = q = 1, r = 0$$$? It seems that you would first remove the $$$0$$$ because it is the lowest, and then the pair $$$20, 4$$$. But it would be optimal to remove $$$0, 5$$$ and $$$4$$$.
By the way, I don't know how to solve the problem either.
We are doing it backwards: first choose to delete r cheapest triplets (none: r = 0), then q cheapest pairs (q=1: (0,5) ); then p cheapest ones (p=1: (4) ).
Then how about $$$A = [0, 3, 2, 2], p = q = 1, r = 0$$$ (one pair and one singleton, no triplets)? Greedy takes $$$0, 3$$$ as the cheapest pair, and then one of the remaining $$$2$$$-s as the singleton. But it would be optimal to take $$$0$$$ as the singleton and $$$2, 2$$$ as the pair.
Yes. Nice, thanks!
Hm... Now lets think how that happened... :)
This happens based on ordering of this 3 operations. But even if we check all six possible ordering there can be ambiguaties that will result in wrong answer.
By the way, I don't know how to solve the problem either.Okay, then I can stop regretting not being able to solve this problem.
Were you in the contest/interview/whatever this was? I was wondering if the GeeksForGeeks blog author left something out or misunderstood the problem.
No, I was not.
Take the sum of maximum n-p-2*-3*r elements. There is always a way to have them.
How is your solution working for the following test case: $$$\newline$$$ $$$p = 0$$$, $$$q = 0$$$, $$$r = 1$$$, $$$n = 5$$$ $$$\newline$$$ $$$Array = [0, 0, 7, 4, 4]$$$. $$$\newline$$$ Answer should be $$$8$$$
Nope, try this array for p=0 q=1 r=0 1 2 1
Hey, Can we sort the array first. Then we can remove the first 6 elements(p+q+r). THe remaining elemetns sum will be the maximum sum??
You can't sort the array. If I'm not wrong, the order matters!
Cool handle.