<h1>Question</h1> ↵
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 ↵
↵
↵
<br>↵
↵
↵
<h1>My Approach</h1> ↵
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.
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 ↵
↵
↵
<br>↵
↵
↵
<h1>My Approach</h1> ↵
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.
