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.