Mike_Mirzayanov_Is_Pussy's blog

By Mike_Mirzayanov_Is_Pussy, 3 years ago, In English

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)

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How did you solve the first problem?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the first three questions too, it will be a big help

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I Don't think this will work, as the robot can clean cells while returning to (0,0)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give one counter example ?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Consider all the cells needs to be cleaned how your bfs is going to work?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        as the robot can clean cells while returning to (0,0)

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For n,m = 4,4 and k == 12, no obstacles. Answer is 12. How bfs would solve it?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like 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.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey will k1 be always equal to k2 because both robots are moving simultaneously?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
3 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

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).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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) ).

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes. Nice, thanks!

          Hm... Now lets think how that happened... :)

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          example
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        Were you in the contest/interview/whatever this was? I was wondering if the GeeksForGeeks blog author left something out or misunderstood the problem.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Take the sum of maximum n-p-2*-3*r elements. There is always a way to have them.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope, try this array for p=0 q=1 r=0 1 2 1

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can't sort the array. If I'm not wrong, the order matters!

»
2 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Cool handle.