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

Post by yatsen » Wed Mar 05, 2003 10:02 am

How to solve this problem effectively?
I got TLE :cry:
Please help!

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

well,

Post by Whinii F. » Sat Mar 08, 2003 5:02 am

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:

Post by Whinii F. » Sat Mar 08, 2003 1:05 pm

Just got AC. :D 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

Post by yatsen » Mon Mar 10, 2003 11:24 am

I just got AC in 0.461 sec.
Thank Whinii F. for your algorithm.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sat Mar 15, 2003 7:31 am

I programmed this problem and I used the method that Whinii F said.
But I still got TLE. What's wrong?

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Re: well,

Post by hank » Sat Mar 15, 2003 7:45 am

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,

Post by yatsen » Mon Mar 17, 2003 11:10 am

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.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Mar 18, 2003 12:08 pm

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

Post by Almost Human » Wed May 07, 2003 10:51 am

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

craniac
New poster
Posts: 2
Joined: Mon Jun 16, 2003 11:25 pm
Location: Poland

Post by craniac » Sun Jul 06, 2003 9:47 pm

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. :D 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

Post by rasel04 » Tue Mar 30, 2004 11:08 pm

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

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Re: WA-10125 (Sum Sets)

Post by minskcity » Fri Aug 27, 2004 7:55 pm

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. :wink:

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

10125 WA :(

Post by neno_uci » Mon Jun 06, 2005 6:43 pm

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:

Post by mf » Mon Jun 06, 2005 7:25 pm

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

Post by neno_uci » Mon Jun 06, 2005 10:38 pm

Thanx mf, I will try to solve this with another algorithm. :D

Post Reply

Return to “Volume 101 (10100-10199)”