abhaypatil2000's blog

Adobe emerge 2021 test question
By abhaypatil2000, history, 3 years ago, In English

Question

This question has been asked by adobe.

There are N number of production facilities. Each of which can produce either vaccine or an antibiotic. The ith facility can produce G[i] number of vaccines, or S[i] number of antibiotics per day.

You have a choice to decide which facility will produce which item.

You are given the task to find the number of unique ways to choose a contiguous range of production facilities, from L to R (1 <= L <= R <= N), such that the following conditions are satisfied.
1. You need to set the production units such that, each facility produces either vaccine or antibiotic.
2. The number of vaccines produced should be equal to the number of antibiotics produced.

Any two ways of production are considered different if:
1. L or R or both are different.
2. If L and R are the same, then there exists at least one facility which is producing a different item in both the ways.

Return answer module 10^9 + 7.

Constraints:
1. 1 <= N <= 10^3
2. 1 <= G[i] <= 10^4
3. 1 <= S[i] <= 10^4
4. Sum of all G[i] is <= 10^4
5. Sum of all S[i] is <= 10^4


My Approach

We could count each vaccine as a +1 and each antibiotic as a -1. Hence the question would be to find the ways to make a sum = 0 between any two indices. But I am able to find an O(n^4) solution (using subset-sum for each n^2 index pair), and with some thinking, I might get it down to O(n^3). But that's my best.

But I believe (by looking at the constraints) that the question demands some O(n^2) solution or O(n * sum(G[i], S[i]).

O(n^3) -> start from index i to n-1, and build the subset sum set, and find the ways to reach 0 at each instance. This can get it down to O(n^2*sum). But not O(n^2) or O(n*sum)

But I am unable to get to the solution. Please help.

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

Comments Comments (12)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by abhaypatil2000 (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think Divide & Conquer DP might work were. My idea is let's say we have to solve for an interval $$$[0, n - 1]$$$ where $$$ 0 <= l < r <= n - 1 $$$ now we take $$$mid = {(l + r) / 2} $$$ and solve the same problem for $$$[0, mid]$$$ and $$$[mid + 1, r]$$$. Now we only need to add the number of ways in which $$$l <= mid$$$ and $$$r > mid $$$. We can do this by creating suffix knapsack for $$$[0, mid]$$$ and a prefix knapsack for $$$[mid + 1, r]$$$. We can evaluate number of such ways in $$$O(sumRange)$$$ and $$$O(n * sumRange)$$$ for knapsack. This will be done at most $$$log(n)$$$ times.

The time complexity will be: $$$O(n * sumRange * log(n))$$$

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

There are two methods to solve this one is kind of prefix sum and another is just use divide and conquer as explained by darklight13

O(N*S) solution
Divide and conquer solution O(N*S*log(N))

Here you can test both the codes https://mycode.prepbytes.com/problems/dynamic-programming/FRENEMY

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

    can you please explain what have you done in the first method, according to me, you are calculating knapsack dp normally and adding to answer if you get sum 0 (equivalently number of ways to get sum 0 in an array), How is this associating the number of ways with l and r, i.e the bounds?

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

      I think his dp(i,j) represents No. of Subarrays staring at i having balance = j. Therefore dp[(i,j) = dp(i+1,j+arr[i].first) + dp(i+1,j-arr[i].second) and balance = 0 is an edge case because for the subarray at (i-1) there are 2 Cases : => Merge with the subarray at i. => Start a fresh subarray.

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

        sure,its starting at index i but the ending point is always n-1, that's what I am saying, lets say we have a range l to r, there are x ways to get sum 0, then we should add x*(l)*(n-r+1) to answer not only x, that's what my confusion is, this is taken care by the second approach, but I am not finding that in 1st approach.

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

          No, the Ending Point of Subarray starting at i is not always n-1.
          Carefully observe that for (i+1)th we are by default incrementing dp[i+1][0] by 1. So, it will take care of the cases where we are ending our subarray at the ith position. And in the end, we are subtracting n from the answer because we have unnecessary included 1 to the answer by each dp[i+1][0].
          This way we are making sure that we are not only considering all the starting points(L) but also all the ending points (R).
          If you dry run for n=3 for [ (1,2) (2,1) (3,3) ] you will get to know.

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

            Isn't the answer for the test case 6? (1,2),(2,1),(3,3) The code is giving output as 4.

            1 to 2 -> 2 ways (+1,-1),(-2,+2)
1 to 3 -> 4 ways (+1,-1),(-2,+2),(+1,+2,-3),(-1,-2,+3)
2 to 3 -> 0 ways

            making a total of 6 ways.

            UPD: Sorry I completely misunderstood the question, this essentially is number of ways to select subarrays with sum=0, I thought something else.

            → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it
    sub

    does prepbyte provide editorial also? I didn't find

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

Can you share job opening link?

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

abhaypatil2000 "You have a choice to decide which facility will produce which item."

do we have a choice to decide the amount too, or we have to produce complete of S[i]/G[i]?

→ Reply