WOWR4 - Editorial (2021 Headlines)

editorial
, , ,
1

PROBLEM LINK

Practice
Contest
Setter: Adithi Narayan
Editorialist: Adithi Narayan

DIFFICULTY

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

Naive Approach [Subtask -1]:

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
  3. It is just discarded

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)

Code Snippet for Subtask 1 
def maxSum(A, B, v, i, n) :
	if (i == n) :
		if (A == B) :
			return A
		else :
			return 0
	# Discarding the current element
	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
  3. It is just discarded

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[0][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]]);
			// Discarding ith batch
			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
2

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]]         );

// Discarding ith batch

if ( dp[i - 1][j] != INT_MIN )

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