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.
Auto comment: topic has been updated by abhaypatil2000 (previous revision, new revision, compare).
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))$$$
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
https://ideone.com/BHM3vP
Here you can test both the codes https://mycode.prepbytes.com/problems/dynamic-programming/FRENEMY
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?
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.
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.
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.
Isn't the answer for the test case 6? (1,2),(2,1),(3,3) The code is giving output as 4.
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.
does prepbyte provide editorial also? I didn't find
Can you share job opening link?
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]?
The later