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.
- You need to set the production units such that, each facility produces either vaccine or antibiotic.
- The number of vaccines produced should be equal to the number of antibiotics produced.
Any two ways of production are considered different if:
- L or R or both are different.
- 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 <= N <= 10^3
- 1 <= G[i] <= 10^4
- 1 <= S[i] <= 10^4
- Sum of all G[i] is <= 10^4
- 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.
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 believe (by looking at the constraints) that the question demands some O(n^2) solution or O(n * sum(G[i], S[i]).
But I am unable to get to the solution. Please help.
Sample test cases:
Input format → n (the number of facilities), next n integers giving the values of G, next n integers giving the values of S.
Input:
3
1 2 1
2 1 2
Output:
4
Explanation:
(1g, 2s), (1s, 2g), (2s, 3g), (2g, 3s) → first comes index, then whether it produces g or s.
Input:
4
1 1 1 1
1 1 1 1
Output:
12
Explanation:
(1g, 2s), (1s, 2g), (2g, 3s), (2s, 3g), (3g, 4s), (3s, 4g), (1g, 2g, 3s, 4s), (1g, 2s, 3g, 4s), (1g, 2s, 3s, 4g), (1s, 2g, 3g, 4s), (1s, 2g, 3s, 4g), (1s, 2s, 3g, 4g),
Input:
4
1 2 3 4
4 3 2 1
Output:
8
Explanation:
(2g, 3s), (2s, 3g), (1s, 2g, 3g, 4s), (1g, 2g, 3s, 4s), (1g, 2s, 3g, 4s), (1g, 2s, 3s, 4g), (1s, 2s, 3g, 4g), (1s, 2g, 3s, 4g),