# WOWR4 - Editorial (2021 Headlines)

Practice
Contest

Easy

## PREREQUISITES

Dynamic Programming

## PROBLEM

The cure for the zombie infection is available as N batches and each batch contains Ai vials.
You have to split the N batches into 2 equal shares, such that each superpower gets an equal number of vials of cures without splitting any batch. You may even choose to discard some batches to ensure equal shares.
Find the maximum number of vials that each nation can get

## EXPLANATION

Brute force recursive strategy can solve this problem easily.
Each batch has 3 possibilities:

1. It can go to superpower A
2. It can go to superpower B

We have to recur for all three scenarios and get the maximum possible solution
Let A,B be the sum of cures for superpower A and B, v be the array containing batches of vials of length n and i be the index of the current element we are dealing with.
Complexity: O(3N)

``````def maxSum(A, B, v, i, n) :
if (i == n) :
if (A == B) :
return A
else :
return 0
val = maxSum(A, B, v, i + 1, n)
# Element is taken with superpower A
val = max(val, maxSum(A + v[i], B, v, i + 1, n))
# Element is taken with superpower B
val = max(val, maxSum(A, B + v[i], v, i + 1, n))
return val
``````

### Optimized Approach [Subtask - 2]

We can optimize our solution with dynamic programming.
Let us consider, A as sum of cures for superpower A, B as sum of cures for superpower B, SUM as the total sum of cures, dp[i][j] as the maximum A considering the first i batches such that
A - B = SUM - j
So, dp[n][SUM] will give us our answer.

We might find cases where A-B is negative, so A-B lies in the rage [-SUM, SUM], the extremes occurring when one superpower has all the cure and the other has none. So, our j [SUM - (A-B)] will range from [0, 2*SUM]

Now, we have to loop through all the batches and all the possible j values, finding the maximum A. We have the same 3 cases for each batch discussed in the recursion section:

1. It can go to superpower A
2. It can go to superpower B

The time complexity will be O(N*SUM)

Setter's solution
``````#include<bits/stdc++.h>
using namespace std;

// Function to find the maximum subset sum
int maxSum(int v[], int n)
{
// sum of all vials
int sum = 0;
for (int i = 0; i < n; i++)
sum += v[i];

int limit = 2 * sum + 1;
int dp[n + 1][limit];

// initialise dp table with INT_MIN for no solution
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < limit; j++)
dp[i][j] = INT_MIN;
}
dp[sum] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < limit; j++) {
// Putting ith batch in A
if ((j - v[i - 1]) >= 0 && dp[i - 1][j - v[i - 1]] != INT_MIN)
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + v[i - 1]);
// Putting ith batch in B
if ((j + v[i - 1]) < limit && dp[i - 1][j + v[i - 1]] != INT_MIN)
dp[i][j] = max(dp[i][j], dp[i - 1][j + v[i - 1]]);
if (dp[i - 1][j] != INT_MIN)
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
return dp[n][sum];
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t,n,i;
cin>>t;
while(t--){
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin >> a[i];
cout << maxSum(a,n)<<endl;
}
return 0;
}
``````
1 Like

there is something wrong with the editorial solution(thought i.e. giving AC)
Instead consider below piece of code (probably it will also yield AC)

``````// Putting ith batch in A

if ( (j + v[i - 1]) < limit && dp[i - 1][j + v[i - 1]] != INT_MIN )

dp[i][j] = max(     dp[i][j], dp[i - 1][j + v[i - 1]] + v[i - 1]    );

// Putting ith batch in B

if ( (j - v[i - 1]) >= 0 && dp[i - 1][j - v[i - 1]] != INT_MIN )

dp[i][j] = max(   dp[i][j], dp[i - 1][j - v[i - 1]]         );