Page 3 of 4

### Re: 10125 - Sumsets

Posted: Sun Jan 04, 2009 10:50 pm
I don't think a O(n^4) algo can pass the time limit. Try something better.

### Re: 10125 - Sumsets

Posted: Wed Jan 14, 2009 5:29 pm
For input 4 -1 0 1 0 the correct output from an old post is 0. logically , -1 + 0 + 1 = 0, but these elements are not distinct(zero appears twice). Can someone give me an explanation.

Thanks!

### Re: 10125 - Sumsets

Posted: Thu Jan 15, 2009 4:31 am
'4 -1 0 1 0' is not a valid input, so you don't need to deal with it.

### Re: 10125 - Sumsets

Posted: Sun Jan 25, 2009 6:10 pm
I am wondering if there is a better method/approach/idea for solving
this problem (different from the one already described above in this thread).

If I am not mistaken the method described above has worst-case
time complexity O( N^2 * log(N^2) ) which basically simplifies down
to O( N^2 * log(N) ) if we ignore the constants
(when estimating the time complexity).

### Re: 10125 - Sumsets

Posted: Thu Mar 18, 2010 3:18 am
the O(n^4) algorithm can get AC actually !

but need some tips

Code: Select all

``````sort array first

for( d = N to 1 )  //from higher to lower
for( a = 1 to N )
for( b = a+1 to N )
for( c = b+1 to N )
//do comparison here ..

``````
the tip is put the loop d outside, and from higher to lower

it's very efficeint , even faster than (a+b) = (d-c) way

### Re: 10125 - Sumsets

Posted: Wed Apr 21, 2010 7:38 am
Yea,the O(n^4) complexity algorithm can pass the time limit,even in better way than O((N^2)*lg(n^2)) algorithm.But this is not because of the efficiency of O(n^4) algorithm,rather because of the weak data set.In the worst case,when answer is 'no solution' it may have to check almost (1000*1000*1000*1000) combination.

### Re: 10125 - Sumsets

Posted: Sun Apr 29, 2012 9:08 pm
Articuno wrote:I don't think a O(n^4) algo can pass the time limit. Try something better.
i've got ac with O(n^4), but with some optimization!

### Re: 10125 - Sumsets

Posted: Fri Jul 06, 2012 10:07 am
Try this case
Input :

Code: Select all

``````4
-3 -3 -3 -9
0``````
Output :

Code: Select all

``````-9
``````

### 10125 - Sumsets WA

Posted: Fri Sep 13, 2013 6:12 pm
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>

int set[1010];
void Qsort(int, int);
int search(int, int, int );

int main(void) {

int t, i, j, k, a, ok;
while(scanf("%d", &t), t)
{
for(i = 0; i < t; i++)
scanf("%d", &set);
Qsort(0, t-1);
ok = 0;
for(i = 0; i < t; i++)
{
for(j = i+1; j < t; j++)
{
a = set+set[j];
for(k = t-1; k >= 0; k--)
{
if(set[k] != set && set[k] != set[j] && set[k]-a != set && set[k]-a != set[j] && a != 0)
if(search(set[k]-a, 0, t-1))
{
ok = 1;
break;
}
}
if(ok)
break;
}
if(ok)
break;
}
if(ok)
printf("%d\n", set[k]);
else
printf("no solution\n");
}
return 0;
}

void Qsort(int low, int high)
{
int p = low, q = high, a;
if(low >= high)
return;
a = set[low];
while(p < q)
{
while(p < q && set[q] > a)
q--;
if(p < q)set[p++] = set[q];
while(p < q && set[p] < a)
p++;
if(p < q)set[q--] = set[p];
}
set[p] = a;
Qsort(low, p-1);
Qsort(p+1, high);
}

int search(int result, int low, int high)
{
int mid;
while(low <= high)
{
mid = (low + high)/2;
if(result > set[mid])
low = mid+1;
else if(result < set[mid])
high = mid-1;
else
return 1;
}
return 0;
}

### Re: 10125 - Sumsets WA

Posted: Fri Sep 13, 2013 9:20 pm
From uhunt:
Siegrift> for that problem 4 nested loops are sufficient

### Re: 10125 - Sumsets

Posted: Fri Sep 20, 2013 9:17 pm
well, as far as optimizations go, you can make up to O(n^3), heck even O(n^2).

O(n^4): brute force
O(n^3): DP - sort all data, make a for-loop for a, b, c, then get maximum a+b+c that is in the set (use hash_map for constant check)
O(n^2): DP - sort all data, store in memo all distinct pairs a+b, then make a reverse for-loop to check if (d-c) exists in memo such that a!=b!=c!=d

i don't know how the O(n^4) algo passed the runtime, but i implemented the O(n^2) algo, which i think is the official solution to the problem

### Re: 10125 - Sumsets

Posted: Mon Oct 28, 2013 4:07 pm
@li_kuet wrote:Try this case
Input :

Code: Select all

``````4
-3 -3 -3 -9
0``````
Output :

Code: Select all

``````-9
``````
The output is wrong I thot? All numbers in the set must be distinct..

### Re: 10125 - Sumsets

Posted: Mon Oct 28, 2013 8:11 pm
Yes all elements in the judge's input are distinct.

### Why WA? Any test cases?

Posted: Wed Oct 30, 2013 9:01 am
I have got WA for this problem a few times.. I use the d-c = a+b algorithm.. Can I hav some datasets to further test the code (all io is correct)?

Code: Select all

``````#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<cmath>
#include<map>

using namespace std;

#define LOOP(times) for(int(i) = 0;i<times;i++)

typedef vector<int> vi;

typedef set<int> st;
typedef st::iterator sIter;
typedef st::reverse_iterator sRevIter;

typedef map<int,int> mii;
typedef mii::iterator mIter;

int main(){
int i,a,b;
int n,x,sum,diff;

st s,soln;
sIter sit;
sRevIter srit;

vi S,ab;

mii dc;
mIter it;

/*
freopen("sumsets.in","r",stdin);
freopen("sumsets.out","w",stdout);
//*/
while(scanf("%d",&n)!=EOF){
if(!n) break;

bool solution = false;

for(i=0;i<n;i++){
scanf("%d",&x);
s.insert(x);
//set will not only sort but remove similar occurences
}

if(s.size()<4){
printf("no solution\n");
s.clear();
continue;
}

for(sit=s.begin();sit!=s.end();sit++){
S.push_back(*sit);
}

ab.push_back(S[n-1]+S[0]);
dc.insert(make_pair(S[n-1]-S[0],S[n-1]));

for(a=0;a<n-1;a++){
//if(S[a] != S[a+1]){
sum = S[a]+S[a+1]; //a+b
diff = S[a+1]-S[a]; //d-c
ab.push_back(sum);
dc.insert(make_pair(diff,S[a+1]));
//}
}

sort(ab.begin(),ab.end());

for(b=0;b<ab.size();b++){ //Search
it = dc.find(ab[b]);
if(it!=dc.end()){ //rejoice
//printf("%d",it->second);
soln.insert(it->second);
solution = true;
//break;
}
}

if(!solution){
printf("no solution");
}
else{
srit = soln.rbegin();
printf("%d",*srit);
}

printf("\n");

S.clear();
s.clear();
ab.clear();
dc.clear();
soln.clear();
}

return 0;
}

``````

### Re: 10125 - Sumsets

Posted: Thu Oct 31, 2013 10:49 pm
That code won't compile