## 10125 - Sumsets

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

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### 10125 - Sumsets

How to solve this problem effectively?
I got TLE Please help!
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### well,

I actually didn't program this problem :') but my teammate did.
I think this IS A SPOILER, so be careful to read.. =)

Try finding sums of every pair (a, b) of numbers in S, and storing them in a sorted array.
Then every pair of c and d, you can find (d-c) in the sorted array with binary search :')
That will give you O(n^2logn) and I think it's sufficient to solve the problem within the time limit.

Note: be aware that a, b, c, d must be unique.
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Just got AC. But my program runs about 1.8sec.. There are much faster solutions. Is there a better algorithm?

Can anybody got below 0.5sec, answer my question?
yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
I just got AC in 0.461 sec.
Thank Whinii F. for your algorithm.
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I programmed this problem and I used the method that Whinii F said.
But I still got TLE. What's wrong?
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### Re: well,

Whinii F. wrote: Try finding sums of every pair (a, b) of numbers in S, and storing them in a sorted array.
Doesn't it cost much time?
yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### Re: well,

hank wrote:
Whinii F. wrote: Try finding sums of every pair (a, b) of numbers in S, and storing them in a sorted array.
Doesn't it cost much time?
No.
n <= 1000, not too big.
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I solved this problem,it ran 0.205 sec. But on the rank list there is someone solved this problem and only ran 0.00 sec.How can it run so fast?
Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
Hi , experience posters. Can you help me with this coding ? why I got WA ????

please help !!!

Code: Select all

``````#include <stdio.h>

int main ( void )
{
long sequence , input ;
int NumOfElement , i , j , k , l ;
char flag ;

/*  freopen ( "10125.in" , "r" , stdin ) ;
freopen ( "10125.out" , "w" , stdout ) ;*/

while ( 1 )
{
scanf ( "%i" , &NumOfElement ) ;

if ( !NumOfElement ) break ;

for ( i = 0 ; i < NumOfElement ; i ++ )
{
scanf ( "%li" , &input ) ;

for ( j = 0 ; j < i && sequence[j] <= input ; j ++ ) ;

for ( k = i - 1 ; k >= j ; k -- )
sequence[k+1] = sequence[k] ;

sequence[j] = input ;
}

for ( i = NumOfElement - 1 , flag = 0 ; i > 2 ; i -- )
{
for ( j = i - 1 ; j > 1 ; j -- )
{
for ( k = j - 1 ; k > 0 ; k -- )
{
for ( l = k - 1 ; l >= 0 ; l -- )
if ( sequence[i] == sequence[j] + sequence[k] + sequence[l] ) { flag = 1 ; break ; }
if ( flag ) break ;
}
if ( flag ) break ;
}
if ( flag ) break ;
}

if ( flag )
printf ( "%li\n" , sequence[i] ) ;
else printf ( "no solution\n" ) ;
}

return 0 ;
}
``````
craniac
New poster
Posts: 2
Joined: Mon Jun 16, 2003 11:25 pm
Location: Poland
Try using a table with hashing function: You store the values of (a+b) there, and check them for appropriate values of (d-c). If you use a very good hashing function or a double-hashing algorythm and choose the best constants, then your program may run faster than 0.5s!!!
Whinii F. wrote:Just got AC. But my program runs about 1.8sec.. There are much faster solutions. Is there a better algorithm?

Can anybody got below 0.5sec, answer my question?
I want to know God's thoughts
The rest are details
rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

### 10125

Procedure:
1. Get all a+b and sorting them.
2.Find all (d-c) and find this by binary search from the above array.

But why wrong answer. PLS help.
Here is my code:

Code: Select all

``````

#include<stdio.h>
#include<stdlib.h>

typedef int LONG;
#define INF 2000000000

LONG arr,data;
int index;

int sfunc1(void const *a,void const *b)
{
LONG p,q;
p=*(LONG *)a;
q=*(LONG *)b;
if(p>q) return 1;
else return -1;
return 0;
}

int binsearch(LONG x)
{
int low,high,mid;
low=0;
high=index;

while(low<(high-1))
{
mid=(low+high)/2;
if(x<data[mid]) high=mid;
else low=mid;
}
if(x==data[low]) return low;
return -1;
}

void main()
{
int i,j,N,flag,r;
LONG a,max;

//freopen("10125.in","r",stdin);

while(scanf("%d",&N)==1 && N)
{
for(i=0;i<N;i++) scanf("%d",&arr[i]);
qsort(arr,N,sizeof(arr),sfunc1);
index=0;
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
data[index++]=arr[i]+arr[j];
}
}
qsort(data,index,sizeof(data),sfunc1);
max=-INF;
flag=1;
for(i=N-1;i>=0;i--)
{
for(j=i-1;j>=0;j--)
{
a=(arr[i]-arr[j]);
r=binsearch(a);
if(r!=-1)
{
if(arr[i]>max) max=arr[i];
flag=0;

}

a=(data[j]-arr[i]);
r=binsearch(a);
if(r!=-1)
{
if(arr[j]>max)max=arr[j];
flag=0;

}
}

}

if(flag==1) printf("no solution\n");
else printf("%d\n",max);
}
}``````
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### Re: WA-10125 (Sum Sets)

rasel04 wrote:Procedure:
1. Get all a+b and sorting them.
2.Find all (d-c) and find this by binary search from the above array.

But why wrong answer. PLS help.
Read problem description more carefully:
where a, b, c, and d are distinct elements of S.
And come back when you get TLE. neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### 10125 WA :(

I am trying to solve this problem using a brute force algorithm and I am getting WA, I don't know why!!!

This is my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int a, b, c, d, n, arre[MAX + 1];

int pepe(const void *a, const void *b)
{
return *((int*)a) - *((int*)b);
}

void ReadData()
{
for (a = 0; a < n; a++)
scanf("%d", &arre[a]);
}

void MakeSolu()
{
qsort(arre, n, sizeof(int), pepe);

for (d = n - 1; d >= 3; d--)
for (c = d - 1; c >= 2; c--)
for (b = c - 1; b >= 1; b--)
for (a = b - 1; a >= 0; a--)
if (arre[a] + arre[b] + arre[c] == arre[d])
{
printf("%d\n", arre[d]);
return;
}

puts("no solution");
}

int main()
{
scanf("%d", &n);

while (n)
{
ReadData();
MakeSolu();
scanf("%d", &n);
}

return 0;
}
``````
I think a TLE error could be logic but WA!!!, what do you say???, waiting for your help,

Yandry.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
A simple test case which your program does not pass:

Code: Select all

``````5
-8 4 10 11 14``````
The answer is 10, which can be written as: 10 = -8 + 4 + 14.
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Thanx mf, I will try to solve this with another algorithm. 