Page 1 of 1

11851 - Celebrity Split

Posted: Tue Oct 05, 2010 3:56 pm
by Angeh
Hi, Experts ...
i get TL consistently ...
How To avoid it ...
i try backtarcking 3^n with some Pruning s ...

can any body give some hints ...??
Thanks in advance ...

Re: 11851 - Celebrity Split

Posted: Wed Oct 06, 2010 1:10 am
by Leonid
I couldn't find any efficient solution so far.

But I believe with some optimization it should be possible to break the tests. 3^n definitely is not a solution and will TLE..

One way to approach the problem is to store all subsets which give the sum S and then iterate through each sum Si. If sum Si can be achieved using 2 non-intersecting subsets then the solution exists for Si. However, I don't know how to solve the worst case when all prices in input are equal. The problem of finding non-intersecting subsets seems to be equivalent to checking if the graph is a clique. The problem is that for C(24,12) that graph will contain about 2.7 * 10^6 nodes, however graph has some properties which possibly can be used to reduce the running time or optimize.

Re: 11851 - Celebrity Split

Posted: Wed Oct 06, 2010 7:40 am
by Angeh
I have Tried this ...But getTime Limit ...
2^n with pruning .... to Generate all Subsets with Sum S .. i could be as much as ... ^25 ...
for test Case
24
1000001
1000002
1000004
1000008
1000016
.
.
.

then for each S .. (S.size)*(S.size ) to find 2 non-intersecting subsets....
This works even Slower than the N^3 solution ....
have You Got AC ?

Re: 11851 - Celebrity Split

Posted: Wed Oct 06, 2010 11:06 pm
by Leonid
No I haven't got AC for this problem, simply stuck as you are :) When subset size is fixed 12 there will be 2704156 subsets with the same sum. Obviously the number of iterations is 2704156^2 and that is why it's slower than 3^n.

I'm suspecting there is different solution for this problem, which has to do with a common optimization that is done for a Subset Sum Problem. With a hell of a lot optimizations I was able today to calculate the solution for near worst case (see below) in around 4 sec, and around 2 * 10^8 iterations. But that is still not enough and results in TLE.

Code: Select all

24
11550995 13750698 20867072 16220643 7903831 13490772 5576556 32634911 13342178 15893883 29230329 27127367 13045515 38976740 9814065 2042692 13644431 8194156 33119358 38302143 24275786 12674407 24354079 4259509 
0
And here is the TLE solution:

Code: Select all

int DP[1<<24];
int WHEREISONE[1<<24];
void findBits() {
	for (int i = 0; i < 24; i++) {
		WHEREISONE[(1 << i)] = i;
	}
}

map<int, vector<int> > SAVED;

static int iter2 = 0;
static int iter1 = 0;
bool solutionExists(vector<int>& items, int subset, int sum) {
	vector<int> S;
	for (int i = 0; i < items.size(); i++) {
		if ( (subset >> i) & 1) {
			S.push_back(i);
		}
	}

	int l = 0, r = 0;
	for (int i = 0; i < S.size() / 2; i++) r |= 1 << S[i];
	for (int i = S.size() / 2; i < S.size(); i++) l |= 1 << S[i];

	vector<int> *right, *left;

	if (SAVED.find(r) != SAVED.end()) right = &SAVED[r];
	else {
		right = &SAVED[r];
		set<int> sr;
		sr.insert(0);
		for (int i = 0; i < S.size() / 2; i++) {
			for (set<int>::reverse_iterator ii = sr.rbegin(); ii != sr.rend(); ++ii) {
				sr.insert(*ii + items[S[i]]);
				iter1++;
			}
		}
		for (set<int>::iterator ii = sr.begin(); ii != sr.end(); ++ii) {
			right->push_back(*ii);
		}
	}

	if (SAVED.find(l) != SAVED.end()) left = &SAVED[l];
	else {
		left = &SAVED[l];
		set<int> sl;
		sl.insert(0);
		for (int i = S.size() / 2; i < S.size(); i++) {
			for (set<int>::reverse_iterator ii = sl.rbegin(); ii != sl.rend(); ++ii) {
				sl.insert(*ii + items[S[i]]);
				iter1++;
			}
		}
		for (set<int>::iterator ii = sl.begin(); ii != sl.end(); ++ii) {
			left->push_back(*ii);
		}
	}

	int cursum = 0;
	vector<int>::iterator ii = right->begin();
	vector<int>::reverse_iterator jj = left->rbegin();
	while (ii != right->end() && jj != left->rend())
	{
		iter2++;
		int s = *ii + *jj;
		if (s == sum) return true;
		if (s < sum) ++ii;
		if (s > sum) ++jj;
	}
	return false;
}

