10125  Sumsets
Moderator: Board moderators
10125  Sumsets
How to solve this problem effectively?
I got TLE
Please help!
I got TLE
Please help!

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

 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 !!!
please help !!!
Code: Select all
#include <stdio.h>
int main ( void )
{
long sequence[1010] , 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 ;
}
Try using a table with hashing function: You store the values of (a+b) there, and check them for appropriate values of (dc). If you use a very good hashing function or a doublehashing 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
The rest are details
10125
Procedure:
1. Get all a+b and sorting them.
2.Find all (dc) and find this by binary search from the above array.
But why wrong answer. PLS help.
Here is my code:
1. Get all a+b and sorting them.
2.Find all (dc) 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[1005],data[1000009];
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<(high1))
{
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[0]),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[0]),sfunc1);
max=INF;
flag=1;
for(i=N1;i>=0;i)
{
for(j=i1;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);
}
}
Re: WA10125 (Sum Sets)
Read problem description more carefully:rasel04 wrote:Procedure:
1. Get all a+b and sorting them.
2.Find all (dc) and find this by binary search from the above array.
But why wrong answer. PLS help.
And come back when you get TLE.where a, b, c, and d are distinct elements of S.
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:
I think a TLE error could be logic but WA!!!, what do you say???, waiting for your help,
Yandry.
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;
}
Yandry.
A simple test case which your program does not pass:
The answer is 10, which can be written as: 10 = 8 + 4 + 14.
Code: Select all
5
8 4 10 11 14