Hi,
I try a problem http://www.spoj.com/problems/SUBSET/ but it’s getting TLE. since n<=20 time complexity for generating subset is 2^n but we have to find subset of a subset that satisfy certain property making this complexity to 2^n * 2^n . How to solve???
Thanks
This problem would be a relatively straightforward case of dynamic programming if it weren’t for the very large limit on the amount of milk each cow produces. On the other hand, N is fairly small, so an exponential-time approach is likely to be feasible.
The obvious approach is to test every subset S in turn. If the sum of S is A, then try all subsets of S to see if one of them has a sum of A/2. Iterating over all subsets of all subsets takes 3^N steps, which is a little too large for the time available.
To reduce the time required, we can use a “meet-in-the-middle” approach. Split the cows evenly into two sets and paint one set brown and the other white. Suppose set S is balanced, and can be split into subsets A and B with the same sum. Then sum(brown in A) - sum(brown in B) = sum(white in B) - sum(white in A) i.e. the brown cows in S can be split into two sets and the white cows in S can also be split into two sets, where the degree of “unbalance” is the same. We can now try to reverse this process: for every subset of the brown cows, compute all the possible unbalance values and store them; similarly for the white cows. Then for each possible unbalance value, pair up all the brown subsets with that value with all the white subsets with that value to make balanced brown-and-white sets of cows.
What is the computational efficiency? The slow part is going to be the final matching. It’s not obvious how to obtain a tight bound, but an approximation is to note that there are O(3^(N/2)) ways to partition subsets of the brown cows, and in the worst case one of these partitions may be matched up with all subsets of the white cows, giving O(3^(N/2).2^(N/2)) = O(6^(N/2)) time, which is good enough.
Another optimization that can be made is when trying to match a brown subset with a white subset, one can choose the smaller of the two, iterate over every unbalance of that subset, and then look for that same unbalance in the other subset by doing a lookup into a hash table. This results in a faster but more complex to analyze runtime, which can be shown to be (1 + sqrt 1.5)^N, a bit better than (sqrt 6)^N.
Here is a code:
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
vector<pii> half(const vector<int> &S)
{
vector<pii> ans;
int N = S.size();
for (int i = 0; i < (1 << N); i++)
for (int j = i; ; j = (j - 1) & i)
{
int sum = 0;
for (int k = 0; k < N; k++)
{
if (j & (1 << k))
sum -= S[k];
else if (i & (1 << k))
sum += S[k];
}
if (sum >= 0)
ans.push_back(pii(sum, i));
if (j == 0)
break;
}
sort(ans.begin(), ans.end());
ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
return ans;
}
int main()
{
int N;
cin >> N;
vector<int> SL, SR;
for (int i = 0; i < N; i++)
{
int x;
cin >> x;
if (i & 1)
SL.push_back(x);
else
SR.push_back(x);
}
vector<pii> L = half(SL);
vector<pii> R = half(SR);
int p = 0;
int q = 0;
int LS = L.size();
int RS = R.size();
vector<bool> good(1 << N);
while (p < LS && q < RS)
{
if (L[p].first < R[q].first)
p++;
else if (L[p].first > R[q].first)
q++;
else
{
int p2 = p;
int q2 = q;
while (p2 < LS && L[p2].first == L[p].first)
p2++;
while (q2 < RS && R[q2].first == R[q].first)
q2++;
for (int i = p; i < p2; i++)
for (int j = q; j < q2; j++)
{
good[L[i].second | (R[j].second << SL.size())] = true;
}
p = p2;
q = q2;
}
}
int ans = count(good.begin() + 1, good.end(), true);
cout << ans << endl;
}