## 10125 - Sumsets

Moderator: Board moderators

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10125 - Sumsets

I don't think a O(n^4) algo can pass the time limit. Try something better.
May be tomorrow is a better day............

ergysr
New poster
Posts: 9
Joined: Sun Oct 07, 2007 1:25 pm

### Re: 10125 - Sumsets

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!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10125 - Sumsets

'4 -1 0 1 0' is not a valid input, so you don't need to deal with it.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Re: 10125 - Sumsets

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

chchwy
New poster
Posts: 2
Joined: Sat Nov 22, 2008 10:45 am

### Re: 10125 - Sumsets

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

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10125 - Sumsets

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 10125 - Sumsets

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!

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 10125 - Sumsets

Try this case
Input :

Code: Select all

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

Code: Select all

-9

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### 10125 - Sumsets WA

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10125 - Sumsets WA

From uhunt:
Siegrift> for that problem 4 nested loops are sufficient
Check input and AC output for thousands of problems on uDebug!

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

### Re: 10125 - Sumsets

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

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

### Re: 10125 - Sumsets

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10125 - Sumsets

Yes all elements in the judge's input are distinct.
Check input and AC output for thousands of problems on uDebug!

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

### Why WA? Any test cases?

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10125 - Sumsets

That code won't compile
Check input and AC output for thousands of problems on uDebug!