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 (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.
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.
-
- 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 (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
The rest are details
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:
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[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<(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[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=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);
}
}
Re: WA-10125 (Sum Sets)
Read problem description more carefully: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.
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