Bronze - Apple Division

Problems and Contests
#1

Complete Search with Recursion · USACO Guide

Hey, I know this is a stupid question. I’m confused on how we’re generating all the possible divisions of elements into two subsets.

Any help would be appreciated.

#2 
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	long long n; cin >> n;
	vector<long long> a;
	long long tot = 0;
	for(int i = 0; i < n; i++){
		long long k; cin >> k;
		tot += k;
		a.push_back(k);
	}
	long long ans = tot;
	for(int i = 0; i < (1<<n); i++){
		long long t = 0;
		for(int j = 0; j < n; j++){
			if(i & (1 << j)){
				t += a[j];	
			}
		}
		ans = min(ans, abs(t - (tot - t)));
	}
	cout << ans << "\n";
}

What I did was to use bitmasking to generate all subsets because 2^20 is feasible, so an O(2^N) algorithm works. For any generated subset, the other subset would simply be the sum of all elements minus the generated subset. Taking the min of the difference between the two would produce our desired result. Technically, this algorithm could be improved to be O(2^N/2), but it isn’t required.

1 Like
#3

Implement the recursive calls yourself on paper. Try to do what the computer is doing, but on paper. I had a decent amount of struggle with recursion when I was in bronze.

2 Likes
#4

I did exactly this for this problem and the permutations problem. It made it so much easier to understand.

2 Likes