10125 - Sumsets

[yatsen]

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

[Whinii F.]

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

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]

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

[hank]

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

[hank]

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]

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]

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]

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]

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!!!

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?

[rasel04]

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]

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]

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]

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]

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