Help regarding aAdobe emerge 2021 test question
Difference between en1 and en2, changed 207 character(s)
<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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English abhaypatil2000 2021-08-26 16:11:39 207 Tiny change: 'dex i to n - 1, and bui' -> 'dex i to n-1, and bui'
en1 English abhaypatil2000 2021-08-25 21:46:29 1778 Initial revision (published)