11851 - Celebrity Split

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11851 - Celebrity Split

Post by Angeh » Tue Oct 05, 2010 3:56 pm

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 ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11851 - Celebrity Split

Post by Leonid » Wed Oct 06, 2010 1:10 am

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.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11851 - Celebrity Split

Post by Angeh » Wed Oct 06, 2010 7:40 am

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 ?
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11851 - Celebrity Split

Post by Leonid » Wed Oct 06, 2010 11:06 pm

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;
}

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11851 - Celebrity Split

Post by Angeh » Thu Oct 07, 2010 2:31 pm

i have read somewhere in the web it could be solved in 3^(n/2) ...
but dont know how to get this ... Time ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11851 - Celebrity Split

Post by Igor9669 » Thu Oct 07, 2010 3:22 pm

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!

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11851 - Celebrity Split

Post by Leonid » Thu Oct 07, 2010 10:47 pm

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.!!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11851 - Celebrity Split

Post by Angeh » Fri Oct 08, 2010 8:28 am

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 ...]
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

caffeine
New poster
Posts: 2
Joined: Sun Oct 10, 2010 2:49 pm

Re: 11851 - Celebrity Split

Post by caffeine » Sun Oct 10, 2010 2:52 pm

can you explain in more detail please, i dont get it :(

thanks in advance

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11851 - Celebrity Split

Post by Angeh » Sun Oct 10, 2010 5:23 pm

split the numbers in 2 Group do an n^3 algorithm for each Group ... ... .... Leonids post ....
think about differances ... in reach Group ....
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Post Reply

Return to “Volume 118 (11800-11899)”