void printBits(int n) {
	while (n) {
		printf("%d", n & 1);
		n >>= 1;
	}
}

int bitSum(int n) {
	int s = 0;
	while (n) {
		s += (n & 1);
		n >>= 1;
	}
	return s;
}

bool solve()
{
	int n; scanf("%d ",&n);
	if (!n) return false;

	vector<int> items(n);
	for (int i = 0; i < n; i++) scanf("%d ", &items[i]);
	int sum = 0;
	for (int i = 0; i < n; i++) sum += items[i];
	int mask = (1 << n) - 1;

	int halfsum = sum / 2;
	int best = 0;
	for (int i = 1; i < (1 << n); i++) {

		int p = i & (i - 1);
		int b = i - p;
		int w = WHEREISONE[b];
		DP[i] = DP[p] + items[w];
		if (DP[i] > halfsum) continue;
	}

	SAVED.clear();

	int real = 0;
	for (int i = (1 << n); i >= 0; i--) {
		if (DP[i] > halfsum || DP[i] <= best || bitSum(i) < n / 2) continue;
		real++;

		if (solutionExists(items, mask ^ i, DP[i])) {
			best = DP[i];
		}
	}

	printf("%d\n", sum - 2 * best);

	return true;
}

Re: 11851 - Celebrity Split

Posted: Thu Oct 07, 2010 2:31 pm
by Angeh
i have read somewhere in the web it could be solved in 3^(n/2) ...
but dont know how to get this ... Time ...

Re: 11851 - Celebrity Split

Posted: Thu Oct 07, 2010 3:22 pm
by Igor9669
Divide into to 2 groups by n/2 elements each and find for each group a solution with your O(3^n) algo! I have not yet tried this problem but I think it will be right idea!

Re: 11851 - Celebrity Split

Posted: Thu Oct 07, 2010 10:47 pm
by Leonid
Igor9669 wrote:Divide into to 2 groups by n/2 elements each and find for each group a solution with your O(3^n) algo! I have not yet tried this problem but I think it will be right idea!
That sounds like a very good idea to divide the elements into 2 groups of O(3^(n/2)). But it's also important how 2 subsets from each group are joined together, that shouldn't be difficult to see in fact what the solution is, when you starting thinking about how to join them, so leaving that pleasure to you guys to figure out :D Finally AC in 4.66 sec.!!

Re: 11851 - Celebrity Split

Posted: Fri Oct 08, 2010 8:28 am
by Angeh
Uhum ... Excellent Problem ....
Thanks igor ... Thanks Leo for that link ... i learned many things ...
Got Ac in 0.204 s ...
Keep Posting ...
[could some body help on problem 11853-Paint Ball ...]

Re: 11851 - Celebrity Split

Posted: Sun Oct 10, 2010 2:52 pm
by caffeine
can you explain in more detail please, i dont get it :(

thanks in advance

Re: 11851 - Celebrity Split

Posted: Sun Oct 10, 2010 5:23 pm
by Angeh
split the numbers in 2 Group do an n^3 algorithm for each Group ... ... .... Leonids post ....
think about differances ... in reach Group ....