10125 - Sumsets

[shamim]

I was wondering, can this problem be solved without doing the n^2log(n) sorting.

[smilitude]

can it be done in this way, without dp , using optimization?
i am novish to dp, again can you plz explain me just the way by which can be done in dp? i will be greatly helped! understanding dp is a great deal to me right now!

Code: Select all

/*
 * 10125 sumsets
 * submission 1 TLE
 * coded at 9:29am 26th dec 05
 *
 */


#include <stdio.h>

int main() {
   long a, b, c, d;
   long max_d;
   int n;
   long list[1000];

   while(scanf("%d",&n) && n) {
      max_d=-1;
      for(int i=0;i<n;i++)
         scanf("%ld",&list[i]);
      //i am confused, can i omit those continue statement??
      for(a=0;a<n;a++) {
         for(b=0;b<n;b++) {
            if(a==b) continue;
            for(c=0;c<n;c++) {
               if(c==b || c==a) continue;
               for(d=0;d<n;d++) {
                  if(d==a||d==b||d==c)   continue;
                  if(list[a]+list[b]+list[c]==list[d])
                     if(list[d]>max_d) max_d=list[d];
               }
            }
         }
      }
      
      if(max_d==-1) printf("no solution\n");
      else printf("%ld\n",max_d);
   }
return 0;
}



[IRA]

I have got WA many times!
I didn't find the mistake...
I use many test data to test...But can't find the error.
Who can help me?

I have find my mistake and got AC...
I didn't see that find the largest d..............

Code: Select all

find the (largest d) such that a + b + c = d where a, b, c, and d are distinct elements of S.


[asif_rahman0]

i tried so many times but i m getting TLE.
so where is my fault? is there any tricks??

Code: Select all

removed


help would be appreciated.

[ayon]

yours algorithm is O(n^3), n can be at most 1000, surely gives you TLE, anyway i solved this problem using O(n^2*logn), but might have some better process

[asif_rahman0]

hi ayon,

can u give me some hints abt the O(n^2*logn).
just need abt O(n^2).
not O(log(n)) part.
then it would be easy for me.
coz i wasted too much time for it.

help would be appreciated:)

[ayon]

the problem is a+b+c=d

Code: Select all

for(all a)
   for(all b)
      insert (a+b) at data structure
for(all d, starting from higher to lower)
   for(all c)
      if(d-c) is at the data structure...  :D

[asif_rahman0]

thnx ayon.

[nymo]

Please, can anyone provide me some test cases? I 've got 10 straight WAs in this problem
[EDIT] just after the previous post, I 've found my error, in some cases, I was printing more than one answer, Should have breaked the loop earlier

[mohsincsedu]

Please gime me some I/O:

For my worng code::

Input:
5
2
3
5
7
12
5
2
16
64
256
1024
5
1
2
3
4
5
5
5
4
3
2
1
10
1
1
1
1
1
1
1
1
1
1
1
5
2
5
6
3
5
6
7
4
5
6
7
8
4
6
3
2
1
5
-8
4
10
11
14
4
-1
0
1
0
0

WA Output::

Code: Select all

12
no solution
no solution
no solution
no solution
no solution                           all Output is correct ( after edit)
no solution
no solution
no solution
6
10
0

[mohsincsedu]

I got AC.
I have a stupid mistake......
Thanks to all.

[walker2009]

i am newbie
can you help me to solve my problem ?
please

Code: Select all

#include <stdio.h>

void swap( int *a, int *b );
void bubble1( int n );
void bubble2( int n );
void search( int n1, int n2 );

int e[1000];
int a[500000];
int b[500000];
int x[500000];

int main( void )
{
   int number;
   int count;
   int i,j;
   
   while (1)
   {
      count=0;
      scanf( "%d", &number );
      if ( number == 0 )
         return 0;      
      while ( count < number )
      {
         scanf( "%d", &e[count] );
         count++;
      }
      
      bubble1( number );

      count=0;
      for( i=0; i<number; i++)
      {
         for( j=i+1; j<number; j++ )
         {
            a[count]=i;
            b[count]=j;
            x[count]=e[i]+e[j];
            count++;
         }
      }   
      bubble2( count );
      search( number, count );      
   }
}

void bubble1( int n )
{
   int i,j;

   for( i=0; i<=n-2; i++)
   {
      for( j=0; j<=n-i-2; j++ )
      {
         if( e[j]<e[j+1] )
            swap( &e[j], &e[j+1] );
      }
   }
}

void bubble2( int n )
{
   int i,j;

   for( i=0; i<=n-2; i++)
   {
      for( j=0; j<=n-i-2; j++ )
      {
         if( x[j]>x[j+1] )
         {
            swap( &x[j], &x[j+1] );
            swap( &a[j], &a[j+1] );
            swap( &b[j], &b[j+1] );
         }
      }
   }
}

void swap( int *a, int *b)
{
   int temp;
   
   temp=*a;
   *a=*b;
   *b= temp;
}

void search( int n1, int n2 )
{
   int ub,lb,m,key;
   int i,j,k;
   for( i=0; i<n1; i++ )
   {
      for( j=0; j<n1; j++ )
      {
         key=e[i]-e[j];
         lb=0;
         ub=n2-1;
         while( lb <= ub )
         {
            m=(lb+ub)/2;
            if( key<x[m] )
               ub=m-1;
            else if( key>x[m] )
               lb=m+1;
            else
            {
               if( !( (a[m]==b[m])||(a[m]==i)||(a[m]==j)||(b[m]==i)||(b[m]==j)||(i==j) ) )
               {
                  printf("%d\n",e[i]);
                  return;
               }
               k=m;
               while( key==x[k+1] && k+1<n1 )
               {
                  k=k+1;
                  if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
                  {
                     printf("%d\n",e[i]);
                     return;
                  }
               }
               k=m;
               while( key==x[k-1] && k-1>=0 )
               {
                  k=k-1;
                  if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
                  {
                     printf("%d\n",e[i]);
                     return;
                  }
               }
               break;
            }
         }
      }
   }
   printf("no solution\n");
}

[helloneo]

There are some threads on this problem..
Do not create a new thread if there is one already..

http://online-judge.uva.es/board/viewtopic.php?t=2460
http://online-judge.uva.es/board/viewtopic.php?t=10824

[sapnil]

Why i get WR.
plz anyone help me....................

Here my code:

.......Code removed

Sapnil

[abid_iut]

I got TLE
I thought it would pass O(n^4)algorithm
here is the part of the code:

Code: Select all

for(a=0;a<n;a++){
         for(b=0;b<n;b++){
            if(a==b)continue;
            for(c=0;c<n;c++){
               if(c==a || c==b)continue;
               for(d=0;d<n;d++){
                  if(d==a || d==b || d==c)continue;
                  if(num[a]+num[b]+num[c]==num[d])
                     if(num[d]>max)max=num[d];
               }
            }
         }
      }
      if(max==0)printf("no solution\n");
      else printf("%d\n",max);


is this ok? can it be done in this way without using DP
pls give some suggestion