supersonic11's blog

By supersonic11, 2 months 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)

 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How did you solve the first problem?

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose in final answer, starting number is $$$A$$$, then last number must be $$$A+N-1$$$ where $$$N$$$ is length of input array. Then answer for it will be $$$N-L$$$, where $$$L$$$ is length of segment such that all elements in it are unique and are between A and A+N. It can be found using binary search on sorted array with unique elements. So like this you can do binary search over all elements and take minimum. Time complexity O(nlogn)

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Second question is related to binary search over rope size from 1 till maximum rope length.

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

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give one counter example ?

        • »
          »
          »
          »
          »
          2 months 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?

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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?

          • »
            »
            »
            »
            »
            »
            2 months 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.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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$$$

      • »
        »
        »
        »
        2 months 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.

      • »
        »
        »
        »
        2 months 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?

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it can be also solved by dp[N][M][K], since maximum number of cells covered would be around 105 (due to constraint on k) and each cell can have answer for 12 states.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please provide code for this ? I am not able to get how to handle cycle in this case also ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
uber Prob 1 sol.
uber prob2 sol.
»
2 months 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).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please take an example to illustrate your solution ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    seems interesting. Kind of hard to come up with counter-example, still trying. Can you justify your solution ?

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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) ).

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes. Nice, thanks!

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

        • »
          »
          »
          »
          »
          2 months 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
    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

»
2 months 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.

  • »
    »
    2 months 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$$$

  • »
    »
    2 months 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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    consider the case: A = [4,5,2,8,3,6,7,1] p=q=r=1. Now how can you get 15 which is equal to (8+7) after removing elements?