## 11851 - Celebrity Split

**Moderator:** Board moderators

### 11851 - Celebrity Split

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

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

Beliefs are not facts, believe what you need to believe;)

### Re: 11851 - Celebrity Split

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.

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

I have Tried this ...But getTime Limit ...

2^n with pruning .... to Generate all Subsets with Sum S

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 Sfor 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 ?This works even Slower than the N^3 solution ....

have You Got AC ?

>>>>>>>>> A2

Beliefs are not facts, believe what you need to believe;)

Beliefs are not facts, believe what you need to believe;)

### Re: 11851 - Celebrity Split

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.

And here is the TLE solution:

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
```

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

i have read somewhere in the web it could be solved in 3^(n/2) ...

but dont know how to get this ... Time ...

but dont know how to get this ... Time ...

>>>>>>>>> A2

Beliefs are not facts, believe what you need to believe;)

Beliefs are not facts, believe what you need to believe;)

### Re: 11851 - Celebrity Split

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

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 Finally AC in 4.66 sec.!!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!

### Re: 11851 - Celebrity Split

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

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

Beliefs are not facts, believe what you need to believe;)

### Re: 11851 - Celebrity Split

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

thanks in advance

thanks in advance

### Re: 11851 - Celebrity Split

split the numbers in 2 Group do an n^3 algorithm for each Group ... ... .... Leonids post ....

think about differances ... in reach Group ....

think about differances ... in reach Group ....

>>>>>>>>> A2

Beliefs are not facts, believe what you need to believe;)

Beliefs are not facts, believe what you need to believe;)