## 10125 - Sumsets

Moderator: Board moderators

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

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

### 10125 - from a novish

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;}`
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### 10125WA

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. `
IRA
Learning poster

Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

### 10125

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.
Last edited by asif_rahman0 on Wed Jun 07, 2006 3:44 pm, edited 1 time in total.
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
ayon
Experienced poster

Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

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:)
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

the problem is a+b+c=d
Code: Select all
`for(all a)   for(all b)      insert (a+b) at data structurefor(all d, starting from higher to lower)   for(all c)      if(d-c) is at the data structure...  :D `
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
ayon
Experienced poster

Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

thnx ayon.
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### I need some test cases:)

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
Last edited by nymo on Fri Jun 09, 2006 8:23 am, edited 1 time in total.
nymo
Experienced poster

Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### 10125 WAAAAAAAAAAA

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
`12no solutionno solutionno solutionno solutionno solution                           all Output is correct ( after edit)no solutionno solutionno solution6100`
Last edited by mohsincsedu on Wed Sep 06, 2006 9:21 pm, edited 4 times in total.
Amra korbo joy akhdin............................
mohsincsedu
Learning poster

Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka

### AC

I got AC.
I have a stupid mistake......
Thanks to all.
Amra korbo joy akhdin............................
mohsincsedu
Learning poster

Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka

### 10125

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

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");}`
walker2009
New poster

Posts: 1
Joined: Sun Mar 04, 2007 8:53 am

There are some threads on this problem..

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

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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

Here my code:

.......Code removed

Sapnil
sapnil
Experienced poster

Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST

### Re: 10125 - Sumsets

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
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
abid_iut
Learning poster

Posts: 80
Joined: Wed Jul 16, 2008 7:34 am

PreviousNext