Adobe Emerge Test 2021

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.

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 formatn (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),

1 Like

Do you have sample test cases ? I think it’s 0-1 knapsack DP.

I have added the sample test cases. Check them out.

If you have solved please share the solution.

I tried once but failed

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

const int MOD = 1e9 + 7;
const int maxn = 1e3 + 5, maxsum = 1e4 + 5, base = 1e4;
int n;
long long dp[maxn][maxsum + base];
pair<int, int> arr[maxn];

long long int helper(int in, long long sum) {
if(in == n) {
return sum == base;
}
if(dp[in][sum] != -1)
return dp[in][sum];
long long ans = sum == base;
(ans += helper(in + 1, sum + arr[in].ff)) %= MOD;
(ans += helper(in + 1, sum - arr[in].ss)) %= MOD;

return dp[in][sum] = ans;

}

int main() {
cin >> n;

for(int i = 0; i < n; i++) {
    cin >> arr[i].ff;
}
for(int i = 0; i < n; i++) {
    cin >> arr[i].ss;
}
memset(dp, -1, sizeof(dp));
long long int ans = 0;
for(int i = 0; i < n; i++) {
    (ans += helper(i, base) - 1) %= MOD;
}

cout << ans << endl;

}

1 Like

Overall time complexity for my solution is O(n * max(sum(s[i] ) , sum(g[i]))

void solve(){
    const int mod = 1e9 + 7;
    int n , s1 = 0 , s2 = 0; 
    cin >> n;
    vector<int> g(n) , s(n);
    for(auto &i: g) cin >> i , s1 += i;
    for(auto &i: s) cin >> i , s2 += i;
    int base = max(s1 , s2);       
    vector<vector<int>> dp(n , vector<int>(2 * base + 1 , -1)); 
    function<int(int,int)> f = [&](int i,int sum){
        if(i == n){
            return 1 * (sum == 0);
        }
        else if(dp[i][base + sum] != -1) return dp[i][base + sum];
        int ans = (sum==0);
        ans += f(i + 1 , sum + s[i]);
        ans += f(i + 1 , sum - g[i]);
        ans %= mod;
        return dp[i][base + sum] = ans;
    };
    int ans = 0;
    for(int i=0;i<n;i++){
        ans = (ans + (f(i + 1 , s[i]) + f(i + 1 , -g[i])) % mod) % mod;
    }
    cout << ans;
    return;
}
3 Likes

Bro, please explain your logic. it will be help full.

1 Like

Hey please explain your logic, it would be extremely helpful.

I got it nice solution.

we need to find number of way to choose l , r such that

sum(s[]) = sum(g[])

which is also equal to

sum(s[]) - sum(g[]) = 0

it means that, if i choose s[i] then i will add it to my sum variable and if i choose g[i] then i will subtract it from my sum variable, at any position if my sum is zero it means that i have already chosen elements such that the above constraints satisfy , in that case, i will simply increment my ans and continue choosing. i == n will be the base case.

so my recurrence relation is, f ( i , sum ) where i denotes the index till which i have chosen some contiguous subarray such that summation of s[i] / -g[i] is sum.

Pardon me for my bad english.

1 Like

basically, f(i, sum) returns the number of ways, starting from index i, with curr_sum = sum, we will be able to get a sum = 0, using future s[i] and -g[i];

Thanks for the reply, actually I was pretty close to this. I was just missing the +1 you added in the recursive function calls, when the sum == 0.

Exactly !!!